[[alternative]]A study on the optimal assignment operation for the dial-and-ride problem

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