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:
Toward Sustainable Logistics Kapitel lesen Erstes Kapitel lesen

2017 | OriginalPaper | Buchkapitel

Cumulative VRP: A Simplified Model of Green Vehicle Routing

verfasst von : Rishi Ranjan Singh, Daya Ram Gaur

Erschienen in: Sustainable Logistics and Transportation

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

There has been a recent resurge of interest in vehicle routing problems, especially in the context of green vehicle routing. One popular and simplified model is that of the cumulative vehicle routing problem. In this chapter, we examine the motivation, the definition, and the mixed integer linear program for the cumulative VRP. We review some of the recent results on approximation algorithms for the cumulative VRP. A column generation-based procedure for solving the cumulative VRP is also described. We also review approximation algorithms for a stochastic version of the cumulative VRP.

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 Transportation Network Regulation for Air Pollution Minimization
Nächstes Kapitel Constructive Algorithms for the Cumulative Vehicle Routing Problem with Limited Duration
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. C Emerg. Technol. 19(5), 741–750 (2011)CrossRef
3.
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. 115(2), 351–385 (2008)MathSciNetCrossRefMATH
4.
Beasley, J.E.: Route firstcluster second methods for vehicle routing. Omega 11(4), 403–408 (1983)CrossRef
5.
Bektaş, T., Demir, E., Laporte, G.: Green vehicle routing. In: Psaraftis, H.N. (ed.) Green Transportation Logistics, pp. 243–265. Springer, Cham (2016)CrossRef
6.
Bell, J.E., McMullen, P.R.: Ant colony optimization techniques for the vehicle routing problem. Adv. Eng. Inform. 18(1), 41–48 (2004)CrossRef
7.
Bertsimas, D.: Probabilistic combinatorial optimization problems. Ph.D. thesis, Massachusetts Institute of Technology (1988)
8.
9.
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
10.
Bjarnadóttir, Á.S.: Solving the vehicle routing problem with genetic algorithms. Ph.D. thesis, Technical University of Denmark (DTU), Lyngby (2004)
11.
Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, B., Raghavan, P., Sudan, M.: The minimum latency problem. In: Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, pp. 163–171. ACM (1994)
12.
13.
Bramel, J., Simchi-Levi, D.: Probabilistic analyses and practical algorithms for the vehicle routing problem with time windows. Oper. Res. 44(3), 501–509 (1996)CrossRefMATH
14.
Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp. 36–45. IEEE, Los Alamitos (2003)
15.
Chiang, W.C., Russell, R.A.: Simulated annealing metaheuristics for the vehicle routing problem with time windows. Ann. Oper. Res. 63(1), 3–27 (1996)CrossRefMATH
16.
Christofides, N.: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical report, DTIC Document (1976)
17.
Christofides, N., Mingozzi, A., Toth, P.: State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2), 145–164 (1981)MathSciNetCrossRefMATH
18.
Cinar, D., Gakis, K., Pardalos, P.M.: Reduction of CO2 emissions in cumulative multi-trip vehicle routing problems with limited duration. Environ. Model. Assess. 20(4), 273–284 (2015)CrossRef
19.
Cinar, D., Gakis, K., Pardalos, P.M.: A 2-phase constructive algorithm for cumulative vehicle routing problems with limited duration. Expert Syst. Appl. 56, 48–58 (2016)CrossRef
20.
Clarke, G., Wright, J.W.: Scheduling of vehicles from a central depot to a number of delivery points. Oper. Res. 12(4), 568–581 (1964)CrossRef
21.
Cordeau, J.F., Laporte, G.: Tabu search heuristics for the vehicle routing problem. In: Sharda, R., Alidaee, B., Rego, C., Voß, S. (eds.) Metaheuristic Optimization via Memory and Evolution, pp. 145–163. Springer, Boston (2005)CrossRef
22.
23.
Demir, E., Bektaş, T., Laporte, G.: A comparative analysis of several vehicle emission models for road freight transportation. Transp. Res. Part D: Transp. Environ. 16(5), 347–357 (2011)CrossRef
24.
Demir, E., Bektaş, T., Laporte, G.: An adaptive large neighborhood search heuristic for the pollution-routing problem. Eur. J. Oper. Res. 223(2), 346–359 (2012)MathSciNetCrossRefMATH
25.
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
26.
Erdoğan, S., Miller-Hooks, E.: A green vehicle routing problem. Transp. Res. Part E: Logist. Transp. Rev. 48(1), 100–114 (2012)CrossRef
27.
Fakcharoenphol, J., Harrelson, C., Rao, S.: The k-traveling repairman problem. In: Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 655–664. Society for Industrial and Applied Mathematics (2003)
28.
29.
Fukasawa, R., Longo, H., Lysgaard, J., de Aragão, M.P., Reis, M., Uchoa, E., Werneck, R.F.: Robust branch-and-cut-and-price for the capacitated vehicle routing problem. Math. Program. 106(3), 491–511 (2006)MathSciNetCrossRefMATH
30.
Fukasawa, R., He, Q., Song, Y.: A branch-cut-and-price algorithm for the energy minimization vehicle routing problem. Transp. Sci. 50(1), 23–34 (2015)CrossRef
31.
Gaur, D.R., Singh, R.R.: Cumulative vehicle routing problem: a column generation approach. In: Ganguly, S., Krishnamurti R. (eds.) Algorithms and Discrete Applied Mathematics, pp. 262–274. Springer, Cham (2015)
32.
Gaur, D.R., Singh, R.R.: A heuristic for cumulative vehicle routing using column generation. Discret. Appl. Math. 228, 140-157 (2016)MathSciNetCrossRefMATH
33.
34.
Gaur, D.R., Mudgal, A., Singh, R.R.: Approximation algorithms for cumulative VRP with stochastic demands. In: Govindarajan, S., Maheshwari A. (eds.) Algorithms and Discrete Applied Mathematics, pp. 176–189. Springer, Cham (2016)CrossRef
35.
Gendreau, M., Potvin, J.Y.: Handbook of Metaheuristics, vol. 2. Springer, New York (2010)CrossRefMATH
36.
Gendreau, M., Laporte, G., Séguin, R.: Stochastic vehicle routing. Eur. J. Oper. Res. 88(1), 3–12 (1996)CrossRefMATH
37.
Gendreau, M., Potvin, J.Y., Bräumlaysy, O., Hasle, G., Løkketangen, A.: Metaheuristics for the vehicle routing problem and its extensions: a categorized bibliography. In: Golden, B.L., Raghavan, S. (eds.) The Vehicle Routing Problem: Latest Advances and New Challenges, pp. 143–169. Springer, New York (2008)CrossRef
38.
Glover, F.W., Kochenberger, G.A.: Handbook of Metaheuristics, vol. 57. Springer Science & Business Media, New York (2006)MATH
39.
Gupta, A., Nagarajan, V., Ravi, R.: Technical note – approximation algorithms for VRP with stochastic demands. Oper. Res. 60(1), 123–127 (2012)MathSciNetCrossRefMATH
40.
Haimovich, M., Rinnooy Kan, A.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)MathSciNetCrossRefMATH
41.
Jabir, E., Panicker, V.V., Sridharan, R.: Multi-objective optimization model for a green vehicle routing problem. Procedia. Soc. Behav. Sci. 189, 33–39 (2015)CrossRef
42.
Jemai, J., Zekri, M., Mellouli, K.: An NSGA-II algorithm for the green vehicle routing problem. In: European Conference on Evolutionary Computation in Combinatorial Optimization, pp. 37–48. Springer, Berlin/Heidelberg (2012)
43.
Jin, M., Liu, K., Eksioglu, B.: A column generation approach for the split delivery vehicle routing problem. Oper. Res. Lett. 36(2), 265–270 (2008)MathSciNetCrossRefMATH
44.
Kara, I., Kara, B.Y., Yetis, M.K.: Energy minimizing vehicle routing problem. In: Combinatorial Optimization and Applications, pp. 62–71. Springer, Norwell (2007)
45.
Kara, İ., Kara, B.Y., Yetis, M.K.: Cumulative vehicle routing problems. In: Caric, T., Gold, H. (eds.) Vehicle Routing Problem, I-Tech, pp. 85–98 (2008)
46.
Kytöjoki, J., Nuortio, T., Bräysy, O., Gendreau, M.: An efficient variable neighborhood search heuristic for very large scale vehicle routing problems. Comput. Oper. Res. 34(9), 2743–2757 (2007)CrossRefMATH
47.
Laporte, G., Nobert, Y., Desrochers, M.: Optimal routing under capacity and distance restrictions. Oper. Res. 33(5), 1050–1073 (1985)MathSciNetCrossRefMATH
48.
Li, H., Lv, T., Li, Y.: The tractor and semitrailer routing problem with many-to-many demand considering carbon dioxide emissions. Transp. Res. Part D: Transp. Environ. 34, 68–82 (2015)CrossRef
49.
Liberatore, F., Righini, G., Salani, M.: A column generation algorithm for the vehicle routing problem with soft time windows. 4OR 9(1), 49–82 (2011)
50.
Lin, C., Choy, K.L., Ho, G.T., Chung, S., Lam, H.: Survey of green vehicle routing problem: past and future trends. Expert Syst. Appl. 41(4), 1118–1138 (2014)CrossRef
51.
Lysgaard, J., Wøhlk, S.: A branch-and-cut-and-price algorithm for the cumulative capacitated vehicle routing problem. Eur. J. Oper. Res. 236(3), 800–810 (2014)MathSciNetCrossRefMATH
52.
MirHassani, S., Mohammadyari, S.: Reduction of carbon emissions in VRP by gravitational search algorithm. Manag. Environ. Qual. Int. J. 25(6), 766–782 (2014)CrossRef
53.
Newman, P., Alimoradian, B., Lyons, T.: Estimating fleet fuel consumption for vans and small trucks. Transp. Sci. 23(1), 46–50 (1989)CrossRef
54.
Ocheni, S.I.: Impact of fuel price increaseon the Nigerian economy. Mediterr. J. Soc. Sci. 6(1 S1), 560 (2015)
55.
Park, Y., Chae, J.: A review of the solution approaches used in recent g-VRP (green vehicle routing problem). Int. J. Adv. Logist. 3(1-2), 27–37 (2014)CrossRef
56.
Potvin, J.Y.: Evolutionary Algorithms for Vehicle Routing. CIRRELT, Montreal (2007)
57.
Prins, C.: A simple and effective evolutionary algorithm for the vehicle routing problem. Comput. Oper. Res. 31(12), 1985–2002 (2004)MathSciNetCrossRefMATH
58.
Qureshi, A.G., Taniguchi, E., Yamada, T.: Column generation-based heuristics for vehicle routing problem with soft time windows. In: Proceedings of the Eastern Asia Society for Transportation Studies, vol. 2009, pp. 151–151. Eastern Asia Society for Transportation Studies (2009)
59.
Sahin, B., Yilmaz, H., Ust, Y., Guneri, A.F., Gulsun, B.: An approach for analysing transportation costs and a case study. Eur. J. Oper. Res. 193(1), 1–11 (2009)CrossRefMATH
60.
Santos, G.T., Cantao, L.A.P., Cantao, R.F.: Vehicle routing problem with fuel consumption minimization: a case study. In: Proceedings of the XVIII Latin-Iberoamerican Conference on Operations Research, CLAIO, pp. 802–809. IEEE (2016)
61.
Stewart, W.R., Golden, B.L.: Stochastic vehicle routing: a comprehensive approach. Eur. J. Oper. Res. 14(4), 371–385 (1983)CrossRefMATH
62.
Toro, E.M., Escobar, A.H., Granada, M.: Literature review on the vehicle routing problem in the green transportation context. revista. luna. azúl 42, 362–387 (2016)
63.
Toth, P., Vigo, D.: Branch-and-bound algorithms for the capacitated VRP. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, pp. 29–51. Society for Industrial and Applied Mathematics, Philadelphia (2001)
64.
Vaira, G., Dzemyda, G., Augutis, J., Barauskas, R., Kaklauskas, A., žilinskas, J., Bareiša, E., Marcinkevičius, V., Kurasova, O.: Genetic algorithm for vehicle routing problem. Ph.D. thesis, Vilniaus Universitetas (2014)
65.
Xiao, Y., Konak, A.: Green vehicle routing problem with time-varying traffic congestion. In: Proceedings of the 14th INFORMS Computing Society Conference, pp. 134–148 (2015)
66.
Xiao, Y., Konak, A.: A simulating annealing algorithm to solve the green vehicle routing & scheduling problem with hierarchical objectives and weighted tardiness. Appl. Soft Comput. 34, 372–388 (2015)CrossRef
67.
Xiao, Y., Konak, A.: The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transp. Res. Part E: Logist. Transp. Rev. 88, 146–166 (2016)CrossRef
68.
Xiao, Y., Zhao, Q., Kaku, I., Xu, Y.: Development of a fuel consumption optimization model for the capacitated vehicle routing problem. Comput. Oper. Res. 39(7), 1419–1431 (2012)MathSciNetCrossRefMATH
Metadaten
Titel
Cumulative VRP: A Simplified Model of Green Vehicle Routing
verfasst von
Rishi Ranjan Singh
Daya Ram Gaur
Copyright-Jahr
2017
Buch
Sustainable Logistics and Transportation

Print ISBN: 978-3-319-69214-2

Electronic ISBN: 978-3-319-69215-9

Copyright-Jahr: 2017

DOI
https://doi.org/10.1007/978-3-319-69215-9_3