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

Maichel M. Aguayo, Subhash C. Sarin and Hanif D. Sherali

Journal of the Operational Research Society, 2018, vol. 69, issue 5, 734-746

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.

Date: 2018
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1057/s41274-017-0261-0 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:69:y:2018:i:5:p:734-746

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1057/s41274-017-0261-0

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().