An Improved Ant Colony System Algorithm for the Vehicle Routing Problem

應用改良式群蟻系統演算法於車輛途程問題之研究

10.29977/JCIIE.200603.0003

陳家和(Chia-Ho Chen)；丁慶榮(Ching-Jung Ting)

車輛途程問題 ； 萬用啓發式演算法 ； 群蟻系統演算法 ； vehicle routing problem ； meta-heuristic ； ant colony system

工業工程學刊

23卷2期（2006 / 03 / 01）

115 - 126

英文

車輛途程問題(Vehicle Routing Problem; VRP)是近五十年來，一個非常著名的組合最佳化問題，過去已有許多學者針對VRP進行求解與探討。很多萬用啓發式演算法(Meta-heuristic)已被應用於求解VRP，如模擬退火法(Simulated Annealing; SA)、基因遺傳演算法(Genetic Algorithms; GA)、禁忌搜尋法(Tabu Search; TS)與螞蟻演算法(Ant Algorithm)等。其中，螞蟻演算法為90年代根據螞蟻族群搜尋食物的現象，所發展而成的萬用啓發式演算法。現今，已有越來越多的學者針對螞蟻演算法進行改良與修正，並應用於許多組合最佳化問題。因此，本研究提出一改良式的群蟻系統演算法(Ant Improved colony System, IACS)，其採用新的途程建構準則、費洛蒙(Pheromone)更新方式與多種區域搜尋法(Local Search)，以改善傳統螞蟻演算法求解VRP之品質。本研究求解14題VRP之標竿測試例題，並將求解結果與SA、GA、TS及其它已發表之螞蟻演算法進行比較。比較結果顯示，IACS之求解品質優於其它已發表之螞蟻演算法，且不遜於其它比較之萬用啓發式演算法。

The vehicle routing problem (VRP), a well-known combinatorial optimization problem, holds a central place in logistics management. Many meta-heuristic approaches like Simulated Annealing (SA), Genetic Algorithms (GA), Tabu Search (TS), and Ant Colony Optimization (ACO) have been proposed to solve VRP. Ant Algorithm is a distributed meta-heuristic approach that has been applied to various combinatorial optimization problems, including traveling salesman problem, quadratic assignment problem. In this research, we proposed an improved ant colony system (IACS) algorithm that possesses a new state transition rule, a new pheromone updating rule and diverse local search approaches. The computational results on 14 VRP benchmark problems show that our IACS yields better solutions than those of other ant algorithms in the literature and is competitive with other meta-heuristic approaches in terms of solution quality.

