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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Buchtitelbild

2013 | OriginalPaper | Buchkapitel

Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem

verfasst von : Mikhail Batsyn, Boris Goldengorin, Anton Kocheturov, Panos M. Pardalos

Erschienen in: Models, Algorithms, and Technologies for Network Analysis

Verlag: Springer New York

Einloggen

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

search-config
loading …

Abstract

In this chapter, we consider the asymmetric capacitated vehicle routing problem (ACVRP). We compare the search tree size and computational time for the bottleneck tolerance-based and cost-based branching rules within a branch-and-bound algorithm on the FTV benchmark instances. Our computational experiments show that the tolerance-based branching rule reduces the search tree size by 45 times and the CPU time by 2.8 times in average.

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

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

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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
Nächstes Kapitel Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times
Literatur
1.
Baldacci, R., Hadjiconstantinou, E., Mingozzi, A.: An exact algorithm for the capacitated vehicle routing problem based on a two-commodity network flow formulation. Oper. Res. 52, 723–738 (2004) MathSciNetCrossRefMATH
2.
Baldacci, R., Christofides, N., Mingozzi, A.: An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts. Math. Program., Ser. A 115(2), 351–385 (2008) MathSciNetCrossRefMATH
3.
Baldacci, R., Mingozzi, A., Roberti, R.: New route relaxation and pricing strategies for the vehicle routing problem. Oper. Res. 59(5), 1269–1283 (2011) MathSciNetCrossRefMATH
4.
Baldacci, R., Mingozzi, A., Roberti, R.: Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. Eur. J. Oper. Res. 218, 1–6 (2012) MathSciNetCrossRefMATH
5.
Fischetti, M., Toth, P., Vigo, D.: A branch-and-bound algorithm for the capacitated vehicle routing problem on directed graphs. Oper. Res. 42, 846–859 (1994) MathSciNetCrossRefMATH
6.
Fukasawa, R., Longo, H., Lysgaard, J., Poggi de Aragao, M., Reis, M., Uchoa, E., Werneck, R.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program., Ser. A 106, 491–511 (2006) MathSciNetCrossRefMATH
7.
Gal, T.T., Greenberg, H.J. (eds.): Advances in Sensitivity Analysis and Parametric Programming. Internat. Ser. Oper. Res. Management Sci., vol. 6. Kluwer Academic, Boston (1997) MATH
8.
Germs, R., Goldengorin, B., Turkensteen, M.: Lower tolerance-based Branch and Bound algorithms for the ATSP. Comput. Oper. Res. 39(2), 291–298 (2012) MathSciNetCrossRefMATH
9.
Golden, B.L., Raghavan, S., Wasil, E.A.: The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol. 43. Springer, New York (2008) CrossRef
10.
Goldengorin, B., Sierksma, G., Turkensteen, M.: Tolerance based algorithms for the ATSP. In: Lecture Notes in Computer Science, vol. 3353, pp. 222–234 (2004)
11.
Jonker, R., Volgenant, A.: A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing 38, 325–340 (1987) MathSciNetCrossRefMATH
12.
13.
Lysgaard, J., Letchford, A.N., Eglese, R.W.: A new branch-and-cut algorithm for the capacitated vehicle routing problem. Math. Program., Ser. A 100, 423–445 (2004) MathSciNetCrossRefMATH
14.
Pessoa, A., de Aragao, M.P., Uchoa, E.: Robust branch-cut-and-price algorithms for vehicle routing problems. In: Golden, B., Raghavan, S., Wasil, E. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces, vol. 43, pp. 297–325 (2008) CrossRef
15.
Toth, P., Vigo, D.: The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia (2002) CrossRefMATH
16.
Turkensteen, M., Ghosh, D., Goldengorin, B., Sierksma, G.: Tolerance-based branch and bound algorithms for the ATSP. Eur. J. Oper. Res. 189(3), 775–788 (2008) MathSciNetCrossRefMATH
17.
Vigo, D.: A heuristic algorithm for the asymmetric capacitated vehicle routing problem. Eur. J. Oper. Res. 89(1), 108–126 (1996) CrossRefMATH
18.
Metadaten
Titel
Tolerance-Based vs. Cost-Based Branching for the Asymmetric Capacitated Vehicle Routing Problem
verfasst von
Mikhail Batsyn
Boris Goldengorin
Anton Kocheturov
Panos M. Pardalos
Copyright-Jahr
2013
Verlag
Springer New York
Buch
Models, Algorithms, and Technologies for Network Analysis

Print ISBN: 978-1-4614-8587-2

Electronic ISBN: 978-1-4614-8588-9

Copyright-Jahr: 2013

DOI
https://doi.org/10.1007/978-1-4614-8588-9_1