A1 Journal article (refereed)
An Investigation of the Robustness in the Travelling Salesman Problem Routes Using Special Structured Matrices (2020)


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. doi:10.1080/23302674.2018.1551584


JYU authors or editors


Publication details

All authors or editors: Aziz, Azmin Azliza; Mousavi Abdehgah, Mohsen; Tavana, Madjid; Niaki, Seyed Taghi Akhavan

Journal or series: International Journal of Systems Science

ISSN: 0020-7721

eISSN: 1464-5319

Publication year: 2020

Volume: 7

Issue number: 2

Pages range: 172-181

Publisher: Taylor & Francis

Publication country: United Kingdom

Publication language: English

DOI: http://doi.org/10.1080/23302674.2018.1551584

Open Access: Publication channel is not openly available

Publication is parallel published (JYX): https://jyx.jyu.fi/handle/123456789/70087


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.


Keywords: linear programming

Free keywords: Travelling salesman problem; robustness; special structured matrices; combinatorial; Kalmanson


Contributing organizations


Ministry reporting: Yes

Reporting Year: 2020

Preliminary JUFO rating: 1


Last updated on 2020-09-07 at 23:10