Pareto-optimal Algorithms for Metric TSP: Experimental Research

Ekaterina N Beresneva (Chirkova), Sergey M Avdoshin

Abstract


The Travelling Salesman Problem (TSP) is a fundamental task in combinatorial optimization. A special case of the TSP is Metric TSP, where the triangle inequality holds. Solutions of the TSP are generally used for costs minimization, such as finding the best tour for round-the-world trip or construction of very large-scale integration schemes. Since the TSP is NP-hard, heuristic algorithms providing near optimal solutions will be considered. The objective of this article is to find a group of Pareto optimal heuristic algorithms for Metric TSP under criteria of run time efficiency and qualitative performance as a part of the experimental study. Classification of algorithms for Metric TSP is presented. Feasible heuristic algorithms and their prior estimates are described. The data structure and the details of the research methodology are provided. Finally, results and prospective research are discussed

Full Text:

PDF

References


D. L. Applegate, The Traveling Salesman Problem, Princeton: Princeton University Press, 2006.

Heidelberg University, "TSPLIB," [Online]. Available: https://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/. [Accessed 01 02 2017].

M. Reed and B. Simon, Methods of Modern Mathematical Physics, London: Academic Press, 1972.

Department of Combinatorics and Optimization at the University of Waterloo, "Status of VLSI Data Sets," University of Waterloo, [Online]. Available: http://www.math.uwaterloo.ca/tsp/vlsi/summary.html. [Accessed 29 04 2017].

Wikipedia, "Multi-objective optimization," [Online]. Available: https://en.wikipedia.org/wiki/Multi-objective_optimization. [Accessed 03 02 2017].

University of Waterloo, "Status of VLSI Data Sets," [Online]. Available: http://www.math.uwaterloo.ca/tsp/vlsi/summary.html. [Accessed 08 02 2017].

B. Hock, "An examination of heuristic algorithms for the Travelling Salesman problem," University of Cape Town, Cape Town, 1988.

M. Fisher, G. Nemhauser and L. Wolsey, An analysis of approximations for maximizing submodular set functions, Springer, 1978.

G. Clarke and J. Wright, "Scheduling of Vehicles from a Central Depot to a Number of Delivery Points," Operations Research, no. 12, pp. 568-581, 1964.

B. L. Golden, T. Magnanti and H. Nguyen, "Implementing vehicle routing algorithms," Networks, vol. 7, no. 2, pp. 113-148, 1977.

D. Rosenkrantz, R. Stearns and P. Lewis II, "An analysis of several heuristics for the traveling salesman problem," vol. 6, pp. 563-581, 1977.

F. Glover and A. P. Punnen, "The Travelling Salesman Problem: New Solvable Cases and Linkages with the Development of Approximation Algorithms," vol. 48, no. 5, 1997.

E. H. Moore, "On Certain Crinkly Curves," Trans. Amer. Math Soc., vol. 1, pp. 72-90, 1900.

D. Johnson and L. McGeoch, "The Traveling Salesman Problem: A Case Study," in Local Search in Combinatorial Optimization, Chichester, 1997, pp. 215-310.

N. Christofides, "Worst-case analysis of a new heuristic for the travelling salesman problem," Graduate School of Industrial Administration, CMU, 1976.

N. Christofides, Graph theory - An Algorithmic Approach, New York: Academic Press, 1974.

F. Bock, "An algorithm for solving "traveling-salesman" and related network optimization problems," in Unpublished manuscript a-ssociated with talk presented at the 14th ORSA National Meeting, 1958.

G. Croes, "A method for solving travelling salesman problems," Operation Resources, vol. 6, pp. 791-812, 1958.

E. Aarts and J. K. Lenstra, Local Search in Combinatorial Optimization, Princeton, New Jersey: Princeton University Press, 2003.

G. Gutin and A. Punnen, The Traveling Salesman Problem and Its Variations, vol. 12, Kluwer, Dordrecht: Springer US, 2002.

M. M. Flood, "The traveling-salesman problem," Operation research, vol. 4, pp. 61-75, 1956.

K. Helsgaun, "An effective implementation of the Lin–Kernighan traveling salesman heuristic," EJOR, vol. 12, pp. 106-130, 2000.

P. J. Laarhoven and E. H. Aarts, imulated Annealing: Theory and Applications, Heidelberg, Germany: Springer, 1987.

D. S. Johnson and L. A. McGeoch, "The traveling salesman problem: A case study," in Local Search in Combinatorial Opti- mization, Chichester, UK, John Wiley & Sons, 1997.

M. Dorigo and L. M. Gambardella, "Ant colony system: a cooperative learning approachto the traveling salesman problem," vol. 1, no. 1, 1997.

B. Gorkemli and D. Karaboga, "Quick Combinatorial Artificial Bee Colony -qCABC- Optimization Algorithm for TSP," vol. 1, no. 5, 2013.

W. J. Cook, Combinatorial optimization, New York: Wiley, 1998.

K. Buchin, "Space-Filling Curves," in Organizing Points Sets: Space-Filling Curves, Delaunay Tessellations of Random Point Sets, and Flow Complexes, Berlin, Free University of Berlin, 2007, pp. 5-30.

K. Helsgaun, "LKH," Keld Helsgaun, [Online]. Available: http://www.akira.ruc.dk/~keld/research/LKH/. [Accessed 24 02 2017].

D. E. Rosenkrantz, R. E. Stearns and P. M. Lewis II, "An analysis of several heuristics for the traveling salesman problem," SIAM J. Comput, p. 563–581, 1977.

S. M. Avdoshin and V. V. Belov, "Obobschennyi metod "volny" dlya resheniya ekstremal'nykh zadach na grafah," ZHVM and MF, vol. 19, no. 3, pp. 739-755, 1979.

C. Nilsson, "Heuristics for the traveling salesman problem," Linkoping University, Linkoping, Sweden, 2013.

S. Kirkpatrick, C. Gelatt and M. Vecchi, "Optimization by Simulated Annealing," Science, vol. 220, pp. 671-680, 13 05 1983.

P. van Laarhoven and E. Aarts, Simulated Annealing: Theory and Applications, Heidelberg: Springer, 1987.

B. Gorkemeli and D. Karaboga, "Quick Combinatorial Artificial Bee Colony -qCABC- Optimization Algorithm for TSP," in 2nd International Symposium on Computing in Informatics and Mathematics, 2013.

M. Dorigo, Ant colony optimization, Cambridge: MIT Press, 2004.

T. Lust and J. Teghem, "The Multiobjective Traveling Salesman Problem: A Survey and a New Approach," Studies in Computational Intelligence , vol. 272, pp. 119-141, 2010.


Refbacks

  • There are currently no refbacks.


Abava  Кибербезопасность IT Congress 2024

ISSN: 2307-8162