1. Alfa, A. S.,S. S. Heragu,M. Chen(1991).A 3-opt based simulated annealing algorithm for vehicle routing problems.Computers & Industrial Engineering,21,635-639.
2. Baker, B. M.,M. A. Ayechew(2003).A genetic algorithm for the vehicle routing problem.Computers & Operations Research,30,787-800.
3. Bullnheimer, B.,R. F. Hartl,C. Strauss(1999).A New Rank Based Version of the Ant System - A Computational Study.Central European Journal of Operations Research,7,25-38.
4. Bullnheimer, B.,R. F. Hartl,C. Strauss(1999).An improved ant system for the vehicle routing problem.Annals of Operations Research,89,319-328.
5. Bullnheimer, B.,R. F. Hartl,C. Strauss,S. Voss,S. Martello,I.H. Osman,C. Roucairol(1998).Applying the ant system to the vehicle routing problem.Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization,109-120.
6. Christofides, N.,A. Mingozzi,P. Toth,N. Christofides,A. Mingozzi,P. Toth,C. Sandi.(1979).The Vehicle Routing Problem.Combinatorial Optimization
7. Colorni A.,M. Dorigo,F. Maffioli,V. Maniezzo,G. Righini,M. Trubian(1996).Heuristics from nature for hard combinatorial problems.International Transactions in Operational Research,3(1),1-21.
8. Colorni, A.,M. Dorigo,V. Maniezzo,F. Varela,P. Bourgine(1991).Distributed optimization by ant colonies.Proceeding of the European Conference on Artificial Life
9. Colorni, A.,M. Dorigo,V. Maniezzo,M. Trubian(1994).Ant system for job-shop scheduling.Belgian Journal of Operations Research, Statistics and Computer Science,34(1),39-53.
10. Costa, D,A. Hertz(1997).Ants can colour graphs.Journal of the Operational Research Society,48,295-305.
11. Dorigo, M.,L. M. Gambardella(1997).Ant colonies for the traveling salesman problem.BioSystems,43,73-81.
12. Dorigo, M.,L. M. Gambardella(1997).Ant colony system: A cooperative learning approach for the traveling salesman problem.IEEE Transactions on Evolutionary Computation,1,53-66.
13. Dorigo, M.,V. Maniezzo,A. Colorni(1996).Ant system: Optimization by a colony of cooperating agents.IEEE Transactions on Systems,29(41)
14. Gambardella, L. M.,E. Taillard,G. Agazzi,D. Corne,M. Dorigo,F. Glover(1999).MACS-VRPTW: A multiple ant colony system for vehicle routing problems with time windows.New ideas in optimization
15. Gambardella, L. M.,E. Taillard,G. Agazzi,D. Corne,M. Dorigo,F. Glover(1999).Ant colonies for vehicle routing problems.New Ideas in Optimization
16. Gambardella, L. M.,E. Taillard,M. Dorigo(1999).Ant colonies for the quadratic assignment problem.Journal of the Operational Research Society,50,167-176.
17. Gambardella, L. M.,M. Dorigo(1997).HAS-SOP: A hybrid ant system for the sequential ordering problem.Tech. Rep. No. IDSIA 97-11
18. Garey, M. R.,D. S. Johnson(1979).Computers and Intractability: A Guide to the Theorey of NP completeness.
19. Gendreau, M.,A. Hertz,G. Laporte(1994).A tabu search heuristic for the vehicle routing problem.Management Science,40,1276-1290.
20. Ghaziri, H.,I. Osman,J. Kelly(1996).Supervision in the self-organizing feature map: application to the vehicle routing problem.Meta-heuristics: Theory & Application,651-660.
21. Golden, B. L.,E. A. Wasil,J. P. Kelly,I-M. Chao,T. G. Crainic,G. Laporte(1998).Metaheuristic in vehicle routing.Fleet Management and Logistics,33-56.
22. Hadjiconstantinou, E.,N. Christofides,A. Mingozzi,Gendreau,G. Laporte(1995).A new exact algorithm for the vehicle routing problem based on q-paths and k-shortest paths relaxations.Freight Transportation,21-43.
23. Jaszkiewicz, A.,P. Kominek(2003).Genetic local search with distance preserving recombination operator for a vehicle routing problem.European Journal of Opera tional Research,151,352-364.
24. Lin, S.(1965).Computer solution of the traveling salesman problem.Bell System Computer Journal,44,2245-2269.
25. Maniezzo, V.,A. Colorni,M. Dorigo(1994).The ant system applied to the quadratic assignment problem.Tech. Rep. IRIDIA/94-28
26. Osman, I. H.(1993).Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem.Annals of Operations Research,41,421-451.
27. Robuste, F.,C. F. Daganzo,R. Souleyrette(1990).Implementing vehicle routing models.Transportation Research B,24,263-586.
28. Rochat, Y.,E. Taillard(1995).Probabilistic and intensification in local search for vehicle routing.Journal of Heuristics,1,147-167.
29. Stützle, T.,M. Dorigo,D. Corne,M. Dorigo,F. Glover(1999).ACO algorithms for the quadratic assignment problem.New Ideas in Optimization,33-50.
30. Su, C. T.,H. H. Chen(1999).Vehicle routing design of physical distribution center.Journal of the Chinese Institute of Industrial Engineers,16(3),405-417.
31. Taillard, E.(1993).Parallel iterative search methods for vehicle routing problems.Networks,23,661-673.
32. Talbi, E. G.,O. Roux,C. Fonlupt,D. Robillard(2001).Parallel ant colonies for the quadratic assignment problem.Future Generation Computer Systems,17(4),441-449.
33. Van Breedam, A.(1995).Improvement heuristics for the vehicle routing problem based on simulated annealing.European Journal of Operational Research,86,480-490.
34. Xu, J.,J. P. Kelly(1996).A network flow-based tabu search heuristic for the vehicle routing problem.Transportation Science,30,379-393.

1. 陳冠宇,丁慶榮(2021)。以蟻群最佳化演算法求解動態車輛途程問題。運輸學刊，33(2)，135-163。
2. 陳家和、丁慶榮(2007)。應用二階段蟻群演算法求解P-中位問題之研究。運輸學刊，19(4)，383-404。
3. 盧宗成、喻奉天、林宗漢(2011)。應用蟻群系統求解卡車與拖車途程問題。運輸學刊，23(2)，199-218。
4. (2006)。智慧型財富管理決策模式之研究—應用人工智慧方法。朝陽商管評論，5(特刊)，25-44。
5. (2011).Ant colony optimization for railway driver crew scheduling: from modeling to implementation.工業工程學刊,28(6),437-449.
6. (2013).A hybrid heuristic method for the fleet size and mix vehicle routing problem.工業工程學刊,30(3),181-189.
7. (2018).Collaborative transportation planning distinguishing old and new shippers for small-medium enterprise.工業工程學刊,35(3),170-180.
8. (2022).Logistics distribution scheduling model of supply chain based on genetic algorithm.工業工程學刊,39(2),83-88.