main| new issue| archive| editorial board| for the authors| publishing house|
Ðóññêèé
Main page
New issue
Archive of articles
Editorial board
For the authors
Publishing house

 

 


ABSTRACTS OF ARTICLES OF THE JOURNAL "INFORMATION TECHNOLOGIES".
No. 12. Vol. 30. 2024

DOI: 10.17587/it.30.607-615

I. F. Leonova, Postgraduate Student,
South Ural State University, Cheliabinsk, Russian Federation

Results of Computational Experiment for Solving the Minimum Traveling Salesman Problem by the Cycle Merging Algorithm

The traveling salesman problem is an important combinatorial optimization problem, which consists in finding the shortest path that passes through each city exactly once and ends at the starting point. Despite its simple formulation, this problem turns out to be computationally complex, and its exact solution requires significant computational resources. In this regard, the search for efficient algorithms to solve the traveling salesman problem remains an urgent task in the context of modern technological challenges. In this paper we present the results of a computational experiment that gives an insight into the quality of the cycle merging algorithm for the minimum traveling salesman problem. The quality of the cycle merging algorithm is investigated on seven sets of instances of the traveling salesman problem. The results obtained are compared with the results of computational experiments for some known heuristics. The analysis allows us to say that the cycle merging algorithm shows relatively good results for all tested sets and can be used for a wide range of instances of the traveling salesman problem as a relatively fast heuristic of good enough quality.
Keywords: traveling salesman problem, heuristic algorithm, construction algorithm, computational experiment

P. 607-615

References

  1. Turkensteen M., Ghosh D., Goldengorin B., Sierksma G. Tolerance-based branch and bound algorithms, A EURO conference for young OR researches and practitioners, ORP3 2005, 6—10 September 2005, Valencia, Spain. Proceedings Edited by C. Maroto et al., ESMAP SL, 2005, pp. 171—182.
  2. Johnson D. S., Gutin G., McGeoch L. A., Yeo A., Zhang W., Zverovitch A. Experimental analysis of heuristics for the ATSP. The traveling salesman problem and its variations, Combinatorial Optimization, vol. 12, Springer, Boston, MA, 2007, pp. 445—487, doi: 10.1007/0-306-48213-4_10.
  3. Glover F., Gutin G., Yeo A., Zverovich A. Construction heuristics for the asymmetric TSP, European Journal of Operational Research, 2001, vol. 129, no. 3, pp. 555—568, doi: 10.1016/s0377-2217(99)00468-3.
  4. Gutin G., Yeo A., Zverovich A. Traveling salesman should not be greedy: domination analysis of greedy-type heuristics for the TSP, Discrete Applied Mathematics, 2002, vol. 117, no. 1—3, pp. 81—86, doi: 10.1016/s0166-218x(01)00195-0.
  5. 5. Panyukov A. V., Leonova Yu. F. Cycle merging algorithm for the metric problem of the traveling salesman at maximum, Bulletin of the South Ural State University. Series: Computational Mathematics and Informatics, 2021, vol. 10, no. 4, pp. 26—36 (in Russian), doi: 10.14529/cmse210402.
  6. Christofides N. Worst-case analysis of a new heuristic for the travelling salesman problem, Operations Research Forum, Cham, Springer International Publishing, 2022, vol. 3, no. 1, p. 20.
  7. Google. 2015. OR-tools: Google's Operations Research tools, available at: https://developers.google.com/optimization?hl=ru (date of access: 01.03.24).
  8. Johnson D. S., McGeoch L. A. The Travelling Saleman Problem: A case study in Local Optimization, AT&T Labs, Florham Park, Department of Mathematics and Computer Science, Amherst College, 1995.
  9. Helsgaun K. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems, Roskilde, Roskilde University, 2017, vol. 12, pp. 966—980.
  10. Lin S., Kernighan B. W. An effective heuristic algorithm for the traveling-salesman problem, Operations research, 1973, vol. 21, no. 2, pp. 498—516.
  11. Helsgaun K. An effective implementation of the Lin—Kernighan traveling salesman heuristic, European journal of operational research, 2000, vol. 126, no. 1, pp. 106—130.
  12. Johnson D. S. A case study in local optimization, Local search in combinatorial optimization, 1997, pp. 215—310, DOI: 10.2307/j.ctv346t9c.
  13. Reinelt G. The traveling salesman: Computational solutions for TSP applications, Springer, 1994.
  14. Karp R. M. A patching algorithm for the nonsymmetric traveling-salesman problem, SIAM Journal on Computing, 1979, vol. 8, no. 4, pp. 561—573, doi: 10.1137/0208045.
  15. Karp R. M., Steele J. M. Probabilistic analysis of heuristics, The traveling salesman problem, 1985, pp. 181—205.
  16. Yeo A. Large exponential neighbourhoods for the TSP, Preprint, Odense, Denmark, Dept of Maths and CS, Odense University, 1997.
  17. Deineko V. G., Woeginger G. J. A study of exponential neighborhoods for the travelling salesman problem and for the quadratic assignment problem, Mathematical programming, 2000, vol. 87, pp. 519—542, doi: 10.1007/s101070050010.
  18. Glover F., Punnen A. P. The travelling salesman problem: new solvable cases and linkages with the development of approximation algorithms, Journal of the Operational Research Society, 1997, vol. 48, pp. 502—510, doi: 10.1038/sj.jors.2600392.
  19. Gutin G. Exponential neighbourhood local search for the traveling salesman problem, Computers & Operations Research, 1999, vol. 26, no. 4, pp. 313—320, doi: 10.1016/s0305-0548(98)00064-1.
  20. Gutin G., Yeo A. Small diameter neighbourhood graphs for the traveling salesman problem: at most four moves from tour to tour, Computers & Operations Research, 1999, vol. 26, no. 4, pp. 321—327, doi: 10.1016/s0305-0548(98)00065-3.
  21. Balas E., Simonetti N. Linear time dynamic programming algorithms for some new classes of restricted TSP's, Proc. IPCO V, LNCS, 1996, vol. 1084, pp. 316—329, doi: 10.1287/ijoc.13.1.56.9748.
  22. Carlier J., Villon P. A new heuristic for the traveling salesman problem, RAIRO-Operations Research, 1990, vol. 24, no. 3, pp. 245—253, doi: 10.1051/ro/1990240302451.
  23. Sigal I. H., Ivanova A. P. Introduction to Applied Discrete Programming. Models and computational algorithms, Moscow, FIZMATLIT, 2007, 304 p. (in Russian).
  24. Reinelt G. TSPLIB—A traveling salesman problem li­brary, ORSA journal on computing, 1991, vol. 3 (INFORMS), pp. 376—384, doi: 10.1287/ijoc.3.4.376.
  25. Leonova Yu. F. Investigation of the quality of the cycle merging algorithm on examples from the TSPLIB library, Actual problems of applied mathematics, computer science and mechanics: proceedings of the International Scientific Conference, Voronezh, 13—15 December 2021, Voronezh, 2022, pp. 573—579 (in Russian).
  26. Balas E., Thoth P. Branch and bound methods. Chapter 10, The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, John Wiley & Sons, New York, 1985, pp. 80—147, doi: 10.21236/ada126957.
  27. Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees, Operations research, 1970, vol. 18, no. 6, pp. 1138—1162, doi: 10.1287/opre.18.6.1138.
  28. Held M., Karp R. M. The traveling-salesman problem and minimum spanning trees: Part II, Mathematical programming, 1971, vol. 1, no. 1, pp. 6—25, doi: 10.1007/bf01584070.
  29. Zverovitch A. E. Construction Heuristics for Hard Combinatorial Optimisation Problems, Diss. University of London, 2003.

To the contents