以混合演化式演算法求解多目標且具時窗限制之車輛路由問題

A Hybrid Multiobjective Evolutionary Algorithm for the Vehicle Routing Problem with Time Windows

許巍懷

指導教授 ： 蔣宗哲

國立臺灣師範大學/理學院/資訊工程研究所/碩士(2011年)

摘要

車輛路由問題旨在尋求車輛與客戶之間最佳分配與移動路線，在已知客戶需求 (如運送量和服務時窗限制) 和車輛容量的情況下，由派車站發車前往服務客戶，最後返回派車站。車輛路由問題在實務上已有廣泛應用，如物品宅配、校車動線、計程車載客、銀行運鈔車補給、郵務信件遞送等等。
本論文以具時窗限制之車輛路由問題為主題，其求解目標為最小化車輛數和總行駛距離，由柏拉圖最佳化觀點求解，提出一混合基因演算法和禁忌搜尋的求解方法。初始解經由禁忌搜尋將目標專於車輛數目最小化，再由基因演算法以多目標進行最佳化。並以改良式的交配和突變策略增加解的品質；在演化一定代數後由禁忌搜尋法對族群中非凌越解集進行深度搜尋以最小化行駛距離。
測試問題集是Solomon建立的6大類共56個問題。本研究以多目標求解問題，對於文獻所提出的67個近似最佳解集合更新了34個，另外有2大類的問題可以達到車輛數與總距離的最佳解。

關鍵字

基因演算法 ； 禁忌搜尋法 ； 時窗車輛路由問題 ； 多目標最佳化

參考文獻

[1] B. M. Baker, M. A. Ayechew, “A genetic algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 30, pp. 787–800, 2003.

[2] C. Prins, “A simple and effective evolutionary algorithm for the vehicle routing problem,” Computers & Operations Research, vol. 31, pp. 1985–2002, 2004.

[3] K. C. Tan, L. H. Lee, Q. L. Zhu, and K. Ou, “Heuristic methods for vehicle routing problem with time windows,” Artificial Intelligence in Engineering, vol. 15, pp. 281–295, 2001.

[4] M. M. Solomon, “Algorithms for the vehicle routing and scheduling problem,” Operations Research Society of America, vol. 35, no. 2, pp. 254－265, 1987.

[5] S. R. Balseiro, I. Loiseau, J. Ramonet, “An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows,” Computer & Operations Research, vol. 38, pp. 954－966, 2011.