An Ant Colony Approach to the Orienteering Problem

利用蟻群演算法求解越野賽跑問題

10.29977/JCIIE.200609.0005

梁韵嘉(Yun-Chia Liang)；Alice E. Smith

蟻群 ； 越野賽跑問題 ； 旅行推銷員問題 ； 途程 ； 最佳化 ； ant colony ； orienteering problem ； traveling salesman problem ； routing ； optimization

工業工程學刊

23卷5期（2006 / 09 / 01）

403 - 414

英文

本研究發展一蟻群最佳化演算法求解越野賽跑問題，此問題可被視為一廣義之旅行推銷員問題，其應用範圍極為廣泛。本演算法依據蟻群最佳化之精神建構，並加入一順序性局部搜尋程序及以距離為考量之懲罰函數為輔助機制。在六十七個測試例題的結果顯示本蟻群演算法僅需極短的運算時間即能與文獻中其他方法表現相同或是略勝一籌。除此之外，本方法之表現不受亂數種子、測試例題大小及限制程度改變而有所影響，因此本研究所提出之蟻群最佳化演算法可被視為求解此類問題之最佳方法。

This paper develops an ant colony optimization approach to the orienteering problem, a general version of the well-known traveling salesman problem with many relevant applications in industry. Based on mainstream ant colony ideas, an unusual sequenced local search and a distance based penalty function are added which result in a method that is convincingly shown to be the best heuristic published for this problem class. Results on 67 test problems show that the ant colony method performs as well or better than all other methods from the literature in all cases and does so at very modest computational cost. Furthermore, the ant colony method is insensitive to seed, problem instance, problem size and degree of constraint.

