撥召服務最佳化指派作業之研究

A Study on the Optimal Assignment Operation for the Dial-and-Ride Problem.

黃漢瑄(Han-Hsuan Huang)

指導教授 ： 邱顯明

淡江大學/管理學院/運輸管理學系碩士班/碩士(2006年)

https://doi.org/10.6846/TKU.2006.00487

摘要

撥召服務系統具有傳統公車系統之服務容量並能提供高度之及門性與即時性，因此除了一般載客之外常被用以服務行動不便者，例如老年人、病患與身心障礙者等。其服務方式須由顧客先行預約，再透過系統將數筆預約進行路線排程。撥召服務問題即為求解此一型式之運輸系統路線排程之車輛繞徑問題。
在問題之求解上，諸多研究皆使用節點再插入法(Vertex Reinsertion)作為臨近解搜尋之方法，然而傳統逐點插入法在搜尋上之效率不佳，因此許多研究皆設計搜尋範圍之限制機制。雖然以再插入法進行搜尋之方法已為撥召服務問題之主流作法，然而在各類車輛繞徑問題中廣被應用之各類巨集啟發式演算法卻鮮少應用於撥召服務問題，
本研究的主要目的在於嘗試將基因演算法(Genetic Algorithm)與蟻群演算法(Ant Colony Optimization)用以求解多車輛撥召服務問題。除了探討此兩類演算法在最佳化撥召服務問題應用上之可能性外，在求解流程上將區分為分群與繞徑兩階段求解以及整體一階段求解兩種形式，並組合兩類演算法以找出最適之求解方式與演算法設定。透過例題之求解發現，以變異性控制適應性基因演算法(Diversity-controlling Adaptive Genetic Algorithm)其結果較佳，而蟻群演算法求解速度較快。
另外，本研究亦將撥召服務問題做一隨機處理，將路網旅行時間加入動態之觀點，並評估於動態旅行時間下，撥召服務問題適之路線接受策略。經過例題求解比較發現，以新舊路線差異為新路線長度之20%作為接受門檻值之做法，其求解結果較為集中，是為較佳之排程策略。

關鍵字

撥召服務問題 ； 隨機性車輛路線問題 ； 基因演算法 ； 蟻群演算法

並列摘要

The Dial-a-Ride system can provide door-to-door and real-time service with the capacity of the traditional bus system. It is special transportation service for the handicapped citizen. The service usually is carried by the advanced order of passengers, and routing plan of service is scheduled based on these demands. The Dial-a-Ride Problem (DARP) is a vehicle routing problem for the arrangement of the Dial-a-Ride service.
The DARP has been proved to be a NP-Hard problem, therefore, most researches addressed this problem adopted heuristic methods as the solution methods. "Vertex Reinsertion" has been adopted by previous studies. Although, it is popular solution procedure, its computation efficiency is not impressed. With tremendous interest of the Meta-heuristics on the combinatorial problem, there is few study discuss its application on the DARP. The purpose of this study is to evaluation of the application of the Genetic Algorithm (GA) and the Ant Colony Optimization (ACO) on the DARP.
Two solution procedures are proposed in this study, i.e., an integrated approach and cluster first route second approach. A series of revised GA and ACO algorithms are developed for these two approaches. A series of case studies with different characteristics such as demand density, demand size were used to test the solution capability of the proposed algorithms. Based on the results of the case studies, the Diversity-controlling Adaptive Genetic Algorithm is identified as the best algorithm in solution quality, and the Ant Colony Optimization is proved to be able to solve the problem quickly.
In addition, the DARP with stochastic travel times has been test in the final part of the analysis. Different types of the decision criteria have been used to identify good decision criteria for the dynamic DARP. Based on the test results, threshold value is 20% of the difference of sum routing durations between new and old routing plans has been proven to be better decision criteria for the dynamic DARP.

並列關鍵字

Dial-and-Ride Problem ； Stochastic Vehicle Routing ； Ant Colony ； Genetic Algorithm

參考文獻

[18] 蘇昭銘與楊琮平，先進撥召公車營運管理系統之研究，中華管理學報，第一卷第一期，第89-114頁，民國八十九年。

[21] 陳家和與丁慶榮，應用螞蟻演算法於車輛途程問題之研究，中華民國運輸學會第18屆論文研討會，民國九十二年。

[2] M.W.P. Savelsbergh, The General Pickup and Delivery Problem, Transportation Science, vol.29 (1), p.17-29, 1995.

[3] Bernd Bullnheimer, Richard F. Hart and Cristine Strauss, An improved ant system algorithm for the vehicle routing problem, 1997.

[4] M.Dorigo and L.M. Gambardella, Ant colonies for the travelling salesman problem, BioSystems, vol.43, p.73-81, 1997.