Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
EURO Journal on Transportation and Logistics
Erschienen in: EURO Journal on Transportation and Logistics 1-2/2012

01.06.2012 | Research Paper

Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison

verfasst von: Roberto Roberti, Paolo Toth

Erschienen in: EURO Journal on Transportation and Logistics | Ausgabe 1-2/2012

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This paper surveys the most effective mathematical models and exact algorithms proposed for finding the optimal solution of the well-known Asymmetric Traveling Salesman Problem (ATSP). The fundamental Integer Linear Programming (ILP) model proposed by Dantzig, Fulkerson and Johnson is first presented, its classical (assignment, shortest spanning r-arborescence, linear programming) relaxations are derived, and the most effective branch-and-bound and branch-and-cut algorithms are described. The polynomial ILP formulations proposed for the ATSP are then presented and analyzed. The considered algorithms and formulations are finally experimentally compared on a set of benchmark instances.
Vorheriger Artikel Conflict-free vehicle routing
Nächster Artikel Demand and capacity management in air transportation

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren
Literatur
Applegate D, Bixby R, Chvátal V, Cook W (2007) The traveling salesman problem: a computational study. Princeton series in applied mathematics. Princeton University Press, Princeton
Balas E (1989) The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph. SIAM J Discret Math 2(4):425–451CrossRef
Balas E (2000) Personal communication
Balas E, Christofides N (1981) A restricted Lagrangian approach to the traveling salesman problem. Math Programm Ser A 21(1):19–46CrossRef
Balas E, Fischetti M (1993) A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets. Math Programm Ser A 58(1-3):325–352CrossRef
Balas E, Toth P (1985) Branch and bound methods. In: Lawler E, Lenstra J, Rinnooy Kan A, Shmoys D (eds) The Traveling Salesman Problem: a guided tour of combinatorial optimization. Wiley, Chichester, pp 361–401
Bellmore M, Malone J (1971) Pathology of traveling-salesman subtour-elimination algorithms. Oper Res 19(2):278–307CrossRef
Carpaneto G, Toth P (1980) Some new branching and bounding criteria for the asymmetric travelling salesman problem. Manage Sci 26(7):736–743CrossRef
Carpaneto G, Toth P (1987) Primal-dual algorithms for the assignment problem. Discret Appl Math 18(2):137–153CrossRef
Carpaneto G, Dell’Amico M, Toth P (1995) Exact solution of large-scale asymmetric traveling salesman problems. ACM Transact Math Softw 21(4):394–409CrossRef
Claus A (1984) A new formulation for the travelling salesman problem. SIAM J Algebraic Discret Methods 5(1):21–25CrossRef
D’Ambrosio C, Lodi A, Martello S (2010) Combinatorial traveling salesman problem algorithms. In: Wiley encyclopedia of operations research and management science, vol 1. Wiley, New York, pp 738–747
Dantzig G, Fulkerson D, Johnson S (1954) Solutions of a large-scale traveling-salesman problem. Oper Res 2(4):393–410CrossRef
Desrochers M, Laporte G (1990) Improvements and extensions to the Miller–Tucker–Zemlin subtour elimination constraints. Oper Res Lett 10(1):27–36CrossRef
Edmonds J (1967) Optimum branchings. J Res Natl Bur Stand Sec B 71B(4):233–240
Finke G, Claus A, Gunn E (1984) A two commodity network flow approach to the travelling salesman problem. Congressus Numerantium 41:167–178
Fischetti M (1991) Facets of the asymmetric traveling salesman polytope. Math Oper Res 16(1):42–56CrossRef
Fischetti M, Toth P (1989) An additive bounding procedure for combinatorial optimization problems. Oper Res 37(2):319–328CrossRef
Fischetti M, Toth P (1992) An additive bounding procedure for the asymmetric travelling salesman problem. Math Program Ser A 53(1-3):173–197CrossRef
Fischetti M, Toth P (1993) An efficient algorithm for the min-sum arborescence problem. ORSA J Comput 5:426–434CrossRef
Fischetti M, Toth P (1997) A polyhedral approach to the asymmetric traveling salesman problem. Manage Sci 43(11):1520–1536CrossRef
Fischetti M, Lodi A, Martello S, Toth P (2001) A polyhedral approach to simplified crew scheduling and vehicle scheduling problems. Manage Sci 47(6):833–850CrossRef
Fischetti M, Lodi A, Toth P (2002) Exact methods for the asymmetric traveling salesman problem. In: Gutin G, Punnen A (eds) The traveling salesman problem and its variations. Kluwer Academic Publishers, The Netherlands, pp 169–205
Fischetti M, Lodi A, Toth P (2003) Solving real-world ATSP instances by branch-and-cut. Lecture Notes in Computer Science 2570 Combinatorial Optimization- Eureka, you shrink! Springer, Berlin, pp 64–77
Fox K, Gavish B, Graves S (1980) An n-constraint formulation of the (time-dependent) traveling salesman problem. Oper Res 28(4):1018–1021CrossRef
Garfinkel R (1973) On partitioning the feasible set in a branch-and-bound algorithm for the asymmetric traveling-salesman problem. Oper Res 21(1):340–343CrossRef
Gavish B, Graves S (1978) The travelling salesman problem and related problems, working Paper GR-078-78. Operations Research Center, Massachusetts Institute of Technology, Cambridge
Godinho MT, Gouveia L, Pesneau P (2011b) On a time-dependent flow-based formulation and an updated classification of formulations for the travelling salesman problem. In: Progress in combinatorial optimization, chap 7. Wiley, New York, pp 223–254
Gouveia L (1995) A result on projection for the vehicle routing problem. Eur J Oper Res 85(3):610–624CrossRef
Gouveia L, Pesneau P (2006) On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48(2):77–89CrossRef
Gouveia L, Pires J (1999) The asymmetric travelling salesman problem and a reformulation of the Miller–Tucker–Zemlin constraints. Eur J Oper Res 112:134–146CrossRef
Gouveia L, Pires J (2001) The asymmetric travelling salesman problem: on generalizations of disaggregated Miller–Tucker–Zemlin constraints. Discret Appl Math 112(1–3):129–145CrossRef
Gouveia L, Voss S (1995) A classification of formulations for the (time-dependent) travelling salesman problem. Eur J Oper Res 83(1):69–82CrossRef
Grötschel M, Padberg M (1985) Polyhedral theory. In: Lawler E, Lenstra J, Rinnooy Kan A, Shmoys D (eds) The Traveling Salesman Problem: A guided tour of combinatorial optimization. Wiley, Chichester, pp 251–305
Gutin G, Punnen A (2002) The traveling salesman problem and its variations. Kluwer, Dortrecht
Held M, Karp R (1970) The traveling-salesman problem and minimum spanning trees. Oper Res 18(6):1138–1162CrossRef
Held M, Karp R (1971) The traveling-salesman problem and minimum spanning trees: part ii. Math Program Ser A 1(1):6–25CrossRef
Jonker R, Volgenant T (1983) Transforming asymmetric into symmetric traveling salesman problems. Oper Res Lett 2(4):161–163CrossRef
Jünger M, Reinelt G, Rinaldi G (1995) The traveling salesman problem. In: Ball M, Magnanti T, Monma C, Nemhauser G (eds) Network models, handbooks in operations research and management science, vol 7. North Holland, Amsterdam, pp 255–330
Karp R (1972) Reducibility among combinatorial optimization problems. In: Miller R, Thatcher J (eds) Complexity of Computer Computations. Plenum Press, New York, pp 85–103
Karp R (1979) A patching algorithm for the nonsymmetric traveling-salesman problem. SIAM J Comput 8(4):561–573CrossRef
Langevin A (1988) Planification des tournées de véhicules. PhD thesis, École Polytechnique de Montréal, Montreal
Langevin A, Soumis F, Desrosiers J (1990) Classification of travelling salesman problem formulations. Oper Res Lett 9(2):127–132CrossRef
Lawler E (1976) Combinatorial optimization: networks and matroids. Holt, Rinehart and Winston, New York
Lawler E, Lenstra J, Rinnooy Kan A, Shmoys D (1985) The Traveling Salesman Problem: A guided tour of combinatorial optimization. Wiley, Chichester
Little J, Murty K, Sweeney D, Karel C (1963) An algorithm for the traveling salesman problem. Oper Res 11(6):972–989CrossRef
Loulou R (1988) On commodity flow formulations for the TSP, working paper. McGill University, Montréal
Miller C, Tucker A, Zemlin R (1960) Integer programming formulation of traveling salesman problems. J Ass Comput Mach 7(4):326–329CrossRef
Miller D, Pekny J (1989) Results from a parallel branch and bound algorithm for the asymmetric traveling salesman problem. Oper Res Lett 8(3):129–135CrossRef
Öncan T, Kuban Altinel I, Laporte G (2009) A comparative analysis of several asymmetric traveling salesman problem formulations. Comput Oper Res 36(3):637–654CrossRef
Padberg M, Rinaldi G (1990a) An efficient algorithm for the minimum capacity cut problem. Math Program Ser A 47(1–3):19–36CrossRef
Padberg M, Rinaldi G (1990b) Facet identification for the symmetric traveling salesman polytope. Math Program Ser A 47(1–3):219–257CrossRef
Padberg M, Sung T (1991) An analytical comparison of different formulations of the travelling salesman problem. Math Program Ser A 52(1–3):315–357CrossRef
Pekny J, Miller D (1992) A parallel branch and bound algorithm for solving large asymmetric traveling salesman problems. Math Program Ser A 55(1–3):17–33CrossRef
Pekny J, Miller D, Stodolsky D (1991) A note on exploiting the hamiltonian cycle problem substructure of the asymmetric traveling salesman problem. Oper Res Lett 10(3):173–176CrossRef
Reinelt G (1994) The traveling salesman problem: computational solutions for TSP applications. Lecture Notes in Computer Science. Springer, Berlin
Sarin S, Sherali H, Bhootra A (2005) New tighter polynomial length formulations for the asymmetric travelling salesman problem with and without precedence constraints. Oper Res Lett 33(1):62–70CrossRef
Sherali H, Driscoll P (2002) On tightening the relaxations of Miller–Tucker–Zemlin formulations for asymmetric traveling salesman problems. Operat Res 50(6):656–669CrossRef
Sherali H, Sarin S, Tsai PF (2006) A class of lifted path and flow-based formulations for the asymmetric travelling salesman problem with and without precedence constraints. Discret Optim 3(1):20–32CrossRef
Smith T, Srinivasan V, Thompson G (1977) Computational performance of three subtour elimination algorithms for solving asymmetric traveling salesman problems. In: PL Hammer BK EL Johnson, Nemhauser G (eds) Studies in Integer Programming, Annals of Discrete Mathematics, vol 1. Elsevier, Amsterdam, pp 495–506
Wong R (1980) Integer programming formulations of the traveling salesman problem. In: Proceedings of the IEEE international conference of circuits and computers, pp 149–152
Metadaten
Titel
Models and algorithms for the Asymmetric Traveling Salesman Problem: an experimental comparison
verfasst von
Roberto Roberti
Paolo Toth
Publikationsdatum
01.06.2012
Verlag
Springer-Verlag
Erschienen in
EURO Journal on Transportation and Logistics / Ausgabe 1-2/2012
Print ISSN: 2192-4376
Elektronische ISSN: 2192-4384
DOI
https://doi.org/10.1007/s13676-012-0010-0

Weitere Artikel der Ausgabe 1-2/2012

EURO Journal on Transportation and Logistics 1-2/2012 Zur Ausgabe

Research Paper

An elastic demand schedule-based multimodal assignment model for the simulation of high speed rail (HSR) systems

Editorial

Editorial

Research Paper

The potential of parsimonious models for understanding large scale transportation systems and answering big picture questions

Research Paper

Demand and capacity management in air transportation

Research Paper

Conflict-free vehicle routing

Research Paper

Transportation and vehicle fleet management in humanitarian logistics: challenges for future research

Premium Partner

    Bildnachweise