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

中文摘要
英文摘要
誌謝
目錄I
圖目錄V
表目錄IV
第一章　序論1
1.1研究動機1
1.2研究目的2
1.3研究範圍3
1.4研究架構及流程4
1.5章節配置6
第二章　文獻回顧7
2.1撥召服務問題7
2.1.1撥召服務7
2.1.2撥召服務問題8
2.2基因演算法12
2.2.1基因演算法概述12
2.2.2基因演算法相關研究應用13
2.3蟻群演算法14
2.3.1蟻群演算法概述14
2.3.2蟻群演算法相關研究應用15
2.4小結16
第三章　模式探討17
3.1撥召服務問題描述17
3.2基本假設18
3.3模式構建19
3.3.1符號介紹20
3.3.2數學模式21
3.4小結24
第四章　求解策略25
4.1繞徑策略25
4.2求解流程28
4.2.1完整一階段流程28
4.2.2分群繞徑二階段流程30
4.3演算法設計32
4.3.1適應性基因演算法32
4.3.2族群競爭式基因演算法37
4.3.3蟻群演算法39
4.4小結43
第五章　案例測試44
5.1求解能力44
5.2參數設定46
5.2.1適應性基因演算法57
5.2.2族群競爭基因演算法50
5.2.3蟻群演算法54
5.2.4參數一覽58
5.3模式參數58
5.3.1路線最大長度59
5.3.2最大乘車時間60
5.4結果比較61
5.4.1小型問題pr1結果比較62
5.4.2大型問題pr5結果比較63
5.4.3文獻結果比較64
5.5小結68
第六章 隨機旅行時間問題分析67
6.1動態旅行時間68
6.1.1旅行時間之計算68
6.1.2旅行時間統計分配假設69
6.1.3亂數產生之方法70
6.2撥召服務路線排程策略70
6.2.1路線之重新排程70
6.2.2排程接受策略71
6.3策略比較73
6.3.1測試結果分析73
6.3.2測試結果小結75
第七章　結論與建議76
7.1 結論76
7.2 建議77
參考文獻79
附錄 求解結果表
 
圖目錄
圖1-1 研究流程圖4
圖2-1 撥召服務路徑排程示意圖8
圖3-1 花型路線示意圖18
圖4-1 車輛於各節點之到達時間、停等時間、開始服務時間與離開時間示意圖25
圖4-2 不同到達與離開策略比較圖26
圖4-3 完整一階段求解流程圖29
圖4-4 分群繞徑二階段求解流程圖30
圖4-5 適應性基因演算法求解流程圖33
圖4-6 基因演算法起始解產生方式34
圖4-7 Uniform交配示意圖34
圖4-8 不同求解流程基因演算法染色體編碼示意圖36
圖4-9 族群競爭基因演算法示意圖37
圖4-10 族群競爭基因演算法求解流程圖38
圖4-11 蟻群演算法螞蟻構建路線示意圖39
圖4-12 蟻群演算法求解流程圖40
圖4-13 完整一階段候選名單編排示意圖41
圖5-1 簡單問題之需求狀況與最佳繞徑圖45
圖5-2 適應性基因演算法、族群競爭式基因演算法與蟻群演算法簡單問題求解結果分佈46
圖5-3 適應性基因演算法各族群數求解結果分布48
圖5-4 適應性基因演算法各迭代數求解結果分布49
圖5-5 族群競爭基因演算法各迭代數求解結果分布50
圖5-6 族群競爭基因演算法各迭代數求解結果分布51
圖5-7 族群競爭基因演算法各迭代數求解結果分布52
圖5-8 族群競爭基因演算法各基因樣板保留率求解結果分布53
圖5-9 蟻群演算法螞蟻隻數求解結果分布55
圖5-10 蟻群演算法螞蟻隻數求解結果分布56
圖5-11 蟻群演算法費洛蒙起始濃度求解結果分布57
圖5-12 路線長度違反成本起始值設定求解結果分布59
圖5-13 路線長度違反成本起始值設定求解結果分布60
圖6-1 隨機旅行時間問題決策流程67
圖6-2 動態旅行時間路線排程處理流程71
圖6-3 門檻值百分比測試結果分佈圖72
圖6-4 不同求解策略旅行時間分布75
 
