Abstract
This chapter (Supported by FAPESP (proc. 2015/11937-9, 2018/25950-5) and by CNPq (proc. 435520/2018-0, 140328/2021-1)) provides mathematical tools and insights for an effective modeling of Green Vehicle Routing Problems (G-VRPs). The G-VRP, inspired by the green logistics, is an NP-hard problem that generalizes the Vehicle Routing Problem (VRP) allowing electric vehicles with limited range to recharge at Alternative Fuel Stations (AFSs) and keep servicing customers. Several insights, properties, inequalities, and preprocessing rules are presented for the modeling of G-VRPs using integer linear programming. The proposed contributions may improve exact methodologies by strengthening their mathematical formulations. The provided contents require some basic background on linear and integer programming.
Similar content being viewed by others
References
J. Andelmin, E. Bartolini, An exact algorithm for the green vehicle routing problem. Transp. Sci. (2017). https://doi.org/10.1287/trsc.2016.0734
J. Andelmin, E. Bartolini, A multi-start local search heuristic for the Green Vehicle Routing Problem based on a multigraph reformulation. Comput. Oper. Res. (2019). https://doi.org/10.1016/j.cor.2019.04.018
M.D. Andrade, Formulations for the green vehicle routing problem. Institute of Computing, University of Campinas, Campinas, São Paulo (2020)
M.D. Andrade, F.L. Usberti, Valid Inequalities for the Green Vehicle Routing Problem. Anais do V Encontro de Teoria da Computação (2020). https://doi.org/10.5753/etc.2020.11086
M.D. Andrade, F.L. Usberti, Instance Generation Framework for Green Vehicle Routing (approved for publication). Special Volume of the AIRO Springer Series (2021a)
M.D. Andrade, F.L. Usberti, Combinatorial properties for the green vehicle routing problem (accepted for publication), in LAGOS 2021: XI Latin and American Algorithms, Graphs and Optimization Symposium (2021b)
R.K. Arakaki, L.P. Maziero, M.D. Andrade, V.M.F. Hama, F.L. Usberti, Routing electric vehicles with remote servicing. Model. Optim. Green Logist. (2020a). https://doi.org/10.1007/978-3-030-45308-4_8
R.K. Arakaki, L.P. Maziero, M.D. Andrade, F.L. Usberti, The electric capacitated covering tour problem (ECCTP), in Proceedings of the LI SBPO (Brazilian Symposium of Operations Research) (2020b). https://proceedings.science/sbpo-2019/papers/the-electric-capacitated-covering-tour-problem. Cited 26 Sep 2021
M. Asghari, S.M.J. Mirzapour Al-e-hashem, Green vehicle routing problem: a state-of-the-art review. Int. J. Prod. Econ. (2021). https://doi.org/10.1016/j.ijpe.2020.107899
P. Augerat, Polyhedral approach of the vehicle routing problem. Institut National Polytechnique de Grenoble – INPG (1995)
P. Bo, Z. Yuan, G. Yuvraj, C. Xiding, A memetic algorithm for the green vehicle routing problem. Sustainability (2019). https://doi.org/10.3390/su11216055
M. Bruglieri, S. Mancini, F. Pezzella, O. Pisacane, A path-based solution approach for the Green Vehicle Routing Problem. Comput. Oper. Res. (2019). https://doi.org/10.1016/j.cor.2018.10.019. https://tel.archives-ouvertes.fr/tel-00005026. Cited 01 Apr 2021
G. Ćirović, D. Pamuz̧ar, D. Božanić, Green logistic vehicle routing problem: routing light delivery vehicles in urban areas using a neuro-fuzzy model. Expert Syst. Appl. (2014). https://doi.org/10.1016/j.eswa.2014.01.005
R.G. Conrad, M.A. Figliozzi, The recharging vehicle routing problem, in Proceedings of the 2011 Industrial Engineering Research Conference (2011). https://doi.org/10.1016/j.cor.2016.03.013
K.N. Das, R. Das, Green vehicle routing problem: a critical survey. Intell. Tech. Appl. Sci. Technol. 736–745 (2020)
M. Drexl, M. Schneider, A survey of variants and extensions of the location-routing problem. Eur. J. Oper. Res. 283–308 (2015). https://doi.org/10.1016/j.ejor.2014.08.030
S. Ene, Í. Küçükoğlu, A. Aksoy, N. Öztürk, A hybrid metaheuristic algorithm for the green vehicle routing problem with a heterogeneous fleet. IJVD (2016). https://doi.org/10.1504/IJVD.2016.078771
S. Erdoǧan, E. Miller-Hooks, A green vehicle routing problem. Transp. Res. Part E: Logist. Transp. Rev. (2012). https://doi.org/10.1016/j.tre.2011.08.001
Á. Felipe, M.T. Ortuño, G. Righini, G. Tirado, A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transp. Res. Part E: Logist. Transp. Rev. (2014). https://doi.org/10.1016/j.tre.2014.09.003
J. Jemai, M. Zekri, K. Mellouli, An NSGA-II algorithm for the green vehicle routing problem, in Evolutionary Computation in Combinatorial Optimization (Springer, Berlin/New York, 2012), pp. 37–48
Y. Jun, S. Hao, Battery swap station location-routing problem with capacitated electric vehicles. Comput. Oper. Res. (2015). https://doi.org/10.1016/j.cor.2014.07.003
Ç. Koç, I. Karaoglan, The green vehicle routing problem: a heuristic based exact solution approach. Appl. Soft Comput. (2016). https://doi.org/10.1016/j.asoc.2015.10.064
M. Kuby, S. Lim, Location of alternative-fuel stations using the flow-refueling location model and dispersion of candidate sites on arcs. Netw. Spat. Econ. (2007). https://doi.org/10.1007/s11067-006-9003-6
V. Leggieri, M. Haouari, A practical solution approach for the green vehicle routing problem. Transp. Res. Part E: Logist. Transp. Rev. (2017). https://doi.org/10.1016/j.tre.2017.06.003
C. Lin, K.L. Choy, G.T.S. Ho, S.H. Chung, H.Y. Lam, Survey of Green Vehicle Routing Problem: past and future trends. Expert Syst. Appl. (2014). https://doi.org/10.1016/j.eswa.2013.07.107
S. Madankumar, C. Rajendran, Mathematical models for green vehicle routing problems with pickup and delivery: a case of semiconductor supply chain. Comput. Oper. Res. (2018). https://doi.org/10.1016/j.cor.2016.03.013
G. Poonthalir, R. Nadarajan, A Fuel Efficient Green Vehicle Routing Problem with varying speed constraint (F-GVRP). Expert Syst. Appl. (2018). https://doi.org/10.1016/j.eswa.2018.01.052
M. Schneider, A. Stenger, D. Goeke, The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci. (2014). https://doi.org/10.1287/trsc.2013.0490
P. Toth, D. Vigo, Vehicle Routing: Problems, Methods, and Applications (SIAM, Philadelphia, 2014)
Y.-W. Wang, C.-C. Lin, T.-J. Lee, Electric vehicle tour planning. Transp. Res. Part D Transp. Environ. (2018). https://doi.org/10.1016/j.trd.2018.04.016
C. Wu, T. Visutarrom, T. Chiang, Green vehicle routing problem: the tradeoff between travel distance and carbon emissions, in 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV) (2018). https://doi.org/10.1109/ICARCV.2018.8581240
Y. Xiao, A. Konak, The heterogeneous green vehicle routing and scheduling problem with time-varying traffic congestion. Transp. Res. Part E Logist. Transp. Rev. (2016). https://doi.org/10.1016/j.tre.2016.01.011
S. Yeh, An empirical analysis on the adoption of alternative fuel vehicles: the case of natural gas vehicles. Energy Policy. (2007). https://doi.org/10.1016/j.enpol.2007.06.012
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 Springer Nature Switzerland AG
About this entry
Cite this entry
Andrade, M.D., Arakaki, R.K., Usberti, F.L. (2022). A Brief Guide on the Modeling of Green Vehicle Routing Problems. In: Fathi, M., Zio, E., Pardalos, P.M. (eds) Handbook of Smart Energy Systems. Springer, Cham. https://doi.org/10.1007/978-3-030-72322-4_131-1
Download citation
DOI: https://doi.org/10.1007/978-3-030-72322-4_131-1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-72322-4
Online ISBN: 978-3-030-72322-4
eBook Packages: Springer Reference Economics and FinanceReference Module Humanities and Social SciencesReference Module Business, Economics and Social Sciences