Solving the single and multiple asymmetric Traveling Salesmen Problems by generating subtour elimination constraints from integer solutions

ABSTRACT

We present an algorithm to solve single and multiple asymmetric traveling salesmen problems (ATSP and mATSP) by generating violated subtour elimination constraints from specific integer solutions. Computational results for the ATSP reveal that the proposed approach is able to solve 29 out of 33 well-known instances taken from the literature (involving between 100 and 1001 cities) to optimality within an hour of CPU time. Furthermore, the proposed approach is demonstrated to outperform any of the most effective state-of-the-art exact algorithms available in the literature when applied to solve the given ATSP instances via their equivalently transformed symmetric TSP representations. For the mATSP, the proposed approach is able to solve 27 out of 36 instances derived from the ATSP library involving up to 1001 cities to optimality within an hour of CPU time and also outperforms the direct solution by CPLEX, one of the three most effective formulations reported in the literature for this class of problems. The proposed approach is easy to implement and can be used to solve ATSP and mATSP as stand-alone models or can be applied in contexts where they appear as sub-models within some application settings.

KEYWORDS:

• Asymmetric traveling salesman problem
• multiple asymmetric traveling salesman
• subtour elimination constraints

Additional information

Notes on contributors

Maichel M. Aguayo

Maichel M. Aguayo is an Assistant Professor in the Industrial Engineering Department at University of Concepción, Concepción, Chile. He is a graduate of Virginia Tech, where he received his doctoral degree. His research interests are in the areas of logistics, routing problems, and applied mathematical programming.

Subhash C. Sarin

Subhash C. Sarin is the Paul T. Norton Endowed Professor in the Grado Department of Industrial and Systems Engineering at Virginia Polytechnic Institute and State University, Blacksburg, Virginia. His research interests are in the areas of production scheduling, applied mathematical programming, and design and analysis of manufacturing systems. He has published several papers in Industrial Engineering and Operations Research journals and has co-authored three books in the production scheduling area. He is a recipient of several prestigious awards at the university, state, and national levels. He has served on the editorial boards of many journals. He is a fellow of the Institute of Industrial and Systems Engineering and a full member of the Institute for Operations Research and the Management Sciences.

Hanif D. Sherali

Hanif D. Sherali is a University Distinguished Professor Emeritus in the Industrial and Systems Engineering Department at Virginia Polytechnic Institute and State University. His areas of research interest are in mathematical optimization modeling, analysis, and design of algorithms for specially structured linear, nonlinear, and continuous and discrete nonconvex programs, with applications to transportation, location, engineering and network design, production, economics, and energy systems. He has published over 343 refereed articles in various operations research journals and has coauthored nine books, with a total Google Scholar citation count of over 27 025 and an H-index of 62. He is an elected member of the National Academy of Engineering, a fellow of both INFORMS and IIE, and a member of the Virginia Academy of Science Engineering and Medicine.