A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times

  1. Lorena Reyes-Rubiano
  2. Daniele Ferone
  3. Angel A. Juan
  4. Javier Faulin
Journal:
Sort: Statistics and Operations Research Transactions

ISSN: 1696-2281

Year of publication: 2019

Volume: 43

Issue: 1

Pages: 3-24

Type: Article

DOI: 10.2436/20.8080.02.77 DIALNET GOOGLE SCHOLAR lock_openOpen access editor

More publications in: Sort: Statistics and Operations Research Transactions

Sustainable development goals

Abstract

Green transportation is becoming relevant in the context of smart cities, where the use of electric vehicles represents a promising strategy to support sustainability policies. However the use of electric vehicles shows some drawbacks as well, such as their limited driving-range capacity. This paper analyses a realistic vehicle routing problem in which both driving-range constraints and stochastic travel times are considered. Thus, the main goal is to minimize the expected time-based cost required to complete the freight distribution plan. In order to design reliable Routing plans, a simheuristic algorithm is proposed. It combines Monte Carlo simulation with a multi-start metaheuristic, which also employs biased-randomization techniques. By including simulation, simheuristics extend the capabilities of metaheuristics to deal with stochastic problems. A series of computational experiments are performed to test our solving approach as well as to analyse the effect of uncertainty on the routing plans.

View funding

Funding information

This work has been partially supported by the Spanish Ministry of Economy and Competitiveness (TRA2015-71883-REDT), and the Ibero-American Program for Science and Technology for Development (CYTED2014-515RT0489). Moreover, we appreciate the financial support of the Erasmus+ Program (2018-1-ES01-KA103-049767) as well as the support of the UPNA doctoral program.

Funders

    • CYTED2014-515RT0489
    • TRA2015-71883-REDT
  • Erasmus+ European Union
    • 2018-1-ES01-KA103-049767

