Shortest path problem solving based on ant colony optimization metaheuristic

• Autorzy: Głąbowski M. , Musznicki B , Nowak P. , Zwierzykowski P.

Identyfikatory

DOI

10.2478/v10248-012-0011-5

• Języki publikacji: EN

Abstrakty

EN

The Ant Colony Optimization (ACO) metaheuristic is a versatile algorithmic optimization approach based on the observation of the behaviour of ants. As a result of numerous analyses, ACO has been applied to solving various combinatorial problems. The ant colony metaheuristic proves itsel I' to be efficient in solving NP-hard problems, often generating the best solution in the shortest amount of time. However, not enough attention has been paid to ACO as a means of solving problems that have optimal solutions which can be found using other methods. The shortest path problem is undoubtedly one of the aspects of great significance to navigation and telecommunications. It is used, amongst others, for determining the shortest route between two geographical locations, for routing in packet networks, and to balance and optimize network utilization. Thus, this article introduces ShortestPathACO, an Ant Colony Optimization based algorithm designed to find the shortest path in a graph. The algorithm consists of several subproblems that are presented successively. Each subproblem is discussed from many points of view to enable researchers to find the most suitable solutions to the problems they investigate.

Słowa kluczowe

EN

ACO Metaheuristic; NP-hard problems; shortest path; algorithmic methods

• Wydawca: Instytut Telekomunikacji i Informatyki Uniwersytetu Technologiczno-Przyrodniczego w Bydgoszczy
• Czasopismo: Image Processing & Communications
• Rocznik: 2012
• Tom: Vol. 17, no. 1-2
• Strony: 7--17
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Głąbowski M.

• Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

autor

Musznicki B

• Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

autor

Nowak P.

• Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

autor

Zwierzykowski P.

• Chair of Communications and Computer Networks, Polanka 3, 60-965 Poznań, Poland

Bibliografia

• [1] M. Dorigo, Optimization, Learning and Natural Algorithms, Ph.D. Thesis, Politecnico di Milano, 1992.
• [2] M. Dorigo and T. Stützle, Ant Colony Optimization, The MIT Press, Cambridge, 2004.
• [3] M. Dorigo, V. Maniezzo and A. Colorni, The Ant System: Optimization by a colony of cooperating agents, in IEEE Transactions on Systems, Man, and Cybernetics-Part B, 26( I ):29-41, I 1996.
• [4] T. Stützle and H. H. Hoos, The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem, in Proceedings of IEEE International Conference on Evolutionary Computation, pp. 309-314, 1997
• [5] T. Stützle and H. H. Hoos, MAX-MIN Ant System, in Future Generation Computer Systems, 16(8):889-914, 2000