Single-commodity flow-based formulations and accelerated benders algorithms for the high-multiplicity asymmetric traveling salesman problem and its extensions

Please note this paper has been re-typeset by Taylor & Francis from the manuscript originally provided to the previous publisher.

Abstract

In this paper, we present a single-commodity flow-based formulation for the high-multiplicity asymmetric traveling salesman problem (HMATSP), which is an extension of the asymmetric traveling salesman problem (ATSP) wherein a city can be visited multiple times. We show that even though this formulation is not as tight as the best known formulation for the HMATSP, it is faster and easier to use for direct solution by CPLEX and can be used to model several variants or extensions of the HMATSP that have not been studied in the literature. Furthermore, we propose effective accelerated Benders algorithms that are demonstrated to solve instances of the HMATSP and its extensions, which are derived from the well-known ATSP libraries and involve up to 1001 cities, within an hour of CPU time. These are the largest-sized HMATSP instances solved to optimality in the literature.

Keywords:

• Asymmetric traveling salesman problem
• scheduling
• high-multiplicity
• polynomial-length formulation
• benders decomposition

Notes

Please note this paper has been re-typeset by Taylor & Francis from the manuscript originally provided to the previous publisher.