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

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

IISE Transactions, 2018, vol. 50, issue 1, 45-53

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.

Date: 2018
References: View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://hdl.handle.net/10.1080/24725854.2017.1374580 (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:uiiexx:v:50:y:2018:i:1:p:45-53

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

DOI: 10.1080/24725854.2017.1374580

Access Statistics for this article

IISE Transactions is currently edited by Jianjun Shi

More articles in IISE Transactions from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().