撥召公車問題之探討－應用於非營利組織

A Dial-a-Ride Problem Applied in Non-profit Organization

楊建志(Chien-Chih Yang)

指導教授 ： 溫于平

國立清華大學/工學院/工業工程與工程管理學系/碩士(2010年)

摘要

摘要
隨著社會福利的發展，老年人與身心障礙者的大眾運輸模式日益受到社會大眾的關注。撥召公車是一種有效且符合老年人與身心障礙者需求的運輸模式。一般而言，撥召公車的服務通常是由非營利組織提供。在本論文中，我們考慮一些特別的限制，例如提供撥召公車服務的組織需要滿足一定的汽車使用率才能向政府社會福利部門申請營運補助經費。我們發展出一個靜態且為固定時窗的混合整數數學模型並且將這個限制加入數學模型中。這個模型的目標函數為最短總旅行時間。實際上，撥召公車排班人員會利用時間矩陣來估計每個地點間的旅行時間，因此我們也利用相同的方式來估計旅行時間。我們把實際需求資料帶到本研究提出的模型中並且將得到的結果與排班人員所排出來的班表進行比較。從比較結果中可以發現到由本研究所提出的模型排出來的班表在汽車總旅行時間與汽車空駛時間上都有較佳的表現。另外，我們試著調整時間窗的大小，我們可以發現到若增加時間窗的範圍，目標函數值會隨之降低，但是計算時間也跟著增加。我們也將此模型應用在不同的汽車上限乘載量。本研究所提出的模型可以被應用在實際需求資料，而且此模式的表現結果比由排班人員所排出來的班表佳。

關鍵字：撥召公車問題，路線規劃問題

ABSTRACT
For developing social welfare, convenient and safe vehicle routes for elderly and disabled has been paid attention. Dial-a-ride (DAR) is one of the efficient transit modes that satisfy the transportation demands of elderly and disabled. In general, DAR service is offered by non-profit organization. In this thesis, we consider the regulation for applying grants of the social welfare department of the government and develop a static mixed-integer model with hard time window. The objective function of the proposed model is to minimize the total traveling time. We estimate the traveling time by time matrix which is an approximate method using in real world. We solve the scheduling problems which were planned by experienced dispatchers by using the proposed model. The result of proposed model is used to compare the rough practicing model which is planned by the dispatchers. The results show that total traveling time and the vehicle riding time without passengers of the proposed model is better than the rough practicing schedule. Furthermore, we try to adjust the range of time window. Increasing the range of time window will reduce the objective function value but increasing the executing time. Besides, the proposed model can be applied by considering multiple riders in a vehicle. The proposed model can solve the DAR request data in real world and the performance of the result is better than the rough practicing schedule.

Keywords: Dial-a-Ride, Vehicle Routing Problem

關鍵字

撥召公車問題 ； 路線規劃問題

並列摘要

無資料

並列關鍵字

Dial-a-Ride ； Vehicle Routing Problem

參考文獻

1. Berbeglia, G., J.F. Cordeau, I. Gribkovskaia, and G. Laporte. "Static pickup and delivery problems: a classification scheme and survey." TOP, 2007: 1-31.

4. Cordeau, J.F. "A Branch-and-Cut Algorithm for the Dial-a-Ride Problem." Operations Research, 2006: 573-586.

5. Cordeau, J.F., and G. Laporte. "A tabu search heuristic for the static multi-vehicle dial-a-ride problem." Transportation Research Part B: Methodological, 2003: 579-594.

6. Cullen, F.H., J. J. Jarvis, and H. D. Ratliff. "Set partitioning based heuristics for interactive routing." Networks, 1981: 125 - 143.

7. Desrosiers, J., Y. Dumas, and F. Soumis. "A dynamic programming solution of the large-scale single-vehicle dial-a-ride problem with time windows." American Journal of Mathematical and Management Sciences, 1986: 301-326.