Strong multi-commodity flow formulations for the asymmetric traveling salesman problem

Ali Balma, Safa Ben Salem, Mehdi Mrad and Talel Ladhari

European Journal of Operational Research, 2018, vol. 271, issue 1, 72-79

Abstract: We provide new compact formulations of polynomial size for the asymmetric traveling salesman problem obtained through the Reformulation-Linearization Technique. The first one is obtained directly by this latter approach while the two others are derived by performing projections of this formulation on the variables of the existing models. We show that the devised formulations are stronger than the state-of-the-art models. Computational experiments conducted on benchmark instances for the classical variant and with precedence constraints confirm the better quality of the relaxations provided by our proposed formulations.

Keywords: Traveling salesman; Reformulation-linearization technique; Compact formulations; Sequential ordering problem (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718304193
Full text for ScienceDirect subscribers only

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:eee:ejores:v:271:y:2018:i:1:p:72-79

DOI: 10.1016/j.ejor.2018.05.021

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().