The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints

DOI10.1016/S0377-2217(97)00358-5zbMATH Open0971.90099OpenAlexW2092353499MaRDI QIDQ1806889FDOQ1806889

Jose Manuel Pires, Luis Gouveia

Publication date: 20 December 1999

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

Full work available at URL: https://doi.org/10.1016/s0377-2217(97)00358-5

Recommendations

• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• A note on the complexity of the asymmetric traveling salesman problem
• The asymmetric m-travelling salesman problem: A duality based branch-and- bound algorithm
• Transforming asymmetric into symmetric traveling salesman problems: Erratum
• The asymmetric bottleneck traveling salesman problem: algorithms, complexity and empirical analysis
• On the LP relaxation of the asymmetric traveling salesman path problem

zbMATH Keywords

Miller-Tucker-Zemlin constraintsLP relaxationasymmetric travelling salesman problem

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• An analytical comparison of different formulations of the travelling salesman problem
• Integer Programming Formulation of Traveling Salesman Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Title not available (Why is that?)
• Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with Hop constraints
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• A result on projection for the vehicle routing problem
• Facets of the Asymmetric Traveling Salesman Polytope
• A Polyhedral Approach to the Asymmetric Traveling Salesman Problem
• Classification of travelling salesman problem formulations
• Title not available (Why is that?)

Cited In (35)

• Formulations and valid inequalities for the heterogeneous vehicle routing problem
• Short combinatorial proof that the DFJ polytope is contained in the MTZ polytope for the asymmetric traveling salesman problem
• A Lagrangian Based Approach for the Asymmetric Generalized Traveling Salesman Problem
• Min-degree constrained minimum spanning tree problem: new formulation via Miller-Tucker-Zemlin constraints
• A comparative analysis of several asymmetric traveling salesman problem formulations
• New formulations for the hop-constrained minimum spanning tree problem via Sherali and Driscoll's tightened Miller-Tucker-Zemlin constraints
• On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems
• Precedence constrained generalized traveling salesman problem: polyhedral study, formulations, and branch-and-cut algorithm
• The effect of the asymmetry of road transportation networks on the traveling salesman problem
• Models for a Steiner multi-ring network design problem with revenues
• Vehicle routing with endogenous learning: application to offshore plug and abandonment campaign planning
• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• An efficient genetic algorithm for the traveling salesman problem with precedence constraints
• Formulations for the clustered traveling salesman problem with \(d\)-relaxed priority rule
• Models for a Steiner ring network design problem with revenues
• The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints
• Competitiveness based on logistic management: a real case study
• Compact formulations for multi-depot routing problems: theoretical and computational comparisons
• Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations
• A hybrid fuzzy-optimization approach to customer grouping-based logistics distribution operations
• Strong multi-commodity flow formulations for the asymmetric traveling salesman problem
• Selective routing problem with synchronization
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A conditional-logic interpretation for Miller-Tucker-Zemlin inequalities and extensions
• Requiem for the Miller-Tucker-Zemlin subtour elimination constraints?
• Optimal toll design: a lower bound framework for the asymmetric traveling salesman problem
• The asymmetric traveling salesman problem with replenishment arcs
• A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem
• Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems
• Compact vs. exponential-size LP relaxations
• Tight lower bounds for the traveling salesman problem with draft limits
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• New formulations of the hop-constrained minimum spanning tree problem via Miller-Tucker-Zemlin constraints
• Hop-indexed circuit-based formulations for the traveling salesman problem
• A Set Covering Approach for the Double Traveling Salesman Problem with Multiple Stacks

This page was built for publication: The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints

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