Complexity indices for the traveling salesman problem continued

Authors

  • Dragoš Cvetković Faculty of Electrical Engineering, University of Belgrade and Mathematical Institute SANU, Belgrade, Serbia
  • Zorica Dražić Faculty of Mathematics, University of Belgrade, Belgrade, Serbia
  • Vera Kovačević-Vujčić Faculty of Organizational Sciences, University of Belgrade, Belgrade, Serbia

DOI:

https://doi.org/10.2298/YJOR201121014C

Keywords:

Traveling salesman problem, Complexity index, Concorde TSP Solver, Random instances, Correlation

Abstract

We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs G with distances between cities as edge weights. A complexity index is an invariant of an instance I by which we predict the execution time of an exact TSP algorithm for I. In the paper [5] we have considered some short edge subgraphs of G and defined several new invariants related to their connected components. Extensive computational experiments with instances on 50 vertices with the uniform distribution of integer edge weights in the interval [1,100] show that there exists correlation between the sequences of selected invariants and the sequence of execution times of the well-known TSP Solver Concorde. In this paper we extend these considerations for instances up to 100 vertices.

References

Baniasadi, P., Ejov, V., Haythorpe, M., and Rossomakhine, S., ”A new benchmark set for traveling salesman problem and hamiltonian cycle problem”, arXiv:1806.09285, (2018).

Bondy, J.A., ”Variations on the Hamiltonian theme”, Canadian Mathematical Bulletin, 15 (1) (1972) 57–62.

Coxeter, H.S.M., ”Self-dual configurations and regular graphs”, Bulletin of the American Mathematical Society, 56 (5) (1950) 413–455.

Cvetković, D., ”Complexity indices for the travelling salesman problem and data mining”, Transactions of Combinatorics, 1 (1) (2012) 35–43.

Cvetković, D., Čangalović, M., Dražić, Z., and Kovačević-Vujčić, V., ”Complexity indices for the traveling salesman problem based on short edge subgraphs”, Central European Journal of Operations Research, 26 (3) (2018) 759–769.

Cvetković, D., Čangalović, M., and Kovačević-Vujčić, V., ”Complexity indices for the travelling salesman problem based on a semidefinite relaxation”, Zbornik radova XXVI Simpozijuma za operaciona istraživanja, SYM-OP-IS 1999, Beograd, (1999) 177–180.

Cvetković, D., Dimitrijević, V., and Milosavljević, M., ”A survey of some non-standard traveling salesman problems”, Yugoslav journal of operations research, 2 (2) (1992) 163–185.

Cvetković, D., Dimitrijević, V., and Milosavljević, M., Variations on the Travelling Salesman Theme, Libra produkt, Beograd, 1996.

Derpich, I., Herrera, C., Sepúlveda, F., and Ubilla, H., ”Complexity indices for the multidimensional knapsack problem”, Central European Journal of Operations Research, 29 (2) (2021) 589–609.

Schwenk, A.J., ”Enumeration of Hamiltonian cycles in certain generalized Petersen graphs”, Journal of Combinatorial Theory, Series B, 47 (1) (1989) 53–59.

Smith-Miles, K., and Lopes, L., ”Measuring instance difficulty for combinatorial optimization problems”, Computers & Operations Research, 39 (5) (2012) 875–889.

Vera, J.R., and Derpich, I., ”Incorporating condition measures in the context of combinatorial optimization”, SIAM Journal on Optimization, 16 (4) (2006) 965–985.

Watkins, M.E., ”A Theorem on Tait Colorings with an Application to the Generalized Petersen Graphs”, Journal of Combinatorial Theory, 6 (2) (1969) 152–164.

Downloads

Published

2021-11-01

Issue

Vol. 31 No. 4 (2021)

Section

Research Articles

License

Copyright (c) 2021 YUJOR

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.