臺灣博碩士論文加值系統

車輛路線巡迴問題求解的演算法設計常運用於物流相關產業之中，但以解決靜態問題與追求精確結果為目標所開發之演算方式，已不能滿足日益複雜的都市道路環境與多樣化的客戶需求，因此，如何利用最新的環境資訊來快速有效的產生動態的車輛路徑供企業或都市物流業者的配送部門作規劃，已必須被考慮進演算法的設計之中。
線上型車輛路線巡迴問題為接受未來有未知的資料產生並將其納入求解的程序之中，形成具動態特性且為NP-hard之問題，故在求解上將以啟發式演算法最為有效率，啟發式演算法為利用各種策略快速的取得近似最佳解，雖非全域最佳解，但求解全域最佳解所花費時間成本太過龐大，在實務操作上NP-hard之問題仍是以啟發式技術求解為主；而本研究以模擬自然運作法則與人類思考模式且具有跳脫局部最佳解能力的巨集式啟發式技術開發其線上型車輛路線巡迴問題求解演算法，並整合對於求解車輛路線巡迴問題表現優秀的禁制搜尋法與有良好區域搜尋機制的遺傳演算法形成混合型啟發式演算法。
為證實所開發之混合型啟發式演算法可應用於真實世界，將結合DynaTAIWAN交通模擬指派模式，運用高雄市真實路網道路幾何特性與即時交通資訊提供給演算法進行求解程序，並依結果修正各項參數，使其混合型啟發式演算法能產生在線上型車輛路線巡迴問題與物流配送規劃上一個高品質且具實用性的結果。

The algorithms for vehicle routing problems (VRPs) were applied to logistics industry, but the algorithms didn’t conform to the complicated traffic situations and varied customers’ demand for solved static problems and exact result. Therefore, designing the algorithm must be considering how to apply new information and quickly provide a dynamic vehicle routing for distribution division of firm and city logistics industry to plan.
The on-line VRPs would accept unknown data in the future and subsume the process, then the problems had dynamic characteristic and as NP-hard problems. Therefore, heuristic algorithm is the most effective for on-line VRPs. Heuristic algorithm used multiple strategies to acquire the approximate global optimal solution, the cost was a huge expense for acquire the global optimal solution, therefore solving NP-hard problems is still depending on heuristic algorithm for practical application. This research develops a heuristic algorithm for solving on-line VRPs. The heuristic algorithm is to simulate the laws of nature, thinking of humans and function of leaving local optimal solution, then integrate Tabu Search (TS) exceptional results for VRPs and Genetic Algorithms (GAs) fine function for local search transform into hybrid heuristic algorithm.
To confirm the hybrid heuristic algorithm for operation of real world is an applicable algorithm, then combine the algorithm with DynaTAIWAN simulation software to supply the information of the geometric characterization of network and real time traffic information of Kaohsiung City, then correct the parameters of algorithm to produce a high quality and applied solution for solving on-line VRPs by hybrid heuristic algorithm to supply logistics.

第一章 緒論 1
1.1 研究背景與動機 1
1.2 研究目的 2
1.3 研究範圍 3
1.4 研究流程 3
第二章 文獻回顧 6
2.1 車輛路線巡迴問題 6
2.1.1 車輛路線巡迴問題之特性 6
2.1.2 離線型車輛路線巡迴問題的求解方式 7
2.1.3 線上型車輛路線巡迴問題的求解方式 9
2.1.4 車輛路線巡迴問題於都市物流之應用 12
2.2 禁制搜尋法 14
2.2.1 禁制搜尋法的發展與應用 14
2.2.2 禁制搜尋法的演算流程 16
2.3 遺傳演算法 19
2.3.1 遺傳演算法的發展與應用 19
2.3.2 遺傳演算法的演算流程 20
2.4 混合型啟發式技術的發展 23
2.5 VRP啟發式演算法演算績效評估方法 25
2.5.1 題庫競賽法 25
2.5.2 演算法競賽 26
2.5.3 參數調整法 27
2.5.4 競爭比法 28
2.6 動態交通模擬指派模式DynaTAIWAN 30
2.7 小結 33
第三章 研究方法 34
3.1 問題描述與假設 34
3.2 研究架構 37
3.3 演算法設計與求解流程 39
3.3.1 解結構設計 39
3.3.2 離線最佳化車輛指派 41
3.3.3 線上路線更新改善 41
3.4 初始指派路徑建構演算法 41
3.5 混合型啟發式路線更新演算法 48
3.5.1 基因編碼與適合度 48
3.5.2 子代染色體生成程序 49
3.5.3 候選清單設計 52
3.5.4 混合型啟發式路線更新演算流程 52
3.6 Floyd-Warshall algorithm 55
3.7 小結 56
第四章 演算架構測試與路網說明 57
4.1 演算架構 57
4.2 實驗路網與測試問題說明 63
4.2.1 實驗路網資料 63
4.2.2 測試問題與環境 64
4.3 離線數學模式求解測試 67
4.4 線上演算法求解測試 70
4.4.1 基礎實驗參數與結果說明 71
4.4.2 候選清單長度敏感性分析 73
4.4.3 突變率敏感性分析 76
4.4.4 淘汰週期敏感性分析 79
4.4.5 線上遺傳演算求解測試 81
4.5 實驗結果分析 83
4.6 小結 88
第五章 線上更新演算實驗與結果分析 89
5.1 實驗設計 89
5.2 線上混合型啟發式演算法實驗 91
5.2.1 所有需求皆已知演算實驗 91
5.2.2 80%已知需求演算實驗 92
5.2.3 60%已知需求演算實驗 94
5.2.4 40%已知需求演算實驗 97
5.2.5 20%已知需求演算實驗 99
5.2.6 所有需求皆未知演算實驗 102
5.3 實驗結果分析 103
5.4 小結 109
第六章 結論與建議 110
6.1 結論 110
6.2 建議 112
參考文獻 114
附錄一 更新頻率實驗編號與情境整理表 118
附錄二 更新頻率實驗演算績效指標數值表 125

