Abstract
Variable neighborhood searches and evolutionary techniques have shown their effectiveness when dealing with many combinatorial optimisation problems. This study proposes to combine these two techniques for addressing the routing problem using electric and modular vehicles. This is a recent problem that aims to overcome recharging battery constraints while maintaining a certain performance regarding to the fleet cost and the traveled distance. An experimental study on benchmark instances is provided to show the relevance of the proposed algorithm.
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
Aggoune-Mtalaa, W., Habbas, Z., Ait Ouahmed, A., Khadraoui, D.: Solving new urban freight distribution problems involving modular electric vehicles. IET Intell. Transp. Syst. 9(6), 654–661 (2015)
Baniamerian, A., Bashiri, M., Zabihi, F.: A modified variable neighborhood search hybridized with genetic algorithm for vehicle routing problems with cross-docking. Electron. Notes Discret. Math. 66, 143–150 (2018). 4th International Conference on Variable Neighborhood Search
Bennekrouf, M., Aggoune-Mtalaa, W., Sari, Z.: A generic model for network design including remanufacturing activities. Supply Chain Forum 14(2), 4–17 (2013)
Boudahri, F., Aggoune-Mtalaa, W., Bennekrouf, M., Sari, Z.: Application of a clustering based location-routing model to a real agri-food supply chain redesign. In: Nguyen, N., Trawiński, B., Katarzyniak, R., Jo, G.S. (eds.) Advanced Methods for Computational Collective Intelligence. Studies in Computational Intelligence, vol. 457, pp. 323–331. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-34300-1_31
Braÿsy, O., Gendreau, M.: Vehicle routing problem with time windows, Part I: route construction and local search algorithms. Transp. Sci. 39(1), 101–118 (2005)
Bruglieri, M., Pezzella, F., Pisacane, O., Suraci, S.: A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electron. Notes Discrete Math. 47, 221–228 (2015)
Bruglieri, M., Mancini, S., Pezzella, F., Pisacane, O., Suraci, S.: A three-phase matheuristic for the time-effective electric vehicle routing problem with partial recharges. Electron. Notes Discrete Math. 58, 95–102 (2017). 4th International Conference on Variable Neighborhood Search
Chen, B., Qu, R., Bai, R., Ishibuchi, H.: A variable neighbourhood search algorithm with compound neighbourhoods for VRPTW, pp. 25–35 (2016)
Chen, P., Huang, H., Dong, X.: Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem. Expert Syst. Appl. 37(2), 1620–1627 (2010)
Dantzig, G.B., Ramser, R.H.: The truck dispatching problem. Manag. Sci. 6, 80–91 (1959)
De Armas, J., Melián-Batista, B., Moreno-Pérez, J.A., Brito, J.: GVNS for a real-world rich vehicle routing problem with time windows. Eng. Appl. Artif. Intell. 42, 45–56 (2015)
Ferreira, H.S., Bogue, E.T., Noronha, T.F., Belhaiza, S., Prins, C.: Variable neighborhood search for vehicle routing problem with multiple time windows. Electron. Notes Discrete Math. 66, 207–214 (2018). 4th International Conference on Variable Neighborhood Search
Hansen, P., Mladenović, N., Todosijević, R., Hanafi, S.: Variable neighborhood search: basics and variants. EURO J. Comput. Optim. 5(3), 423–454 (2017)
Hiermann, G., Puchinger, J., 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)
Kubiak, M.: Distance measures and fitness-distance analysis for the capacitated vehicle routing problem. In: Doerner, K.F., Gendreau, M., Greistorfer, P., Gutjahr, W., Hartl, R.F., Reimann, M. (eds.) Metaheuristics. ORSIS, vol. 39, pp. 345–364. Springer, Boston, MA (2007). https://doi.org/10.1007/978-0-387-71921-4_18
Merz, P., Freisleben, B.: Fitness landscape analysis and memetic algorithms for the quadratic assignment problem. IEEE Trans. Evol. Comput. 4(4), 337–352 (2000)
Moura, A.: A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem. In: Bortfeldt, A., Homberger, J., Kopfer, H., Pankratz, G., Strangmeier, R. (eds.) Intelligent Decision Support, pp. 187–201. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-8349-9777-7_11
Mtalaa, W., Aggoune, R., Schaefers, J.: CO2 emissions calculation models for green supply chain management. In: Proceedings of POMS 20th Annual Meeting (2009). http://www.pomsmeetings.org/ConfProceedings/011/FullPapers/011-0590.pdf
Ombuki, B., Ross, B.J., Hanshar, F.: Multi-objective genetic algorithms for vehicle routing problem with time windows. Appl. Intell. 24, 17–30 (2006)
Rezgui, D., Aggoune-Mtalaa, W., Bouziri, H.: Towards the electrification of urban freight delivery using modular vehicles. In: 10th IEEE SOLI Conference, vol. 6, pp. 154–159 (2015)
Rezgui, D., Chaouachi Siala, J., Aggoune-Mtalaa, W., Bouziri, H.: Application of a memetic algorithm to the fleet size and mix vehicle routing problem with electric modular vehicles. GECCO (Companion) 6, 301–302 (2017)
Rezgui, D., Siala, J.C., Aggoune-Mtalaa, W., Bouziri, H.: Towards smart urban freight distribution using fleets of modular electric vehicles. In: Ben Ahmed, M., Boudhir, A.A. (eds.) SCAMS 2017. LNNS, vol. 37, pp. 602–612. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-74500-8_55
Schneider, M., Stenger, A., Goeke, D.: The electric vehicle-routing problem with time windows and recharging stations. Transp. Sci. 48(4), 500–520 (2014)
Schneider, M.: The vehicle-routing problem with time windows and driver-specific times. Eur. J. Oper. Res. 250(1), 101–119 (2016)
Serrano, C., Aggoune-Mtalaa, W., Sauer, N.: Dynamic models for green logistic networks design. IFAC Proc. Vol. (IFAC-PapersOnline) 46(9), 736–741 (2013)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper. Res. 35, 254–265 (1987)
Ursani, Z., Essam, D., Cornforth, D., Stocker, R.: Localized genetic algorithm for vehicle routing problem with time windows. Appl. Soft Comput. 11, 5375–5390 (2011)
Van Duin, J.H., Tavasszy, L.A., Quak, H.J.: Towards electric-urban freight: first promising steps in the electric vehicle revolution. Eur. Transp. 54(9), 1–19 (2013)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer Nature Switzerland AG
About this paper
Cite this paper
Rezgui, D., Bouziri, H., Aggoune-Mtalaa, W., Siala, J.C. (2019). An Evolutionary Variable Neighborhood Descent for Addressing an Electric VRP Variant. In: Sifaleras, A., Salhi, S., Brimberg, J. (eds) Variable Neighborhood Search. ICVNS 2018. Lecture Notes in Computer Science(), vol 11328. Springer, Cham. https://doi.org/10.1007/978-3-030-15843-9_17
Download citation
DOI: https://doi.org/10.1007/978-3-030-15843-9_17
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-15842-2
Online ISBN: 978-3-030-15843-9
eBook Packages: Computer ScienceComputer Science (R0)