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

DOI10.1016/J.EJOR.2018.05.021MaRDI QIDQ724060zbMATH OpenOpenAlexWikidataFDO

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

Publication date 25 July 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2018.05.021

zbMATH Keywords

compact formulationsreformulation-linearization techniquesequential ordering problemtraveling salesman

Mathematics Subject Classification ID

Transportation, logistics and supply chain management (90B06) Combinatorial optimization (90C27) Programming involving graphs or networks (90C35)

Recommendations

• A comparative analysis of several asymmetric traveling salesman problem formulations
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem
• Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations

Cites work

• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A comparative analysis of several asymmetric traveling salesman problem formulations
• A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A New Formulation for the Travelling Salesman Problem
• A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Handbooks in operations Research \& management science: Transportation
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Integer Programming Formulation of Traveling Salesman Problems
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• Solution of a Large-Scale Traveling-Salesman Problem
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(9)

• Stronger multi-commodity flow formulations of the (capacitated) sequential ordering problem
• Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations
• New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• Formulations for the clustered traveling salesman problem with d-relaxed priority rule
• Tight lower bounds for the traveling salesman problem with draft limits
• An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem
• Lifted formulations for the target visitation problem
• A comparative analysis of several asymmetric traveling salesman problem formulations

Describes a project that uses

Uses Software

• TSPLIB
• CPLEX

This page was built for publication: Strong multi-commodity flow formulations for the asymmetric traveling salesman problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q724060)