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:
Randomization for Efficient Dynamic Graph Algorithms Kapitel lesen Erstes Kapitel lesen

2016 | OriginalPaper | Buchkapitel

Approximation Algorithms for Cumulative VRP with Stochastic Demands

verfasst von : Daya Ram Gaur, Apurva Mudgal, Rishi Ranjan Singh

Erschienen in: Algorithms and Discrete Applied Mathematics

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper we give randomized approximation algorithms for stochastic cumulative VRPs for split and unsplit deliveries. The approximation ratios are \(2(1+\alpha )\) and 7 respectively, where \(\alpha \) is the approximation ratio for the metric TSP. The approximation factor is further reduced for trees and paths. These results extend the results in [Technical note - approximation algorithms for VRP with stochastic demands. Operations Research, 2012] and [Routing vehicles to minimize fuel consumption. Operations Research Letters, 2013].

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
Vorheriges Kapitel AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables
Nächstes Kapitel Some Distance Antimagic Labeled Graphs
Literatur
1.
Altinkemer, K., Gavish, B.: Heuristics for unequal weight delivery problems with a fixed error guarantee. Oper. Res. Lett. 6(4), 149–158 (1987)MathSciNetCrossRefMATH
2.
Archetti, C., Feillet, D., Gendreau, M., Speranza, M.G.: Complexity of the VRP and SDVRP. Transp. Res. Part C. 19(5), 741–750 (2011)CrossRef
3.
Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM (JACM) 45(5), 753–782 (1998)MathSciNetCrossRefMATH
4.
Bertsimas, D.: Probabilistic combinatorial optimization problems. Ph.D. thesis, Massachusetts Institute of Technology (1988)
5.
6.
Bertsimas, D.J., Simchi-Levi, D.: A new generation of vehicle routing research: robust algorithms, addressing uncertainty. Oper. Res. 44(2), 286–304 (1996)CrossRefMATH
7.
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document (1976)
8.
9.
Demir, E., Bektaş, T., Laporte, G.: A review of recent research on green road freight transportation. Eur. J. Oper. Res. 237(3), 775–793 (2014)CrossRefMATH
10.
11.
Gaur, D.R., Singh, R.R.: Cumulative vehicle routing problem: a column generation approach. In: Ganguly, S., Krishnamurti, R. (eds.) CALDAM 2015. LNCS, vol. 8959, pp. 262–274. Springer, Heidelberg (2015)
12.
Gendreau, M., Laporte, G., Séguin, R.: Stochastic vehicle routing. Eur. J. Oper. Res. 88(1), 3–12 (1996)CrossRefMATH
13.
14.
Gupta, A., Nagarajan, V., Ravi, R.: Technical note - approximation algorithms for VRP with stochastic demands. Oper. Res. 60(1), 123–127 (2012)MathSciNetCrossRefMATH
15.
Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)MathSciNetCrossRefMATH
16.
Kara, I., Kara, B.Y., Yetis, M.K.: Energy minimizing vehicle routing problem. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA 2007. LNCS, vol. 4616, pp. 62–71. Springer, Heidelberg (2007)CrossRef
17.
Kara, I., Kara, B.Y., Yetis, M.K.: Cumulative vehicle routing problems. In: Vehicle Routing Problem, pp. 85–98 (2008)
18.
Labbé, M., Laporte, G., Mercure, H.: Capacitated vehicle routing on trees. Oper. Res. 39(4), 616–622 (1991)CrossRefMATH
19.
Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, k-MST, and related problems. SIAM J. Comput. 28(4), 1298–1309 (1999)MathSciNetCrossRefMATH
20.
Stewart, W.R., Golden, B.L.: Stochastic vehicle routing: a comprehensive approach. Eur. J. Oper. Res. 14(4), 371–385 (1983)CrossRefMATH
21.
Xiao, Y., Zhao, Q., Kaku, I., Yuchun, X.: Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Comput. Oper. Res. 39(7), 1419–1431 (2012)MathSciNetCrossRefMATH
Metadaten
Titel
Approximation Algorithms for Cumulative VRP with Stochastic Demands
verfasst von
Daya Ram Gaur
Apurva Mudgal
Rishi Ranjan Singh
Copyright-Jahr
2016
Verlag
Springer International Publishing
Buch
Algorithms and Discrete Applied Mathematics

Print ISBN: 978-3-319-29220-5

Electronic ISBN: 978-3-319-29221-2

Copyright-Jahr: 2016

DOI
https://doi.org/10.1007/978-3-319-29221-2_15