Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

A polyhedral study of the asymmetric travelling salesman problem with time windows

Please always quote using this URN: urn:nbn:de:0297-zib-2807
  • The asymmetric travelling 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 modelled by means of ``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 travelling 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 strongly {\em NP}--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 [1997] where we show that it outperforms alternative formulations on some classes of problem instances.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Author:Norbert Ascheuer, Matteo Fischetti, Martin Grötschel
Document Type:ZIB-Report
Date of first Publication:1997/02/28
Series (Serial Number):ZIB-Report (SC-97-11)
Published in:Appeared in: Networks 36 (2000) pp. 69-79
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.