Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Toward Sustainable Logistics Read chapter Read first chapter

2017 | OriginalPaper | Chapter

Cumulative VRP: A Simplified Model of Green Vehicle Routing

Authors : Rishi Ranjan Singh, Daya Ram Gaur

Published in: Sustainable Logistics and Transportation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now
previous chapter Transportation Network Regulation for Air Pollution Minimization
next chapter Constructive Algorithms for the Cumulative Vehicle Routing Problem with Limited Duration
Literature
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.
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.
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
Metadata
Title
Cumulative VRP: A Simplified Model of Green Vehicle Routing
Authors
Rishi Ranjan Singh
Daya Ram Gaur
Copyright Year
2017
Book
Sustainable Logistics and Transportation

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

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

Copyright Year: 2017

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

Premium Partner

    Image Credits