使用種子導引的蟻拓分群優化法求解車輛途程問題

A Seed-Guided Ant Colony Optimization Method for Capacitated Vehicle Routing Problem

陳俊傑(Chun-Chieh Chen)

指導教授 ： 楊烽正

國立臺灣大學/工學院/工業工程學研究所/碩士(2004年)

https://doi.org/10.6342/NTU.2004.00687

摘要

本研究以蟻拓尋優法(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的求解結果比較以驗證模式的效用。結果顯示本研究提出的演算法在求解品質有明顯改善。

關鍵字

K-means ； 車輛途程問題 ； 蟻拓尋優法 ； P-K-means

並列摘要

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.

並列關鍵字

ant colony optimization ； P-K-means ； vehicle routing problem ； K-means

參考文獻

Clarke, C. and Wright, J., “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points,” Operations Research, v 12, 1964, pp. 568-581.

Dorigo, M., and Caro, G., 1999, “The Ant Colony Optimization Meta-Heuristic,” New Ideas in Optimization, McGraw-Hill, pp. 11-32.

Dorigo, M., and Gambardella, L. M., 1997, “Ant Colony System: A cooperative Learning Approach to the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, vol.1, no.1, pp. 53-66.

Fisher, M. L., and Jaikumar, R., 1981, "A Generalized Assignment Heuristic for Vehicle Routing". Networks, pp. 109-124.

Hölldobler, B., and Wilson, E. O., 1995, Journey to the Ants: A Story of Scientific Exploration, Belknap printing, reprint edition.