A Polyhedral Approach to the Asymmetric Traveling Salesman Problem

DOI10.1287/mnsc.43.11.1520zbMath0902.90159OpenAlexW2033789385MaRDI QIDQ4392516

Paolo Toth, Matteo Fischetti

Publication date: 8 June 1998

Published in: Management Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/mnsc.43.11.1520

zbMATH Keywords

branch-and-boundbranch-and-cutasymmetric traveling salesmanfacet-defining cuts

Mathematics Subject Classification ID

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

Related Items (31)

Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem ⋮ A branch-and-cut framework for the consistent traveling salesman problem ⋮ Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs ⋮ The traveling purchaser problem, with multiple stacks and deliveries: a branch-and-cut approach ⋮ A threshold accepting heuristic with intense local search for the solution of special instances of the traveling salesman problem ⋮ SelfSplit parallelization for mixed-integer linear programming ⋮ A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs ⋮ Solving the asymmetric traveling purchaser problem ⋮ Exact and heuristic dynamic programming algorithms for the traveling salesman problem with flexible time windows ⋮ Search and delivery man problems: when are depth-first paths optimal? ⋮ A column generation algorithm for the demand‐responsive feeder service with mandatory and optional, clustered bus‐stops ⋮ A solution approach for multi‐trip vehicle routing problems with time windows, fleet sizing, and depot location ⋮ Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem ⋮ An asymmetric traveling salesman problem based matheuristic algorithm for flowshop group scheduling problem ⋮ New cutting-planes for the time- and/or precedence-constrained ATSP and directed VRP ⋮ A Column Generation Model for a Scheduling Problem with Maintenance Constraints ⋮ Combined route capacity and route length models for unit demand vehicle routing problems ⋮ A branch-and-cut algorithm for a production scheduling problem with sequence-dependent and time-dependent setup times ⋮ An asymmetric TSP with time windows and with time-dependent travel times and costs: an exact solution through a graph transformation ⋮ Determination of the candidate arc set for the asymmetric traveling salesman problem ⋮ The weighted arborescence constraint ⋮ A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints ⋮ The asymmetric travelling salesman problem: on generalizations of disaggregated Miller-Tucker-Zemlin constraints ⋮ A polyhedral study of the asymmetric traveling salesman problem with time windows ⋮ A personalized walking bus service requiring optimized route decisions: a real case ⋮ The asymmetric travelling salesman problem and a reformulation of the Miller-Tucker-Zemlin constraints ⋮ Asymmetric Multidepot Vehicle Routing Problems: Valid Inequalities and a Branch-and-Cut Algorithm ⋮ Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems ⋮ A branch-and-cut algorithm for multiple sequence alignment ⋮ A note on the separation of subtour elimination constraints in elementary shortest path problems ⋮ A genetic algorithm with a mixed region search for the asymmetric traveling salesman problem

Uses Software

• Unnamed Item

This page was built for publication: A Polyhedral Approach to the Asymmetric Traveling Salesman Problem