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

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

Zitieren Sie bitte immer diese 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.

Volltext Dateien herunterladen

Metadaten exportieren

Weitere Dienste

Teilen auf Twitter Suche bei Google Scholar Statistik - Anzahl der Zugriffe auf das Dokument
Metadaten
Verfasserangaben:Norbert Ascheuer, Matteo Fischetti, Martin Grötschel
Dokumentart:ZIB-Report
Datum der Erstveröffentlichung:28.02.1997
Schriftenreihe (Bandnummer):ZIB-Report (SC-97-11)
ZIB-Reportnummer:SC-97-11
Verlagspublikation: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.