Premium
A polyhedral study of the asymmetric traveling salesman problem with time windows
Author(s) -
Ascheuer Norbert,
Fischetti Matteo,
Grötschel Martin
Publication year - 2000
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/1097-0037(200009)36:2<69::aid-net1>3.0.co;2-q
Subject(s) - travelling salesman problem , digraph , polytope , convex hull , scheduling (production processes) , mathematical optimization , vehicle routing problem , mathematics , integer programming , regular polygon , combinatorics , branch and cut , path (computing) , computer science , routing (electronic design automation) , computer network , geometry , programming language
Abstract The asymmetric traveling salesman problem with time windows (ATSP‐TW) is a basic model for scheduling and routing applications. In this paper, we present a formulation of the problem involving only 0/1 variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time‐window restrictions are modeled using “infeasible path elimination” constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric traveling salesman problems are also described, along with a lifting theorem. We also study the ATSP‐TW polytope, P TW , defined as the convex hull of the integer solutions of our model. We show that determining the dimension of P TW is a strongly ‐complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for P TW . Computational experiments on the new formulation are reported in a companion paper, where we show that it outperforms alternative formulations on some classes of problem instances. © 2000 John Wiley & Sons, Inc.