撥召服務系統具有傳統公車系統之服務容量並能提供高度之及門性與即時性，因此除了一般載客之外常被用以服務行動不便者，例如老年人、病患與身心障礙者等。其服務方式須由顧客先行預約，再透過系統將數筆預約進行路線排程。撥召服務問題即為求解此一型式之運輸系統路線排程之車輛繞徑問題。 在問題之求解上，諸多研究皆使用節點再插入法(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.