表目錄
表2-1 撥召公車問題相關文獻彙總表11
表4-1 移除與重劃步驟示意35
表5-1 簡單問題節點設定44
表5-2 簡單問題最佳繞徑排程45
表5-3 簡單問題各演算法求解結果46
表5-4 適應性基因演算法調整參數範圍表47
表5-5 適應性基因演算法各參數設定表47
表5-6 適應性基因演算法族群大小比較表48
表5-7 適應性基因演算法迭代數比較表49
表5-8 適應性基因演算法調整參數範圍表50
表5-9 族群競爭式基因演算法族群大小比較表50
表5-10 族群競爭基因演算法迭代數比較表51
表5-11 族群競爭基因演算法突變率比較表52
表5-12 族群競爭基因演算法基因樣板保留率比較表53
表5-13 蟻群演算法調整參數範圍表54
表5-14 蟻群演算法各參數設定表54
表5-15 蟻群演算法螞蟻隻數比較表55
表5-16 蟻群演算法迭代數比較表56
表5-17 蟻群演算法費洛蒙起始濃度比較表57
表5-18 各演算法參數比較結果58
表5-19 路線長度違反成本起始值設定比較表59
表5-20 乘車時間違反成本起始值設定比較表60
表5-21 結果分析選用例題規模61
表5-22 小型問題總路線長度各分組t檢定結果比較62
表5-23 小型問題總路線長度整體t檢定結果比較62
表5-24 大型問題總路線長度各分組t檢定結果比較63
表5-25 大型問題總路線長度整體t檢定結果比較63
表5-26 例題pr1結果表64
表5-27 例題pr5結果表65
表6-1 門檻值百分比測試結果72
表6-2 門檻值t檢定成對比較結果73
表6-3 不同策略解集合範圍74
表6-4 不同策略t檢定結果74
表6-5 不同策略F檢定結果74

[1]	M. Dorigo, V. Maniezzo and A. Colorny, Ant System: An Autocatalytic Optimizing Process, 1991, Technical Report, p.91-016, Politecnico di Milano, Italy, 1991.
[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.
[5]	Toth P and Vigo D, Heuristic algorithms for the handicapped persons transportation problem. Transportation Science, vol.31, p.60-71, 1997.
[6]	Marco Dorigo and Gianni Di Caro, The Ant Colony Optimization Meta-Heuristic, New Ideas in Optimization, 1999.
[7]	Dusan Teodorovic and Gordana Radivojevic, A fuzzy logic approach to dynamic Dial-A-Ride problem, Fuzzy Sets and Systems 116 p.23-33, 2000.
[8]	Karl Doerner, Manfred Gronalt, Richard F. Hartl, Marc Reimann, Christine Strauss and Michael Stummer, SavingsAnts for the Vehicle Routing Problem, Vienna University of Economics and Business Administration, December, 2001.
[9]	Jean-François Cordeau and Gilbert Laporte, A tabu search heuristic for the static multi-vehicle dial-a-ride problem, Transportation Research Part B 37 p.579–594, 2003.
[10]	Jean-François Cordeau and Gilbert Laporte, The Dial-a-Ride Problem (DARP):Variants, modeling issues and algorithms, French and Italian Operations Research Societies 1 p.89-101,2003.
[11]	Kenny Q. Zhu, A Diversity-controlling Adaptive Genetic Algorithm for the Vehicle Routing Problem with Time Windows, Department of Computer Science, National University of Singapore, 2003.
[12]	Kenny Q. Zhu, Population Diversity in Genetic Algorithm for Vehicle Routing Problem with Time Windows, Department of Computer Science, National University of Singapore, 2003.
[13]	Andrea Attanasio, Jean-François Cordeau, Gianpaolo Ghiani and Gilbert Laporte,Parallel Tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem, Parallel Computing 30 p.377–387,2004.
[14]	K.B. Bergvinsdottir, The Genetic Algorithm for solving the Dial-a-Ride Problem, Kgs. Lyngby, 2004.
[15]	Marco Diana and Maged M. Dessouky, A new regret insertion heuristic for solving large-scale dial-a-ride problems with time windows, Transportation Research Part B 38 p.539–557, 2004.
[16]	P.S. Shelokar, V.K. Jayaraman and B.D. Kulkarni, An ant colony approach for clustering, Analytica Chimica Acta, 509, p.187-195, 2004.
[17]	游進俊，靜態撥召服務問題啟發式解法之研究，國立交通大學土木工程研究所，民國八十二年。
[18]	蘇昭銘與楊琮平，先進撥召公車營運管理系統之研究，中華管理學報，第一卷第一期，第89-114頁，民國八十九年。
[19]	張世峰，即時行車資訊下物流配送作業規劃之研究，淡江大學運輸管理學系運輸科學碩士班碩士論文，民國九十一年六月。
[20]	邱裕鈞、馮正民與朱文正，考量旅行時間可靠度之車輛途程問題－螞蟻族群演算法之應用，中華民國運輸學會第18屆論文研討會，民國九十二年。
[21]	陳家和與丁慶榮，應用螞蟻演算法於車輛途程問題之研究，中華民國運輸學會第18屆論文研討會，民國九十二年。
[22]	曾惠鈺，即時行車資訊下物流配送作業規劃之研究，淡江大學運輸管理學系運輸科學碩士班碩士論文，民國九十二年六月。
[23]	紀婉容與許永真，以族群競爭式基因演算法解決具有次序及時間限制的載運路徑規劃問題，台大工程學刊第九十期第89-98頁，民國九十三年二月。
[24]	林典翰與楊烽正，優加劣減螞蟻擇段系統應用於零工式生產排程問題，第一屆台灣作業研究學會學術研討會暨2004年科技與管理學術研討會，民國九十五年。