Abstract
Electric Vehicles (EVs) are the future of transportation, but due to their battery and charging technology they cannot yet directly replace traditional vehicles. Nonetheless, EVs are a great option for city-logistics, due to the small distances and their zero local emissions. In this paper, a novel variant of the Electric Vehicle Routing Problem (EVRP), called Close-Open EVRP (COEVRP), is presented. It considers ending EV trips at Charging Stations, as opposed to other EVRP variants that only allow for en-route charging. This new variant follows a traditional routing scheme, allowing EVs to recharge only at the end of their route. The objective is to minimize energy consumption, as well as the number of vehicles. The energy consumption function takes into account the weight of the transported items. A mathematical formulation for the problem is presented and small instances were solved using a commercial solver. To solve larger instances, a hybrid metaheuristic combining Simulated Annealing and Variable Neighborhood Search algorithm was employed and thoroughly tested.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
Data Availability
The datasets generated during and/or analysed during the current study are available from the corresponding author on reasonable request.
References
Schrage, L.: Formulation and structure of more complex/realistic routing and scheduling problems. Networks 11(2), 229–232 (1981)
Sariklis, D., Powell, S.: A heuristic method for the open vehicle routing problem. Journal of the Operational Research Society 51(5), 564–573 (2000)
Brandão, J.: A tabu search algorithm for the open vehicle routing problem. European Journal of Operational Research 157(3), 552–564 (2004)
Tarantilis, C.D., Diakoulaki, D., Kiranoudis, C.T.: Combination of geographical information system and efficient routing algorithms for real life distribution operations. European Journal of Operational Research 152(2), 437–453 (2004)
Tarantilis, C.D., Ioannou, G., Kiranoudis, C.T., Prastacos, G.P.: A threshold accepting approach to the open vehicle routing problem. RAIRO-Operations Research 38(4), 345–360 (2004)
Tarantilis, C.D., Ioannou, G., Kiranoudis, C.T., Prastacos, G.P.: Solving the open vehicle routeing problem via a single parameter metaheuristic algorithm. Journal of the Operational research Society 56(5), 588–596 (2005)
Fu, Z., Eglese, R., Li, L.Y.: A new tabu search heuristic for the open vehicle routing problem. Journal of the operational Research Society 56(3), 267–274 (2005)
Aksen, D., Özyurt, Z., Aras, N.: Open vehicle routing problem with driver nodes and time deadlines. Journal of the Operational Research Society 58(9), 1223–1234 (2007)
Repoussis, P.P., Tarantilis, C.D., Ioannou, G.: The open vehicle routing problem with time windows. Journal of the Operational Research Society 58(3), 355–367 (2007)
Li, F., Golden, B., Wasil, E.: The open vehicle routing problem: Algorithms, large-scale test problems, and computational results. Computers & operations research 34(10), 2918–2930 (2007)
Letchford, A.N., Lysgaard, J., Eglese, R.W.: A branch-and-cut algorithm for the capacitated open vehicle routing problem. Journal of the Operational Research Society 58(12), 1642–1651 (2007)
Fleszar, K., Osman, I.H., Hindi, K.S.: A variable neighbourhood search algorithm for the open vehicle routing problem. European Journal of Operational Research 195(3), 803–809 (2009)
Derigs, U., Reuter, K.: A simple and efficient tabu search heuristic for solving the open vehicle routing problem. Journal of the Operational Research Society 60(12), 1658–1669 (2009)
Salari, M., Toth, P., Tramontani, A.: An ilp improvement procedure for the open vehicle routing problem. Computers & Operations Research 37(12), 2106–2120 (2010)
Zachariadis, E.E., Kiranoudis, C.T.: An open vehicle routing problem metaheuristic for examining wide solution neighborhoods. Computers & Operations Research 37(4), 712–723 (2010)
Repoussis, P.P., Tarantilis, C.D., Bräysy, O., Ioannou, G.: A hybrid evolution strategy for the open vehicle routing problem. Computers & Operations Research 37(3), 443–455 (2010)
Li, X., Leung, S.C., Tian, P.: A multistart adaptive memory-based tabu search algorithm for the heterogeneous fixed fleet open vehicle routing problem. Expert Systems with Applications 39(1), 365–374 (2012)
López-Sánchez, A., Hernández-Díaz, A.G., Vigo, D., Caballero, R., Molina, J.: A multi-start algorithm for a balanced real-world open vehicle routing problem. European Journal of Operational Research 238(1), 104–113 (2014)
Marinakis, Y., Marinaki, M.: A bumble bees mating optimization algorithm for the open vehicle routing problem. Swarm and Evolutionary Computation 15, 80–94 (2014)
Cao, E., Lai, M., Yang, H.: Open vehicle routing problem with demand uncertainty and its robust strategies. Expert Systems with Applications 41(7), 3569–3575 (2014)
Vincent, F.Y., Jewpanya, P., Redi, A.P.: Open vehicle routing problem with cross-docking. Computers & Industrial Engineering 94, 6–17 (2016)
Şevkli, A.Z., Güler, B.: A multi-phase oscillated variable neighbourhood search algorithm for a real-world open vehicle routing problem. Applied Soft Computing 58, 128–144 (2017)
Hosseinabadi, A.A.R., Vahidi, J., Balas, V.E., Mirkamali, S.S.: Ovrp gels: solving open vehicle routing problem using the gravitational emulation local search algorithm. Neural Computing and Applications 29(10), 955–968 (2018)
Lahyani, R., Gouguenheim, A.-L., Coelho, L.C.: A hybrid adaptive large neighbourhood search for multi-depot open vehicle routing problems. International Journal of Production Research 57(22), 6963–6976 (2019)
Shen, L., Tao, F., Wang, S.: Multi-depot open vehicle routing problem with time windows based on carbon trading. International journal of environmental research and public health 15(9), 2025 (2018)
Lalla-Ruiz, E., Mes, M.: Mathematical formulations and improvements for the multi-depot open vehicle routing problem. Optimization Letters 15(1), 271–286 (2021)
Ruiz, E., Soto-Mendoza, V., Barbosa, A.E.R., Reyes, R.: Solving the open vehicle routing problem with capacity and distance constraints with a biased random key genetic algorithm. Computers & Industrial Engineering 133, 207–219 (2019)
Atefi, R., Salari, M., Coelho, L.C., Renaud, J.: The open vehicle routing problem with decoupling points. European Journal of Operational Research 265(1), 316–327 (2018)
Soto, M., Sevaux, M., Rossi, A., Reinholz, A.: Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem. Computers & Industrial Engineering 107, 211–222 (2017)
Brandão, J.: A memory-based iterated local search algorithm for the multi-depot open vehicle routing problem. European Journal of Operational Research 284(2), 559–571 (2020)
Niu, Y., Yang, Z., Chen, P., Xiao, J.: Optimizing the green open vehicle routing problem with time windows by minimizing comprehensive routing cost. Journal of Cleaner Production 171, 962–971 (2018)
Liu, R., Jiang, Z., Hu, H., Yao, S.: A memetic algorithm for the close-open mixed vehicle routing problem. In: 2010 IEEE International Conference on Industrial Engineering and Engineering Management, pp. 728–732 (2010). IEEE
Liu, R., Jiang, Z.: The close-open mixed vehicle routing problem. European Journal of Operational Research 220(2), 349–360 (2012)
Brito, J., Expósito, A., Moreno, J.A.: Variable neighbourhood search for close-open vehicle routing problem with time windows. IMA Journal of Management Mathematics 27(1), 25–38 (2016)
Brito, J., Martínez, F.J., Moreno, J., Verdegay, J.L.: An aco hybrid metaheuristic for close-open vehicle routing problems with time windows and fuzzy constraints. Applied Soft Computing 32, 154–163 (2015)
Azadeh, A., Farrokhi-Asl, H.: The close-open mixed multi depot vehicle routing problem considering internal and external fleet of vehicles. Transportation Letters 11(2), 78–92 (2019)
Tavakkoli-Moghaddam, R., Meskini, M., Nasseri, H., Tavakkoli-Moghaddam, H.: A multi-depot close and open vehicle routing problem with heterogeneous vehicles. In: 2019 International Conference on Industrial Engineering and Systems Management (IESM), pp. 1–6 (2019). IEEE
Sun, G.-J.: Knowledge-guided neighborhood search algorithm for closeopen vehicle routing problem. In: Proceedings of the Seventh International Forum on Decision Sciences, pp. 157–163 (2020). Springer
Fernando, M., Thibbotuwawa, A., Perera, H.N., Ratnayake, R.C.: Closeopen mixed vehicle routing optimization model with multiple collecting centers to collect farmers’ perishable produce. In: 2022 International Conference for Advancement in Technology (ICONAT), pp. 1–8 (2022). IEEE
Conrad, R.G., Figliozzi, M.A.: The recharging vehicle routing problem. In: Proceedings of the 2011 Industrial Engineering Research Conference, p. 8 (2011). IISE Norcross, GA
Erdoğan, S., Miller-Hooks, E.: A green vehicle routing problem. Transportation research part E: logistics and transportation review 48(1), 100–114 (2012)
Schneider, M., Stenger, A., Goeke, D.: The electric vehicle-routing problem with time windows and recharging stations. Transportation Science 48(4), 500–520 (2014)
Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G.: A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E: Logistics and Transportation Review 71, 111–128 (2014)
Bruglieri, M., Pezzella, F., Pisacane, O., Suraci, S.: A variable neighborhood search branching for the electric vehicle routing problem with time windows. Electronic Notes in Discrete Mathematics 47, 221–228 (2015)
Keskin, M., Çatay, B.: Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies 65, 111–127 (2016)
Bruglieri, M., Mancini, S., Pezzella, F., Pisacane, O., Suraci, S.: A threephase matheuristic for the time-effective electric vehicle routing problem with partial recharges. Electronic Notes in Discrete Mathematics 58, 95–102 (2017)
Desaulniers, G., Errico, F., Irnich, S., Schneider, M.: Exact algorithms for electric vehicle-routing problems with time windows. Operations Research 64(6), 1388–1405 (2016)
Yavuz, M.: An iterated beam search algorithm for the green vehicle routing problem. Networks 69(3), 317–328 (2017)
Keskin, M., Çatay, B.: A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research 100, 172–188 (2018)
Ceselli, A., Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G.: A branchand-cut-and-price algorithm for the electric vehicle routing problem with multiple technologies. In: Operations Research Forum, vol. 2, pp. 1–33 (2021). Springer
Chakraborty, N., Mondal, A., Mondal, S.: Intelligent charge scheduling and eco-routing mechanism for electric vehicles: A multi-objective heuristic approach. Sustainable Cities and Society 69, 102820 (2021)
Montoya, A., Guéret, C., Mendoza, J.E., Villegas, J.G.: The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B: Methodological 103, 87–110 (2017)
Lee, C.: An exact algorithm for the electric-vehicle routing problem with nonlinear charging time. Journal of the Operational Research Society 72(7), 1461–1485 (2021)
Kancharla, S.R., Ramadurai, G.: Electric vehicle routing problem with non-linear charging and load-dependent discharging. Expert Systems with Applications 160, 113714 (2020)
Poonthalir, G., Nadarajan, R.: Green vehicle routing problem with queues. Expert Systems with Applications 138, 112823 (2019)
Keskin, M., Laporte, G., Çatay, B.: Electric vehicle routing problem with time-dependent waiting times at recharging stations. Computers & Operations Research 107, 77–94 (2019)
Keskin, M., Çatay, B., Laporte, G.: A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations. Computers & Operations Research 125, 105060 (2021)
Iwan, S., Nürnberg, M., Jedliński, M., Kijewska, K.: Efficiency of light electric vehicles in last mile deliveries-szczecin case study. Sustainable Cities and Society 74, 103167 (2021)
Xiao, Y., Zhang, Y., Kaku, I., Kang, R., Pan, X.: Electric vehicle routing problem: A systematic review and a new comprehensive model with nonlinear energy recharging and consumption. Renewable and Sustainable Energy Reviews 151, 111567 (2021)
Asghari, M., Al-e, S.M.J.M., et al.: Green vehicle routing problem: A state-of-the-art review. International Journal of Production Economics 231, 107899 (2021)
Moghdani, R., Salimifard, K., Demir, E., Benyettou, A.: The green vehicle routing problem: A systematic literature review. Journal of Cleaner Production 279, 123691 (2021)
Kar, S., Dutta, J., Barma, P.S., Mukherjee, A., De, T.: A hybrid multi-objective evolutionary algorithm for open vehicle routing problem through cluster primary-route secondary approach. International Journal of Management Science and Engineering Management, 1–15 (2022)
Jie, W., Yang, J., Zhang, M., Huang, Y.: The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology. European Journal of Operational Research 272(3), 879–904 (2019)
Kara, I., Kara, B.Y., Yetis, M.K.: Energy minimizing vehicle routing problem. In: International Conference on Combinatorial Optimization and Applications, pp. 62–71 (2007). Springer
Feo, T.A., Resende, M.G.: Greedy randomized adaptive search procedures. Journal of Global Optimization 6(2), 109–133 (1995)
Mladenović, N., Hansen, P.: Variable neighborhood search. Computers & operations research 24(11), 1097–1100 (1997)
Xiao, Y., Zhao, Q., Kaku, I., Mladenovic, N.: Variable neighbourhood simulated annealing algorithm for capacitated vehicle routing problems. Engineering Optimization 46(4), 562–579 (2014)
Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), 254–265 (1987)
Acknowledgements
The research work was supported by the Hellenic Foundation for Research and Innovation (HFRI) under the HFRI PhD Fellowship grant (Fellowship Number: 6334.)
Funding
Open access funding provided by HEAL-Link Greece.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Competing Interests
The authors declare that they have no competing interests.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Stamadianos, T., Kyriakakis, N.A., Marinaki, M. et al. A hybrid simulated annealing and variable neighborhood search algorithm for the close-open electric vehicle routing problem. Ann Math Artif Intell (2023). https://doi.org/10.1007/s10472-023-09858-x
Accepted:
Published:
DOI: https://doi.org/10.1007/s10472-023-09858-x