An Ant Colony Approach to the Orienteering Problem

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

關鍵字

蟻群；越野賽跑問題；旅行推銷員問題；途程；最佳化

並列摘要

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.

並列關鍵字

ant colony ； orienteering problem ； traveling salesman problem ； routing ； optimization

參考文獻

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.

Google Scholar

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.

Google Scholar

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.

Google Scholar

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.