混合式螞蟻演算法解容量限制車輛途程問題

A Hybrid ACO Algorithm for Capacitated Vehicle Routing Problems

黃翊婷(Yi-Ting Huang)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2012年)

摘要

車輛途程問題是有名的組合最佳化問題，而此問題已經被研究數十年，因有效地找出車輛途程在物流管理是很重要的議題．本論文提出一新的混合演算法，其基於螞蟻演算法與粒子演算法此兩種群體智慧方法，解容量限制車輛途程問題。在提出的演算法中，每一隻螞蟻就像粒子演算法中的粒子，能夠記住曾經找到最好的解，並於解建構完成後，只有菁英螞蟻可根據自己目前為止記憶中的最佳解更新費洛蒙。然而，費洛蒙干擾方法被嵌入於螞蟻演算法架構中，其為了克服費洛蒙停滯的問題。最後，我們選擇兩組標準題庫來測試所提出的演算法效能，而計算結果顯示出本演算法相較於其他現有的群體智慧方法，其效果良好。

關鍵字

粒子演算法 ； 螞蟻演算法 ； 車輛途程問題 ； 群體智慧

並列摘要

The vehicle routing problem (VRP) is a well-known combinatorial optimization problem. It has been studied for several decades because finding effective vehicle routes is an important issue of logistic management. This paper proposes a new hybrid algorithm based on two main swarm intelligence (SI) approaches, ant colony optimization (ACO) and particle swarm optimization (PSO), for solving capacitated vehicle routing problems (CVRP). In the proposed algorithm, each artificial ant, like a particle in PSO, is allowed to memorize the best solution ever found. After solution construction, only elite ants can update pheromone according to their own best-so-far solutions. Moreover, a pheromone disturbance method is embedded into the ACO framework to overcome the problem of pheromone stagnation. Two sets of benchmark problems were selected to test the performance of the proposed algorithm. The computational results show that the proposed algorithm performs well in comparison with existing swarm intelligence approaches.

並列關鍵字

vehicle routing problems ； particle swarm optimization ； swarm intelligence ； ant colony optimization

參考文獻

[1] G. Laporte, “The vehicle routing problem: an overview of exact and approximate algorithms,” European Journal of Operational Research, vol. 59, no. 3, pp. 345-358, 1992.

[2] I. H. Osman, “Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem,” Annals of Operations Research, vol. 41, no. 4, pp. 421-451, 1993.

[4] J. K. Lenstra1 and A. H. G. Rinnooy Kan, “Complexity of vehicle routing and scheduling problems,” Networks, vol. 11, no. 2, pp. 221-228, 1981.

[5] G. Barbarosoglu and D. Ozgur, “A tabu search algorithm for the vehicle routing problem,” Computers & Operations Research, vol 26, no. 3, pp. 255-270, 1999.

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