毛皖亭 (2007)，線上動態車輛巡迴路線演算法之發展：滾動平面法之應用，國立成功大學交通管理科學系碩士論文。
林志鴻 (2005)，宅配業車輛路線規劃問題之模式建立與求解，運輸學刊，第十七卷，第一期，頁65~頁94。
胡大瀛等人 (2003)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統，交通部運輸研究所。
胡大瀛等人 (2004)，區域級智慧型運輸系統示範計畫－核心交通分析與預測系統(第一年期)，交通部運輸研究所。
胡大瀛等人 (2008)，即時動態交通分析與預測模型 (DynaTAIWAN) 之實證分析與推廣(1/3)，交通部運輸研究所。
胡大瀛等人 (2008)，即時動態交通分析與預測模型 (DynaTAIWAN) 之實證分析與推廣(2/3)，交通部運輸研究所。
張清濱 (2008)，動態車輛路線巡迴問題之數學模式建構與分析，國立成功大學交通管理科學系碩士論文。
梅明德、謝浩明 (2001)，時窗限制動態車輛路線問題之線上型路線建立啟發式解法，運輸學刊，第十三卷，第二期，頁73~頁111。
郭蕙瑜 (2010)，動態旅行維修員問題之研究－以號誌維修為例，國立成功大學交通管理科學系碩士論文。
馮正民、邱裕鈞 (2004)，研究分析方法，建都文化事業股份有限公司。
Ball, M. O., Magnanti, T. L., Monma, C. L., and Nemhauser, G. L. (1995), Network Routing. In Handbooks in Operations Research and Management Science, Vol. 8, North-Holland: Netherlands.
Bäck, T. (1996), Evolutionary Algorithms in Theory and Practice, Oxford University Press, New York.
Bodin, L., Golden, B., Assad, A. and Ball, M. (1983), “Routing and Scheduling of Vehicles and Crews,” Computers and Operations Research, Vol. 10, pp. 63-211.
Buhrkal, K., Larsen, A. and Ropke, S. (2012), “The Waste Collection Vehicle Routing Problem with Time Windows in a City Logistics Context,” Procedia - Social and Behavioral Sciences, Vol. 39, pp. 241-254.
Christofides, N., Mingozzi, A. and Toth, P. (1979), “The Vehicle Routing Problem”, in Christofides N., Mingozzi, A., Toth, P. and Sandi, C. (eds), Combinatorial Optimization, Wiley, Chichester 315-338.
Ehmke, J. F. (2012), “Integration of Information and Optimization Models for Routing in City Logistics,” International Series in Operations Research & Management Science, Vol. 177.
Ehmke, J. F., Steinert, A. and Mattfeld, D. C. (2012), “Advanced routing for city logistics service providers based on time-dependent travel times,” Journal of Computational Science, Vol. 3, Iss. 4, pp. 193-205.
Fink, I., Krumke, S. O., and Westphal, S. (2009), “New lower bounds for online k-server routing problems,” Information Processing Letters, Vol. 109, pp. 563-567.
Fisher, M.L. (1995), “Vehicle Routing,” Chapter 1 in M. Ball, T. Magnanti, C. Momma, and G. Nemhauser (eds) Network Routing, Handbooks in Operations Research and Management Science 8, pp. 1-33.
Fleischmann, B., Gnutzmann, S., and Sandvoß, E. (2004), “Dynamic Vehicle Routing Based on On-Line Traffic Information,” Transportation Science, Vol. 38, No. 4, pp. 420-433.
Fu, Z., Eglese, R., and Li, L. Y. O. (2008), “A unified tabu search algorithm for vehicle routing problems with soft time windows,” Journal of the Operational Research Society, Vol. 59, pp. 663-673.
Garey, M. R., and Johnson, D.S. (1979), Computers and Intracta-bility: A Guide to the Theory of NP-Completeness, Freeman, San Francisco.
Ghiani, G., Guerriero, F., Laporte, G. and Musmanno, R. (2003), “Real-time vehicle routing: Solution concepts, algorithms and parallel computing strategies,” European Journal of Operational Research, Vol. 151, No. 1, pp. 1-11.
Glover, F. (1977), “Heuristic for Integer Programming Using Surrogate Constraints,” Decision Science, Vol. 8, pp. 156-166.
Glover, F. (1986), “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, Vol. 13, Iss. 5, pp. 533-549.
Glover, F. (1989), “Tabu Search-Part I,” ORSA Journal on Computing, Vol. 1, No. 3, pp. 190-206.
Glover, F., Kelly, J. P., and Laguna, M. (1995), “Genetic algorithms and tabu search: Hybrids for optimization,” Computers & Operations Research, Vol. 22, Iss. 1, pp. 111-134.
Golden, B. L., Magnanti, T. L., and Nguyen, H. Q. (1977), “Implement Vehicle Routing Algorithms,” Networks, Vol. 7, pp. 113-148.
Holland, J. H. (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, MI.
Horn, M. E. T. (2006), “On-Line Vehicle Routing and Scheduling With Time-Varying Travel Speeds,” Journal of Intelligent Transportation Systems, Vol. 10, Iss. 1, pp. 33-40.
Jaillet, P., and Wagner, M. R. (2008), “Online Vehicle Routing Problems: A Survey,” The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 221-237.
Jaillet, P. and Wagner, M. R. (2008), “Generalized Online Routing: New Competitive Ratios, Resource Augmentation, and Asymptotic Analyses,” Operations Research, Vol. 56, No. 3, pp. 745-757.
Karlin, A., Manasse, M., Rudolph, L., and Sleator, D. (1988), “Competitive snoopy catching,” Algorithmica, Vol. 3, No. 1, pp. 79-119.
Krumke, S., Paepe, W., Poensgen, D., and Stougie, L. (2003), “News from the online traveling repairman,” Theoretical Computer Science, Vol. 295, Iss. 1-3, pp. 279-294.
Ma, W., Dong, D., and Wang, K. (2010), “Competitive Analysis for the On-Line Vehicle,” New Trends in Information Science and Service Science, Iss. 11-13, pp. 430-435.
Mauri, G. R. and Lorena, L. A. N. (2006), “A new hybrid heuristic for driver scheduling,” International Journal of Hybrid Intelligent Systems.
Malandraki, C. and Daskin, M. S. (1992), “Time Dependent Vehicle Routing Problems: Formulations, Properties and Heuristic Algorithms,” Transportation Science, Vol. 26, pp.185-199.
Prins, C. (2004), “A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 31, Iss. 12, pp.1985-2002.
Ribeiro, C. C., Noronha, T. F., Rocha, C. and Urrutia, S. (2005), “A Heuristic for a Real-Life Car Sequencing Problem with Multiple Requirements,” Sixth Metaheuristics International Conference, Vienne, Austria.
Sleator, D. D. and Tarjan, R. E. (1985), “Amortized efficiency of list update and paging rules,” Communications of the ACM, Vol. 28, Iss. 2, pp. 202-208.
Solomon, M. M. (1987), “Algorithms for the Vehicle Routing and Scheduling Problems with Time Window Constraints,” Operations Research, Vol. 35, No. 2, pp. 254-265.
Taniguchi, E., Thompson, R. G., Yamade, T. and Duin, R. V. (2001), City logistics: network modeling and intelligent transport system, Oxford: Elsevier Science Ltd.
Ting, C. K., Li, S. T. and Lee, C. (2001), “TGA: A New Integrated Approach to Evolutionary Algorithms,” Proceedings of the IEEE 2001 Congress on Evolutionary Computation, Korea, 2001, Vol. 2, pp. 917 -924.
van Hemert, J. I., and La Poutre, J. A. (2004), “Dynamic Routing Problems with Fruitful Regions: Models and Evolutionary Computation,” Parallel Problem Solvers from Nature VIII, pp. 690-699.
Vehicle Routing and Travelling Salesperson Problems. (2002, March 20), Norwegian: Stiftelsen for industriell og teknisk forskning (SINTEF). Retrieved October 16, 2009, from the World Wide Web: http://www.top.sintef.no/vrp/index.html
Yurtkuran, A., and Emel, E. (2010), “A new Hybrid Electromagnetism-like Algorithm for capacitated vehicle routing problems,” Expert Systems with Applications, Vol. 37, Iss. 4, pp. 3427-3433.