ZIB

Treffer pro Seite

Treffer 1 - 2 | 2 Treffer

Sortierung

Digitale Medien

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints (2000)

Ascheuer, Norbert ; Jünger, Michael ; Reinelt, Gerhard

Springer

Computational optimization and applications 17 (2000), S. 61-84

zur Merkliste hinzufügen auf der Merkliste

Details

ISSN: 1573-2894

Schlagwort(e): asymmetric traveling salesman problem ; precedence constraints ; branch&cut

Quelle: Springer Online Journal Archives 1860-2000

Thema: Informatik

Notizen: Abstract In this article we consider a variant of the classical asymmetric traveling salesman problem (ATSP), namely the ATSP in which precedence constraints require that certain nodes must precede certain other nodes in any feasible directed tour. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing (Timlin, Master's Thesis, Department of Combinatorics and Optimization, University of Waterloo, 1989), sequencing in flexible manufacturing (Ascheuer et al., Integer Programming and Combinatorial Optimization, University of Waterloo, Waterloo, 1990, pp. 19–28; Idem., SIAM Journal on Optimization, vol. 3, pp. 25–42, 1993), to stacker crane routing in an automatic storage system (Ascheuer, Ph.D. Thesis, Tech. Univ. Berlin, 1995). We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&cut-algorithm and give computational results on real-world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances with more than 200 nodes can be solved to optimality within a few minutes of CPU-time. As a side product we obtain a branch&cut-algorithm for the ATSP. All instances in TSPLIB can be solved to optimality in a reasonable amount of computation time.

Materialart: Digitale Medien

URL: http://dx.doi.org/10.1023/A:1008779125567

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

Artikel (Nationallizenzen)

Volltext

Unbekannt

A Branch & Cut Algorithm for the Asymmetric Traveling Salesman Problem with Precedence Constraints (1997)

Ascheuer, Norbert ; Jünger, Michael ; Reinelt, Gerhard

zur Merkliste hinzufügen auf der Merkliste

Details

Publikationsdatum: 2020-08-05

Beschreibung: In this paper we consider a variant of the classical ATSP, namely the asymmetric Hamiltonian path problem (or equivalently ATSP) with precedence constraints. In this problem precedences among the nodes are present, stating that a certain node has to precede others in any feasible sequence. This problem occurs as a basic model in scheduling and routing and has a wide range of applications varying from helicopter routing[Timlin89], sequencing in flexible manufacturing [AscheuerEscuderoGroetschelStoer90,AscheuerEscuderoGroetschelStoer93], to stacker crane routing in an automatic storage system[Ascheuer95]. We give an integer programming model and summarize known classes of valid inequalities. We describe in detail the implementation of a branch&-cut algorithm and give computational results on real world instances and benchmark problems from TSPLIB. The results we achieve indicate that our implementation outperforms other implementations found in the literature. Real world instances up to 174 nodes could be solved to optimality within a few minutes of CPU-time. As a side product we obtained a branch&cut-algorithm for the ATSP. All instances in TSPLIB could be solved to optimality in a reasonable amount of computing time.

Schlagwort(e): ddc:000

Sprache: Englisch

Materialart: reportzib , doc-type:preprint

Format: application/postscript

Format: application/pdf

Permalink

Bibliothek	Standort	Signatur	Band/Heft/Jahr	Verfügbarkeit

Andere fanden auch interessant ...

OPUS

PDF

Überblick

Treffer 1 - 2 | 2 Treffer