載運乘客時允許車輛暫停等待之撥召公車問題

The Dial-a-Ride Problem that Allows Vehicles Idle When Carrying Passengers

萬紘杰(Hung-Chieh Wan)

指導教授 ： 溫于平

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

https://doi.org/10.6843/NTHU.2007.00043

摘要

大眾運輸隨著一個城市的發展而愈益重要；交通建設幫助促進經濟發展、民生、社會福利等需求，而當建設發展至一程度，我們需重新考慮其使用效率來因應所伴隨產生的問題。私人載具在道路使用上相當沒有效率，卻因社會經濟力提升與具有高度使用彈性而普及。撥召公車(DAR)系統，不須像傳統大眾運輸定時定線的運作，本文進一步放鬆—車上有人時，公車不得暫停—的限制，利用車上乘客的繞行時間，來提高車輛利用率以及降低乘客等待公車到達的時間，藉由轉換乘客的兩種不方便來減少車輛行駛距離。
我們採用regret insertion解決此NP-hard問題，在小型問題上，其表現與最佳解的差距在5.16%之內。在允許車輛暫停之後，為了分別一條途程可行與否，我們提出了postponement的想法，取代原本不允許暫停的schedule block。實驗結果顯示了系統在不同的人數、車數與不同服務水準下，一些重要的現象，以及採用暫停策略為系統帶來的效益；如我們所預期，乘客的繞行時間增加，使得車輛的運行時間與乘客的等待時間減少。在DAR中，高的繞行率使系統運作較有效率，而暫停的效益也較易突顯；另外，在一個服務人口密度高的區域，DAR也較能夠發揮其作用；若DAR能藉由提升車隊大小來保持服務品質，吸引更多人願意使用此服務，則對雙方將是一很好的良性循環。

關鍵字

撥召公車 ； 暫停 ； 可行性檢驗 ； regret插入法

並列摘要

The development of mass transits is imperative as one city develops. The traffic facilities help promote the economic, people’s livelihood, social welfare and so forth. Once they are complete, the operating efficiency should be reconsidered to meet the following troubles such as pollutions and traffic congestion. Automobiles are always the preferences of people since people can travel everywhere at any time. Dial-a-Ride (DAR) appears to improve the traditional mass transits for its flexible service routes and schedules. A common restriction, no-idle with someone onboard, is relaxed in this thesis. It is our idea to raise the utilization of the fleet and make people wait few times for the arrival of vehicles at the cost of extra ride time of passengers onboard.
The regret insertion heuristic is adopted to solve this complex problem. In order to verify the feasibility of one route after we allow the vehicles idle when carrying passengers, we propose the concept of postponement in place of the schedule block for no-idle problems. Regret insertion gives solutions within 5.16% gaps in small scale problems. Experiment results display important phenomenon in different problem sizes and service qualities and mainly reveal the effects after introducing the idle strategy. We decrease the traveling time and the wait time of passengers by increase the extra ride time of passengers onboard as our expectancy. In such a system with strict time windows, the higher detour rate makes it operate more efficiently. The efficiency also increases while more people participate in DAR. If the operators can provide more vehicles, this will be a good cycle to develop this transit system.

並列關鍵字

Dial-a-Ride ； idle ； feasibility check ； regret insertion

參考文獻

[2] Cordeau, J.F., “A branch-and-cut algorithm for the dial-a-ride problem,” Operations Research, 54, 573-586(2006).

[3] Cordeau, J.F. and G. Laporte, “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research B, 37, 579-594(2003).

[4] Cordeau, J.F. and G. Laporte, “The dial-a-ride problem (DARP): Variants, modeling issues and algorithms,” Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1, 89-101(2003).

[5] Cullen, F.H., J.J. Jarvis and H.D. Ratliff, “Set Partitioning based heuristics for interactive routing,” Networks 11, 125-143 (1981).

[6] 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, 6, 301-325(1986).