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.

KEYWORDS:

• Travelling salesman problem
• robustness
• special structured matrices
• combinatorial
• linear programming
• Kalmanson

ORCID

Seyed Taghi Akhavan Niaki http://orcid.org/0000-0001-6281-055X

Additional information

Notes on contributors

Azmin Azliza Aziz

Azmin Azliza Aziz is an Assistant Professor in the Faculty of Business and Accountancy, University of Malaya. Her research interests are Operations research and Applied Statistics.

Seyed Mohsen Mousavi

Seyed Mohsen Mousavi is a Postdoctoral Research Associate in Faculty of Information Technology, University of Jyvaskyla, Finland. His research fields are Optimization, Operations research, Supply Chain, Multiobjective optimization and Machine learning.

Madjid Tavana

Madjid Tavana is a Professor and Distinguished Chair of Business Analytics at La Salle University, where he serves as Chairman of the Business Systems and Analytics Department. He also holds an Honorary Professorship in Business Information Systems at the University of Paderborn in Germany. Dr. Tavana is Distinguished Research Fellow at the Kennedy Space Center, the Johnson Space Center, the Naval Research Laboratory at Stennis Space Center, and the Air Force Research Laboratory. He was recently honored with the prestigious Space Act Award by NASA. He holds an MBA, PMIS, and PhD in Management Information Systems and received his Post-Doctoral Diploma in Strategic Information Systems from the Wharton School at the University of Pennsylvania. He has published 14 books and over 250 research papers in international scholarly academic journals. He is the Editor-in-Chief of International Journal of Applied Decision Sciences, International Journal of Management and Decision Making, International Journal of Communication Networks and Distributed Systems, International Journal of Knowledge Engineering and Data Mining, International Journal of Strategic Decision Sciences, and International Journal of Enterprise Information Systems.

Seyed Taghi Akhavan Niaki

Seyed Taghi Akhavan Niaki is a Distinguished Professor of Industrial Engineering at Sharif University of Technology. His research interests are in the areas of simulation modeling and analysis, applied statistics, multivariate quality control, and operations research. Before joining Sharif University of Technology, he worked as a systems engineer and quality control manager for Iranian Electric Meters Company. He received his Bachelor of Science degree in Industrial Engineering from Sharif University of Technology, his Master’s and Ph.D. degrees both in Industrial Engineering from West Virginia University. He is the Editor-In-Chief of Scientia Iranica, the Editor of Scientia Iranica – Transactions E, the Executive Editor of Scientific-Research Journal of Sharif, the Editor of Sharif Journal of Industrial Engineering and Management, and a member of the board of editors in several international journals. He is also a member of alpha-pi-mu.