楊烽正臺灣大學：工業工程學研究所陳俊傑Chen, Chun-ChiehChun-ChiehChen2007-11-262018-06-292007-11-262018-06-292004http://ntur.lib.ntu.edu.tw//handle/246246/51255本研究以蟻拓尋優法(Ant Colony Optimization, ACO)為基提出「ACO分排同步」和「ACO整併」優化模式來求解車輛途程問題(Vehicle Routing Problem, VRP)。一般組合問題常見可模式化為順序問題(sequencing problem)與分群問題(clustering problem)，而VRP則同時兼具順序(決定路徑順序)與分群(顧客分群)屬性。過往研究，泰半將VRP模式化成順序問題，本研究提示的模式則以分群模式為主。此外，本研究提示了一個衍生自K-means的顧客分群法，名為P-K-means。P-K-means是一個以極座標為基的分群法，主要弁酮O先嘗試將顧客分群以決定出種子顧客。種子顧客的設定會引導螞蟻進行顧客分車演算。因種子顧客初期的分散特性最後能得到較佳的分群結果。 本研究並以文獻上的14題標竿問題進行測試，並和其他ACO求解VRP的求解結果比較以驗證模式的效用。結果顯示本研究提出的演算法在求解品質有明顯改善。We presented two ACO-based models to solve Vehicle Routing Problem (VRP) named “Composite ACO” and “Synchronized ACO”. Generally speaking, combination problems can be modeled to sequencing problems and clustering problems, but VRP combines both sequencing (to determine sequence of route) and clustering attributes. Besides, we also presented a clustering algorithm called P-K-means. P-K-means is a polar-coordinate based clustering algorithm, and its main task is to determine the seeds in advance. The function of the seeds are clustering the vehicles. By using the information of the seeds, we can obtain better clustering results. We also compare our algorithm with 14 benchmarks VRP problems, and the results show that our algorithms perform much better than the others.目 錄 I 圖目錄 IV 表目錄 VI 名詞匯編 VII 符號列表 IX 第1章 緒論 1 1.1 研究背景和動機 1 1.2 研究目的及內容 2 1.3 研究範疇與架構 3 1.4 章節概要 5 第2章 文獻探討 6 2.1 蟻拓尋優法 6 2.1.1 真實螞蟻覓食行為探討 6 2.1.2 蟻拓尋優法的演算過程 8 2.1.3 螞蟻系統 (Ant System) 9 2.1.4 和 14 2.1.5 螞蟻屯拓系統(ant colony system, ACS) 16 2.1.6 蟻拓尋優法的其他應用 18 2.2 車輛途程問題 20 2.2.1 車輛途程問題的常見求解法 20 2.3 蟻拓尋優法求解車輛途程問題 27 2.3.1 求解VRP 28 2.3.2 AS求解VRP 29 2.4 分群演算法 30 2.4.1 階層式分群法 31 2.4.2 非階層式分群法 32 2.4.3 分群方法比較 35 2.5 文獻探討結語 35 第3章 使用種子導引的蟻拓分群優化法求解車輛途程問題 36 3.1 過往蟻拓最佳化技術求解車輛途程問題的缺失 37 3.2 車輛途程問題模式及求解架構 41 3.2.1 車輛途程問題描述 41 3.2.2 車輛途程問題求解模式的求解系統架構 41 3.3 使用種子導引的蟻拓尋優法求解車輛途程問題 44 3.3.1 P-K-means演算法 44 3.3.2 ACO分排同步優化法求解車輛途程問題 59 3.3.3 整併ACO優化演算法(CACO)求解車輛途程問題 81 3.4 本研究和過往ACO最佳化技術比較 94 3.5 小結 94 第4章 演算法設計效能分析及範例驗證 95 4.1 演算法穩健性測試 95 4.1.1 小型範例問題測試 95 4.2 標竿題目測試 100 4.2.1 ACO分排同步優化法和其他以分群為基演算法比較 100 4.2.2 ACO分排同步優化法和其他螞蟻最佳化技術比較 105 4.2.3 ACO分排同步優化法與萬用啟發式方法比較 110 4.3 小結 112 第5章 結論與未來研究建議 113 5.1 結論 113 5.2 未來研究建議 113 參考文獻 114804435 bytesapplication/pdfen-USK-means車輛途程問題蟻拓尋優法P-K-meansant colony optimizationvehicle routing problemthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/51255/1/ntu-93-R91546015-1.pdf