Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations

DOI10.1016/J.COR.2014.05.014MaRDI QIDQ337114zbMATH OpenOpenAlexFDO

Authors Hanif D. Sherali, Jason D. Judd, Pei-Fang (Jennifer) Tsai, Subhash C. Sarin

Publication date 10 November 2016

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

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

zbMATH Keywords

precedence constraintsmultiple asymmetric traveling salesmen problemsequential ordering problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Software, source code, etc. for problems pertaining to operations research and mathematical programming (90-04)

Recommendations

• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem
• Strong multi-commodity flow formulations for the asymmetric traveling salesman problem
• A comparative analysis of several asymmetric traveling salesman problem formulations

Cites work

• scientific article; zbMATH DE number 3599820 (Why is no real title available?)
• A Cutting Planes Algorithm for the m-Salesmen Problem
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A classification of formulations for the (time-dependent) traveling salesman problem
• 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
• An Optimal Solution Method for Large-Scale Multiple Traveling Salesmen Problems
• Computational Experience with an M-Salesman Traveling Salesman Algorithm
• Exact algorithms for the vehicle routing problem, based on spanning tree and shortest path relaxations
• Improvements and extensions to Miller-Tucker-Zemlin subtour elimination constraints
• Improving Discrete Model Representations via Symmetry Considerations
• Integer Programming Formulation of Traveling Salesman Problems
• Integer linear programming formulations of multiple salesman problems and its variations
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Note—A Note on “The Formulation of the M-Salesman Traveling Salesman Problem”
• Preemptive and nonpreemptive multi-objective programming: Relationships and counterexamples
• Solution of a Large-Scale Traveling-Salesman Problem
• TSPLIB—A Traveling Salesman Problem Library
• Technical Note—An n-Constraint Formulation of the (Time-Dependent) Traveling Salesman Problem
• Technical Note—An Improved Transformation of the Symmetric Multiple Traveling Salesman Problem
• The Time-Dependent Traveling Salesman Problem and Its Application to the Tardiness Problem in One-Machine Scheduling
• The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints
• Transformation of Multisalesman Problem to the Standard Traveling Salesman Problem

Cited in

(8)

• On extended formulations for the precedence constrained asymmetric traveling salesman problem
• New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
• A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
• Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem
• The multiple Steiner TSP with order constraints: complexity and optimization algorithms
• Strong multi-commodity flow formulations for the asymmetric traveling salesman problem
• New formulation for the high multiplicity asymmetric traveling salesman problem with application to the Chesapeake problem
• Modeling and optimization of multiple traveling salesmen problems: an evolution strategy approach

Describes a project that uses

Uses Software

• TSPLIB
• VRP

This page was built for publication: Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations

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