1. Bauer, A.,B. Bullnheimer R. F. Hartl,C. Strauss(2000).Minimizing Total Tardiness on a Single Machine Using Ant Colony Optimization.Central European Journal of Operations Research,8(2),125-141.
2. Bilchev, G.,I. C. Parmee,T. Fogarty(1995).The Ant Colony Meta phor for Searching Continuous Design Spaces.Lecture Notes in Computer Science,993,25-39.
3. Chao, I. M.,B. L. Golden,E. A. Wasil(1996).A Fast and Effective Heuristic for the Orienteering.European Journal of Operational Research,88,475-489.
4. Colorni, A.,M. Dorigo, V. Maniezzo,M. Trubian(1994).Ant System for Job-Shop Scheduling.Belgian Journal of Operations Research, Statistics and Computer Science (JORBEL),34(1),39-53.
5. Costa, D.,A. Hertz(1997).Ants Can Colour Graphs.Journal of the Operational Research Society,48,295-305.
6. Den Besten, M.,T. Stützle,M. Dorigo(2000).Ant Colony Optimization for the Total Weighted Tardiness Problem.Proceedings of the 6th International Conference on Parallel Problem Solving from Nature (PPSN VI).
7. Di Caro, G.,M. Dorigo(1998).Ant Colonies for Adaptive Routing in Packet-Switched Communication Networks.Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V).
8. Dorigo, M.(1992).Italy,Politecnico di Milano.
9. Dorigo, M.,L. M. Gambardella(1997).Ant Colony System: A Cooperative Learning Approach to the Travelling Salesman Problem.IEEE Transactions on Evolutionary Computation,1(1),53-66.
10. Fischetti, M.,J. J. S. Gonzalez,P. Toth(1998).Solving the Orienteering Problem through Branch-and-Cut.INFORMS Journal on Computing,10(2),133-148.
11. Gambardella, L. M.,E. Taillard,G. Agazzi,D. Corne,M. Dorigo,F. Glover(1999).New Ideas in Optimization.McGraw-Hill.
12. Gambardella, L. M.,M. Dorigo(2000).An Ant Colony System Hybridized with a New Local Search for the Sequential Ordering Problem.INFORMS Journal on Computing,12(3),237-255.
13. Golden, B. L.,L. Levy,R. Vohra(1987).The Orienteering Problem.Naval Research Logistics,34,307-318.
14. Golden, B. L.,Q. Wang,L. Liu(1988).A Multifaceted Heuristic for The Orienteering Problem.Naval Research Logistics,35,359-366.
15. Hayes, M.,J. M. Norman(1984).Dynamic Programming in Orienteering: Route Choice and the Siting of Controls.Journal of the Operational Research Society,35(9),791-796.
16. Keller, P. C.(1989).Algorithms to Solve the Orienteering Problem: A Comparison.European Journal of Operational Research,41,224-231.
17. Laporte, G.,S. Martello(1990).The Selective Traveling Salesman Problem.Discrete Applied Mathematics,26,193-207.
18. Leguizamon, G.,Z. Michalewicz(1999).A New Version of Ant System for Subset Problems.Proceedings of the 1999 Congress on Evolutionary Computation
19. Leifer, A. C.,M. B. Rosenwein(1993).Strong Linear Programming Relaxations for the Orienteering Problem.European Journal of Operational Research,73,517-523.
20. Liang, Y.-C.,A. E. Smith(2004).An Ant Colony Optimization Algorithm for the Redundancy Allocation Problem (RAP).IEEE Transactions on Reliability,53(3),417-423.
21. Liang, Y.-C.,M.-H. Lo,A. H. L. Chen(2003).An Ant Colony Approach for the Vehicle Routing Problem under Distance and Capacity Constraints.Proceedings of the 8th Annual International Conference on Industrial Engineering-Theory, Applications and Practice (IJIE2003),Nevada:
22. Maniezzo, V.,A. Colorni(1999).The Ant System Applied to the Quadratic Assignment Problem.IEEE Transactions on Knowledge and Data Engineering,11(5),769-778.
23. Mariano, C. E.,E. Morales(1999).MOAQ an Ant-Q Algorithm for Multiple Objective Optimization Problems.Proceedings of the Genetic and Evolutionary Computation Conference,1,894-901.
24. Merkle, D.,M. Middendorf(2005).On Solving Permutation Scheduling Problems with Ant Colony Optimization.International Journal of Systems Science,36(5),255-266.
25. Michels, R.,M. Middendorf(1998).An Island Model Based Ant System with Lookahead for the Shortest Supersequence Problem.Proceedings of the 5th International Conference on Parallel Problem Solving from Nature (PPSN V),The Netherlands:
26. Michels, R.,M. Middendorf,D. Corne,M. Dorigo,F. Glover(1999).An Ant System for the Shortest Common Supersequence Problem.New Ideas in Optimization.
27. Middendorf, M.,F. Reischle,H. Schmeck(2002).Multi Colony Ant Algorithms.Journal of Heuristics,8(3),305-320.
28. Mladenovic, N.,P. Hansen(1997).Variable Neighborhood Search.Computers and Operations Research,24(11),1097-1100.
29. Ramalhinho, H.,D. Serra(1998).Adaptive Approach Heuristics for the Generalized Assignment Problem.Economic Working Paper 288.
30. Ramesh, R.,K. M. Brown(1991).An Efficient Four-Phase Heuristic for the Generalized Orienteering Problem.Computers and Operations Research,18(2),151-165.
31. Ramesh, R.,Y. S. Yoon,M. H. Karwan(1992).An Optimal Algorithm for the Orienteering Tour Problem.ORSA Journal on Computing,4(2),155-165.
32. Schoofs, L.,B. Naudts(2000).Ant Colonies are Good at Solving Constraint Satisfaction Problems.Proceedings of the 2000 Congress on Evolutionary Computation
33. Stützle, T.,M. Dorigo,D. Corne,M. Dorigo,F. Glover(1999).ACO Algorithms for the Quadratic Assignment Problem.New Ideas in Optimization.
34. Tasgetiren, M. F.,A. E. Smith(2000).A Genetic Algorithm for the Orienteering Problem.Proceedings of the 2000 Congress on Evolutionary Computation
35. Tsiligirides, T.(1984).Heuristic Methods Applied to Orienteering.Journal of Operational Research Society,35(9),797-809.
36. Wagner, I. A.,A. M. Bruckstein(1999).Hamiltonian(t)-An Ant Inspired Heuristic for Recognizing Hamiltonian Graphs.Proceedings of the 1999 Congress on Evolutionary Computation,Washington, D.C.:
37. Wang, Q.,X. Sun, B. L. Golden,J. Jia(1995).Using Artificial Neural Networks to Solve the Orienteering Problem.Annals of Operations Research,61,111-120.
38. Wodrich, M.,G. Bilchev(1997).Cooperative Distributed Search: The Ants` Way.Journal of Control and Cybernetics,26(3),413-446.
39. Wren, A.,A. Holiday(1972).Computer Scheduling of Vehicles from One or More Depots to a Number of Delivery Points.Operations Research Quarterly,23,333-344.

1. (2013).A multiple-level variable neighborhood search approach to the orienteering problem.工業工程學刊,30(4),238-247.