An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices
Abstract
In this study, the robustness of the Travelling Salesman Problem (TSP) routes is investigated by recognising the special combinatorial structures of Kalmanson matrices. A recognition algorithm encompassing three procedures based on combinatorial and linear programming (LP) is developed and executed on several randomly generated instances. These procedures produce three lower bounds which provide guarantees on the optimality of the solutions. Computational experiments show that the proposed LP-based procedure performs efficiently well across all problem dimensions and provides the best lower bounds to the TSP. This is supported by an average deviation of less than 7% between the TSP tour lengths and the lower bounds of the Kalmanson matrices.
Main Authors
Format
Articles
Research article
Published
2020
Series
Subjects
Publication in research information system
Publisher
Taylor & Francis
The permanent address of the publication
https://urn.fi/URN:NBN:fi:jyu-202005143208Use this for linking
Review status
Peer reviewed
ISSN
0020-7721
DOI
https://doi.org/10.1080/23302674.2018.1551584
Language
English
Published in
International Journal of Systems Science
Citation
- Aziz, A. A., Mousavi Abdehgah, M., Tavana, M., & Niaki, S. T. A. (2020). An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices. International Journal of Systems Science, 7(2), 172-181. https://doi.org/10.1080/23302674.2018.1551584
License
Copyright© 2018 Taylor & Francis