Choice of best possible metaheuristic algorithm for the travelling salesman problem with limited computational time: quality, uncertainty and speed

• Autorzy: Antosiewicz M. , Koloch G. , Kamiński B.
• Języki publikacji: EN

Abstrakty

EN

We compare six metaheuristic optimization algorithms applied to solving the travelling salesman problem. We focus on three classical approaches: genetic algorithms, simulated annealing and tabu search, and compare them with three recently developed ones: quantum annealing, particle swarm optimization and harmony search. On top of that we compare all results with those obtained with a greedy 2-opt interchange algorithm. We are interested in short-term performance of the algorithms and use three criteria to evaluate them: solution quality, standard deviation of results and time needed to reach the optimum. Following the results from simulation experiments we conclude that simulated annealing and tabu search outperform newly developed approaches in short simulation runs with respect to all three criteria. Simulated annealing finds best solutions, yet tabu search has lower variance of results and converges faster.

Słowa kluczowe

EN

metaheuristic algorithms; travelling salesman problem

• Wydawca: Komisja Informatyki Polskiej Akademii Nauk, Oddział w Gdańsku
• Czasopismo: Journal of Theoretical and Applied Computer Science
• Rocznik: 2013
• Tom: Vol. 7, nr 1
• Strony: 46--55
• Opis fizyczny: Bibliogr. 14 poz., rys., tab.

Twórcy

autor

Antosiewicz M.

• Warsaw School of Economics

autor

Koloch G.

• Warsaw School of Economics

autor

Kamiński B.

• Warsaw School of Economics

Bibliografia

• [1] Geem Z.W., Kim J.H., Loganathan G.V. A New Heuristic Optimization Algorithm: Harmony Search. Simulation, No. 2/76, 2001, s. 60-68
• [2] Gutin G., Punnen A.P. The Traveling Salesmen Problem and Its Variations. Kluver Academic Publishers, 2002
• [3] Hahsler M., Hornik K. TSP - Infrastructure for the Traveling Salesperson Problem. Journal of Statistical Software, No 2/23, 2007
• [4] Johnson D.S., Papadimitriou C.H. Computational Complexity. E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys, (eds), The Travelling Salesemen Problem, Wiley, New York, 2002
• [5] Johnson D.S., McGeoch L.A. Experimental Analysis of Heuristics for the STSP. G. Gutin, A.P. Punnen (eds), The Travelling Salesemen Problem and its Variations, Kluwer Academic Publishers, 2002
• [6] Kadowaki T. Study of Optimization Problems by Quantum Annealing, PhD Thesis, Department of Physics, Tokyo Institute of Technology, 1998
• [7] Kaur B., Mittal U. Optimization of TSP using Genetic Algorithm. Advances in Computational Sciences and Technology, No 2/3, 2010, s. 119-125
• [8] Kim B.I., Shim J.I., Zhang M. Comparison of TSP Algorithms. Project for Models in Facilities Planning and Materials Handling, 1998
• [9] Misevičius A. Using Iterated Tabu Search for the Travelling Salesemen Problem. Informacines Technologijos ir Valdymas, No 32/3, 2004, s. 29-40
• [10] Ram D.J., Sreenivas T.H., Subramaniam K.G. Parallel Simulated Annealing Algorithms. Journal of Parallel and Distributed Computing, No 37, 1996, s. 207-212
• [11] Schrijver A. On the history of combinatorial optimization (till 1960). K. Aardal, G.L. Nemhauser, R. Weismantel, (eds), Handbook of Discrete Optimization, Elsevier, Amsterdam, 2005
• [12] Sze S.N., Tiong W.K. A Comparison between Heuristic and Meta-Heuristic Methods for Solving the Multiple Traveling Salesman Problem. World Academy of Science, Engineering and Technology, No 25, 2007, s. 300-303
• [13] Tan K.C., Lee L.H., Zhu Q.L., Ou K. Heuristic methods for vehicle routing problem with time windows. Artificial Intelligence in Engineering, No 15, 2001, s. 281-295
• [14] Zhang C., Sun J., Wang Y., Yang Q. An Improved Discrete Particle Swarm Optimization Algorithm for TSP. Proceedings of Web Intelligence/IAT Workshops'2007, 2007, s. 35-38