A comparative analysis of several asymmetric traveling salesman problem formulations

DOI10.1016/j.cor.2007.11.008zbMath1179.90321OpenAlexW2092481826WikidataQ96159668 ScholiaQ96159668MaRDI QIDQ955595

B. E. Eshmatov

Publication date: 20 November 2008

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.cor.2007.11.008

zbMATH Keywords

projectionsinteger linear programmingasymmetric traveling salesman problemformulations

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Linear programming (90C05)

Related Items

Generating subtour elimination constraints for the TSP from pure integer solutions ⋮ Layered graph approaches for combinatorial optimization problems ⋮ Modeling lotsizing and scheduling problems with sequence dependent setups ⋮ An effective hybrid harmony search for the asymmetric travelling salesman problem ⋮ The probabilistic travelling salesman problem with crowdsourcing ⋮ The traveling salesman problem with time-dependent service times ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ A new mathematical programming formulation for the single-picker routing problem ⋮ Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations ⋮ An iterated local search for the traveling salesman problem with release dates and completion time minimization ⋮ The multiple Steiner TSP with order constraints: complexity and optimization algorithms ⋮ Integer programming models and linearizations for the traveling car renter problem ⋮ Compact formulations for multi-depot routing problems: theoretical and computational comparisons ⋮ Decomposition-based algorithms for the crew scheduling and routing problem in road restoration ⋮ The prisoner transportation problem ⋮ A multi-cover routing problem for planning rapid needs assessment under different information-sharing settings ⋮ A node current-based 2-index formulation for the fixed-destination multi-depot travelling salesman problem ⋮ Covering and connectivity constraints in loop-based formulation of material flow network design in facility layout ⋮ The vessel swap-body routing problem ⋮ Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ A new graph model and algorithms for consistent superstring problems ⋮ A data-guided lexisearch algorithm for the asymmetric traveling salesman problem ⋮ Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing ⋮ Some contributions of Ailsa H. Land to the study of the traveling salesman problem ⋮ Node based compact formulations for the Hamiltonian p‐median problem ⋮ The cumulative school bus routing problem: Polynomial‐size formulations ⋮ A Benders decomposition approach for order acceptance and scheduling problem: a robust optimization approach ⋮ The delivery man problem with time windows ⋮ Optimization of logistics services in hospitals ⋮ Multiperiod location-routing with decoupled time scales ⋮ Natural and extended formulations for the time-dependent traveling salesman problem ⋮ Rail platooning: scheduling trains along a rail corridor with rapid-shunting facilities ⋮ Consistent vehicle routing problem with service level agreements: a case study in the pharmaceutical distribution sector ⋮ Local search inequalities ⋮ The set orienteering problem ⋮ Selective and periodic inventory routing problem for waste vegetable oil collection ⋮ An analytical comparison of the LP relaxations of integer models for the \(k\)-club problem ⋮ New mixed integer-programming model for the pickup-and-delivery problem with transshipment ⋮ The traveling salesman problem with draft limits ⋮ Unnamed Item ⋮ MIP models for connected facility location: a theoretical and computational study ⋮ Assignment problem with conflicts ⋮ Formulation and a two-phase matheuristic for the roaming salesman problem: application to election logistics ⋮ Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning ⋮ Solving the family traveling salesman problem ⋮ Strong multi-commodity flow formulations for the asymmetric traveling salesman problem ⋮ A new formulation and an exact approach for the many-to-many hub location-routing problem ⋮ Requiem for the Miller-Tucker-Zemlin subtour elimination constraints? ⋮ Routing Optimization Under Uncertainty ⋮ Models and algorithms for the traveling salesman problem with time-dependent service times ⋮ Exact approaches for the cutting path determination problem ⋮ An optimization model for the vehicle routing problem with practical three-dimensional loading constraints ⋮ Equivalent cyclic polygon of a euclidean travelling salesman problem tour and modified formulation ⋮ The minimum flow cost Hamiltonian cycle problem: a comparison of formulations ⋮ Compact formulations of the Steiner traveling salesman problem and related problems

Uses Software

• TSPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Classification of travelling salesman problem formulations
• A result on projection for the vehicle routing problem
• An analytical comparison of different formulations of the travelling salesman problem
• The Euclidean traveling salesman problem is NP-complete
• A reformulation-linearization technique for solving discrete and continuous nonconvex problems
• A classification of formulations for the (time-dependent) traveling salesman problem
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• The perfectly matchable subgraph polytope of a bipartite graph
• Integer Programming Formulation of Traveling Salesman Problems
• A New Formulation for the Travelling Salesman Problem
• Parametric enhancements of the Esau–Williams heuristic for the capacitated minimum spanning tree problem
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• TSPLIB—A Traveling Salesman Problem Library
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• A Survey of Different Integer Programming Formulations of the Travelling Salesman Problem
• Solution of a Large-Scale Traveling-Salesman Problem
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints