Abstract
This paper deals with the Green Electric Vehicle Routing Problem with Time Window and Mixed Fleet and presents a Mixed Integer Linear Programming formulation for it. Initially, we applied the CPLEX solver in this formulation. Then, to reduce the computational time, we used Local Branching and Variable Neighborhood Descent Branching (VNDB) methods. We did computational experiments with a simple adaptation of the 100-customers Solomon’s benchmark instances. The results showed that the three solution strategies reached the optimal solution. However, the running time of the VNDB is considerably smaller than those required by the other two solution methods. Therefore, this fact proves that the VNDB is the more efficient technique in the tested scenario.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Andelmin, J., Bartolini, E.: An exact algorithm for the green vehicle routing problem. Transp. Sci. 51(4), 1288–1303 (2017)
Bektaş, T., Laporte, G.: The pollution-routing problem. Transp. Res. Part B: Methodol. 45(8), 1232–1250 (2011)
Bruglieri, M., Pezzella, F., Pisacane, O., Suraci, S., et al.: A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electron. Notes Discret. Math. 47(15), 221–228 (2015)
Caceres-Cruz, J., Arias, P., Guimarans, D., Riera, D., Juan, A.A.: Rich vehicle routing problem: survey. ACM Comput. Surv. (CSUR) 47(2), 32 (2015)
Feng, W., Figliozzi, M.: An economic and technological analysis of the key factors affecting the competitiveness of electric commercial vehicles: a case study from the USA market. Transp. Res. Part C: Emerg. Technol. 26, 135–145 (2013)
Figliozzi, M.: Vehicle routing problem for emissions minimization. Transp. Res. Rec. 2197(1), 1–7 (2010)
Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1–3), 23–47 (2003)
Foroutan, R.A., Rezaeian, J., Mahdavi, I.: Green vehicle routing and scheduling problem with heterogeneous fleet including reverse logistics in the form of collecting returned goods. Appl. Soft Comput. 94(1568–4946), 106462 (2020)
Goeke, D., Schneider, M.: Routing a mixed fleet of electric and conventional vehicles. Eur. J. Oper. Res. 245(1), 81–99 (2015)
Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33(10), 3034–3045 (2006)
Hiermann, G., Puchinger, J., Ropke, S., Hartl, R.F.: The electric fleet size and mix vehicle routing problem with time windows and recharging stations. Eur. J. Oper. Res. 252(3), 995–1018 (2016)
Hung, Y.C., Michailidis, G.: Optimal routing for electric vehicle service systems. Eur. J. Oper. Res. 247(2), 515–524 (2015)
Juan, A., Mendez, C., Faulin, J., De Armas, J., Grasman, S.: Electric vehicles in logistics and transportation: a survey on emerging environmental, strategic, and operational challenges. Energies 9(2), 86 (2016)
Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M.M.: Vehicle routing problem with time windows. In: Desaulniers, G., Desrosiers, J., Solomon, M.M. (eds.) Column Generation, pp. 67–98. Springer, Boston (2005). https://doi.org/10.1007/0-387-25486-2_3
Koç, Ç., Karaoglan, I.: The green vehicle routing problem: a heuristic based exact solution approach. Appl. Soft Comput. 39, 154–164 (2016)
Lazić, J., Hanafi, S., Mladenović, N., Urošević, D.: Variable neighbourhood decomposition search for 0–1 mixed integer programs. Comput. Oper. Res. 37(6), 1055–1067 (2010)
Lin, C., Choy, K.L., Ho, G.T., Chung, S.H., Lam, H.: Survey of green vehicle routing problem: past and future trends. Expert Syst. Appl. 41(4), 1118–1138 (2014)
Macrina, G., Pugliese, L.D.P., Guerriero, F., Laporte, G.: The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Comput. Oper. Res. 101, 183–199 (2019)
Paz, J., Granada-Echeverri, M., Escobar, J.: The multi-depot electric vehicle location routing problem with time windows. Int. J. Ind. Eng. Comput. 9(1), 123–136 (2018)
Schiffer, M., Walther, G.: The electric location routing problem with time windows and partial recharging. Eur. J. Oper. Res. 260(3), 995–1013 (2017)
Schiffer, M., Walther, G.: An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transp. Sci. 52(2), 331–352 (2018)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35(2), 254–265 (1987)
Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. SIAM (2014)
Yu, Y., Wang, S., Wang, J., Huang, M.: A branch-and-price algorithm for the heterogeneous fleet green vehicle routing problem with time windows. Transp. Res. Part B: Methodol. 122, 511–527 (2019)
Acknowledgments
The authors thank the Brazilian agencies FAPEMIG (grant PPM-CEX 676/17), CNPq (grant 303266/2019-8) and CAPES, as well as the Federal Center for Technological Education of Minas Gerais (CEFET-MG) and the Federal University of Ouro Preto (UFOP) for supporting this study.
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Stehling, T.M., Freitas Souza, M.J., de Souza, S.R. (2021). Variable Neighborhood Descent Branching Applied to the Green Electric Vehicle Routing Problem with Time Window and Mixed Fleet. In: Mladenovic, N., Sleptchenko, A., Sifaleras, A., Omar, M. (eds) Variable Neighborhood Search. ICVNS 2021. Lecture Notes in Computer Science(), vol 12559. Springer, Cham. https://doi.org/10.1007/978-3-030-69625-2_2
Download citation
DOI: https://doi.org/10.1007/978-3-030-69625-2_2
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-69624-5
Online ISBN: 978-3-030-69625-2
eBook Packages: Computer ScienceComputer Science (R0)