Bibliographic References

  • Alvarez Fernandez, S., Ferone, D., Juan, A.A., Silva, D.G. and de Armas, J. (2018). A 2-stage biasedrandomized iterated local search for the uncapacitated single allocation p-hub median problem. Transactions on Emerging Telecommunications Technologies, 29, e3418.
  • Bektaş, T. and Laporte, G. (2011). The pollution-routing problem. Transportation Research Part B: Methodological, 45, 1232–50.
  • Bianchi, L., Dorigo, M., Gambardella, L.M. and Gutjahr, W.J. (2009). A survey on metaheuristics for stochastic combinatorial optimization. Natural Computing, 8, 239–87.
  • Bibri, S.E. and Krogstie, J. (2017). Smart sustainable cities of the future: An extensive interdisciplinary literature review. Sustainable Cities and Society, 31, 183–212.
  • Bozorgi, A.M., Farasat, M. and Mahmoud. (2017). A. A time and energy efficient routing algorithm for electric vehicles based on historical driving data. IEEE Transactions on Intelligent Vehicles, 2, 308– 20.
  • Bozorgi-Amiri, A., Jabalameli, M. and Al-e Hashem, S.M. (2013). A multi-objective robust stochastic programming model for disaster relief logistics under uncertainty. OR spectrum, 35, 905–33.
  • Cáceres-Cruz, J., Arias, P., Guimarans, D., Riera, D. and Juan, A.A. (2014). Rich vehicle routing problem: A survey. ACM Computing Surveys, 47, 1-28.
  • Christofides, N. (1976). The vehicle routing problem. Revue française d’automatique, informatique, recherche opérationnelle. Recherche opérationnelle, 10, 55–70.
  • Clarke, G. and Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12, 568–81.
  • De Armas, J., Juan, A.A., Marquès, J.M. and Pedroso, J.P. (2017). Solving the deterministic and stochastic uncapacitated facility location problem: from a heuristic to a simheuristic. Journal of the Operational Research Society, 68, 161–76.
  • Demir, E., Bektaş, T. and Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European Journal of Operational Research, 223, 346–59.
  • Desaulniers, G., Errico, F., Irnich, S. and Schneider, M. (2016). Exact algorithms for electric vehiclerouting problems with time windows. Operations Research, 64, 1388–1405.
  • Dominguez, O., Guimarans, D., Juan, A.A. and de la Nuez, I. (2016a). A biased-randomised large neighbourhood search for the two-dimensional vehicle routing problem with backhauls. European Journal of Operational Research, 255, 442–62.
  • Dominguez, O., Juan, A.A., Barrios, B., Faulin, J. and Agustin, A. (2016b). Using biased randomization for solving the two-dimensional loading vehicle routing problem with heterogeneous fleet. Annals of Operations Research, 236, 383–404.
  • Dominguez, O., Juan, A.A. and Faulin, J. (2014). A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without item rotations. International Transactions in Operational Research, 21, 375–98.
  • Dominguez, O., Juan, A.A., de la Nuez Pestana, I.A. and Ouelhadj, D. (2016c). An ils-biased randomization algorithm for the two-dimensional loading hfvrp with sequential loading and items rotation. Journal of the Operational Research Society, 67, 37–53.
  • Erdoğan, S. and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review, 48, 100–14.
  • Eshtehadi, R., Fathian, M. and Demir, E. (2017). Robust solutions to the pollution-routing problem with demand and travel time uncertainty. Transportation Research Part D: Transport and Environment, 51, 351–63.
  • Eurostat. Energy, transport and environment indicators (2016). Available at: http://ec.europa.eu (accessed August, 2018).
  • Faulin, J., Gilibert, M., Juan, A.A., Vilajosana, X. and Ruiz, R. (2008). Sr-1: A simulation-based algorithm for the capacitated vehicle routing problem. In: Simulation Conference, 2008. WSC 2008. Winter. IEEE, 2708–16.
  • Faulin, J. and Juan, A.A. (2008). The algacea-1 method for the capacitated vehicle routing problem. International Transactions in Operational Research, 15, 599–621.
  • Felipe, A., Ortuño, M.T., Righini, G. and Tirado, G. (2014). 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–28.
  • Ferone, D., Gruler, A., Festa, P. and Juan, A.A. (2018). Enhancing and extending the classical GRASP framework with biased randomization and simulation. Journal of the Operational Research Society.
  • Gendreau, M., Ghiani, G. and Guerriero, E. (2015). Time-dependent routing problems: A review. Computers & Operations Research, 64, 189–97.
  • Golden, B.L., Wasil, E.A., Kelly, J.P. and Chao, I.M. (1998). The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. In: Fleet management and logistics. Springer, 33–56.
  • Gonzalez-Neira, E.M., Ferone, D., Hatami, S. and Juan, A.A. (2017). A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic process-ing times. Simulation Modelling Practice and Theory, 79(Supplement C), 23–36. http://ec.europa.eu
  • Grasas, A., Juan, A.A., Faulin, J., de Armas, J. and Ramalhinho, H. (2017). Biased randomization of heuristics using skewed probability distributions: a survey and some applications. Computers & Industrial Engineering, 110, 216–28.
  • Grasas, A., Juan, A.A. and Lourenço, HR. (2016). SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic combinatorial optimization. Journal of Simulation, 10, 69– 77.
  • Hiermann, G., Puchinger, J., Ropke, S. and Hartl, R.F. (2016). The electric fleet size and mix vehicle routing problem with time windows and recharging stations. European Journal of Operational Research, 252, 995–1018.
  • Hof, J., Schneider, M. and Goeke, D. (2017). Solving the battery swap station location-routing problem with capacitated electric vehicles using an AVNS algorithm for vehicle-routing problems with intermediate stops. Transportation Research Part B, 97, 102–12.
  • Juan, A.A., Faulin, J., Grasman, S., Riera, D., Marull, J. and Mendez, C. (2011a). Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transportation Research Part C: Emerging Technologies, 19, 751–65.
  • Juan, A.A., Faulin, J., Jorba, J., Caceres, J. and Marquès, J.M. (2013). Using parallel & distributed computing for real-time solving of vehicle routing problems with stochastic demands. Annals of Operations Research, 207, 43–65.
  • Juan, A.A., Faulin, J., Jorba, J., Riera, D., Masip, D. and Barrios, B. (2011b). On the use of monte carlo simulation, cache and splitting techniques to improve the clarke and wright savings heuristics. Journal of the Operational Research Society, 62, 1085–97.
  • Juan, A.A., Faulin, J., Pérez-Bernabeu, E. and Jozefowiez, N. (2014a). Horizontal cooperation in vehicle routing problems with backhauling and environmental criteria. Procedia Social and Behavioral Sciences, 111, 1133–41.
  • Juan, A.A., Goentzel, J. and Bektaş, T. (2014b). Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations? Applied Soft Computing Journal, 21, 84–94.
  • Juan, A.A., Lourenço, H.R., Mateo, M., Luo, R. and Castella, Q. (2014c). Using iterated local search for solving the flow-shop problem: Parallelization, parametrization, and randomization issues. International Transactions in Operational Research, 21, 103–26.
  • Juan, A.A., Mendez, C.A., Faulin, J., De Armas, J. and Grasman, S.E. (2016). Electric vehicles in logistics and transportation: A survey on emerging environmental, strategic, and operational challenges. Energies, 9, 1–21.
  • Juan, A.A., Pascual, I., Guimarans, D. and Barrios, B. (2015). Combining biased randomization with iterated local search for solving the multidepot vehicle routing problem. International Transactions in Operational Research, 22, 647–67.
  • Koç, C. and Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing Journal, 39, 154–64.
  • Li, F., Golden, B. and Wasil, E. (2005). Very large-scale vehicle routing: New test problems, algorithms, and results. Computers and Operations Research, 32, 1165–79.
  • Lin, C., Choy, K.L., Ho, G.T.S., Chung, S.H. and Lam, H.Y. (2014). Survey of green vehicle routing problem: past and future trends. Expert Systems with Applications, 41(4 part 1), 1118–38.
  • McKinnon, A., Cullinane, S., Browne, M. and Whiteing, A. (2015). Green Logistics: Improving the Environmental Sustaintability of Logistics. 2nd ed. London: Kogan Page. ISBN: 978-0-7494-6625-1.
  • Pérez-Bernabeu, E., Juan, A.A., Faulin, J. and Barrios, B.B. (2015). Horizontal cooperation in road transportation: a case illustrating savings in distances and greenhouse gas emissions. International Transactions in Operational Research, 22, 585–606.
  • Ritzinger, U., Puchinger, J. and Hartl, R.F. (2015). A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research, 7543, 1–17.
  • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017a). A multicriteria analysis for the green VRP: a case discussion for the distribution problem of a Spanish retailer. Transportation Research Procedia, 22, 305–13.
  • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017b). Multi-criteria optimization for fleet size with environmental aspects. Transportation Research Procedia, 27, 61–8.
  • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017c). Selected multi criteria green vehicle routing problems. In: Applications of Management Science, 57–83.
  • Schneider, M., Stenger, A. and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48, 500–20.
  • Schneider, M., Stenger, A. and Hof, J. (2015). An adaptive VNS algorithm for vehicle routing problems with intermediate stops. OR Spectrum, 37, 353–87.
  • Serrano-Hernández, A., Juan, A.A., Faulin, J. and Perez-Bernabeu, E. (2017). Horizontal collaboration in freight transport: Concepts, benefits, and environmental challenges. Statistics and Operations Research Transactions, 41, 1–22.
  • Shao, S., Guan, W. and Bi. J. (2018). Electric vehicle-routing problem with charging demands and energy consumption. The Institute of Engineering and Technology, 12, 202–12.
  • The World Bank. (2018). Connecting to compete: trade logistics in the global economy. Technical Report; World Bank; Washington, DC. Available at: https://elibrary.worldbank.org/doi/abs/10.1596/29971 (accessed: August 2018).
  • Toth, P. and Vigo, D. (2014). Vehicle routing: problems, methods, and applications. SIAM.
  • Uchoa, E., Pecin, D., Pessoa, A., Poggi, M., Vidal, T. and Subramanian, A. (2017). New benchmark instances for the capacitated vehicle routing problem. European Journal of Operational Research, 257, 845–58. https://elibrary.worldbank.org/doi/abs/10.1596/29971
Data source: Dialnet