Ir al contenido

Documat

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

  • Autores: Lorena Reyes Rubiano, Daniele Ferone, Ángel Alejandro Juan Pérez Árbol académico, Francisco Javier Faulín Fajardo Árbol académico
  • Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 43, Nº. 1, 2019, págs. 3-24
  • Idioma: inglés
  • DOI: 10.2436/20.8080.02.77
  • Enlaces
  • Resumen

    • 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.

  • Referencias bibliográficas
    • 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...
    • 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....
    • Bibri, S.E. and Krogstie, J. (2017). Smart sustainable cities of the future: An extensive interdisciplinary literature review. Sustainable...
    • Bozorgi, A.M., Farasat, M. and Mahmoud. (2017). A. A time and energy efficient routing algorithm for electric vehicles based on historical...
    • Bozorgi-Amiri, A., Jabalameli, M. and Al-e Hashem, S.M. (2013). A multi-objective robust stochastic programming model for disaster relief...
    • Cáceres-Cruz, J., Arias, P., Guimarans, D., Riera, D. and Juan, A.A. (2014). Rich vehicle routing problem: A survey. ACM Computing Surveys,...
    • Christofides, N. (1976). The vehicle routing problem. Revue française d’automatique, informatique, recherche opérationnelle. Recherche...
    • 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...
    • Demir, E., Bektaş, T. and Laporte, G. (2012). An adaptive large neighborhood search heuristic for the pollution-routing problem. European...
    • Desaulniers, G., Errico, F., Irnich, S. and Schneider, M. (2016). Exact algorithms for electric vehiclerouting problems with time windows....
    • Dominguez, O., Guimarans, D., Juan, A.A. and de la Nuez, I. (2016a). A biased-randomised large neighbourhood search for the two-dimensional...
    • Dominguez, O., Juan, A.A., Barrios, B., Faulin, J. and Agustin, A. (2016b). Using biased randomization for solving the two-dimensional loading...
    • Dominguez, O., Juan, A.A. and Faulin, J. (2014). A biased-randomized algorithm for the two-dimensional vehicle routing problem with and without...
    • Dominguez, O., Juan, A.A., de la Nuez Pestana, I.A. and Ouelhadj, D. (2016c). An ils-biased randomization algorithm for the two-dimensional...
    • Erdoğan, S. and Miller-Hooks, E. (2012). A green vehicle routing problem. Transportation Research Part E: Logistics and Transportation Review,...
    • Eshtehadi, R., Fathian, M. and Demir, E. (2017). Robust solutions to the pollution-routing problem with demand and travel time uncertainty....
    • 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...
    • Faulin, J. and Juan, A.A. (2008). The algacea-1 method for the capacitated vehicle routing problem. International Transactions in Operational...
    • Felipe, A., Ortuño, M.T., Righini, G. and Tirado, G. (2014). A heuristic approach for the green vehicle routing problem with multiple technologies...
    • Ferone, D., Gruler, A., Festa, P. and Juan, A.A. (2018). Enhancing and extending the classical GRASP framework with biased randomization and...
    • 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,...
    • Gonzalez-Neira, E.M., Ferone, D., Hatami, S. and Juan, A.A. (2017). A biased-randomized simheuristic for the distributed assembly permutation...
    • Grasas, A., Juan, A.A., Faulin, J., de Armas, J. and Ramalhinho, H. (2017). Biased randomization of heuristics using skewed probability distributions:...
    • Grasas, A., Juan, A.A. and Lourenço, HR. (2016). SimILS: a simulation-based extension of the iterated local search metaheuristic for stochastic...
    • Hiermann, G., Puchinger, J., Ropke, S. and Hartl, R.F. (2016). The electric fleet size and mix vehicle routing problem with time windows and...
    • Hof, J., Schneider, M. and Goeke, D. (2017). Solving the battery swap station location-routing problem with capacitated electric vehicles...
    • Juan, A.A., Faulin, J., Grasman, S., Riera, D., Marull, J. and Mendez, C. (2011a). Using safety stocks and simulation to solve the vehicle...
    • Juan, A.A., Faulin, J., Jorba, J., Caceres, J. and Marquès, J.M. (2013). Using parallel & distributed computing for real-time solving...
    • 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...
    • Juan, A.A., Faulin, J., Pérez-Bernabeu, E. and Jozefowiez, N. (2014a). Horizontal cooperation in vehicle routing problems with backhauling...
    • Juan, A.A., Goentzel, J. and Bektaş, T. (2014b). Routing fleets with multiple driving ranges: Is it possible to use greener fleet configurations?...
    • 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:...
    • 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...
    • Juan, A.A., Pascual, I., Guimarans, D. and Barrios, B. (2015). Combining biased randomization with iterated local search for solving the multidepot...
    • Koç, C. and Karaoglan, I. (2016). The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing Journal,...
    • Li, F., Golden, B. and Wasil, E. (2005). Very large-scale vehicle routing: New test problems, algorithms, and results. Computers and Operations...
    • 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...
    • McKinnon, A., Cullinane, S., Browne, M. and Whiteing, A. (2015). Green Logistics: Improving the Environmental Sustaintability of Logistics....
    • Pérez-Bernabeu, E., Juan, A.A., Faulin, J. and Barrios, B.B. (2015). Horizontal cooperation in road transportation: a case illustrating...
    • Ritzinger, U., Puchinger, J. and Hartl, R.F. (2015). A survey on dynamic and stochastic vehicle routing problems. International Journal of...
    • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017a). A multicriteria analysis for the green VRP: a case discussion for the distribution...
    • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017b). Multi-criteria optimization for fleet size with environmental aspects. Transportation...
    • Sawik, B., Faulin, J. and Pérez-Bernabeu, E. (2017c). Selected multi criteria green vehicle routing problems. In: Applications of Management...
    • Schneider, M., Stenger, A. and Goeke, D. (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation...
    • Schneider, M., Stenger, A. and Hof, J. (2015). An adaptive VNS algorithm for vehicle routing problems with intermediate stops. OR Spectrum,...
    • Serrano-Hernández, A., Juan, A.A., Faulin, J. and Perez-Bernabeu, E. (2017). Horizontal collaboration in freight transport: Concepts, benefits,...
    • Shao, S., Guan, W. and Bi. J. (2018). Electric vehicle-routing problem with charging demands and energy consumption. The Institute of Engineering...
    • The World Bank. (2018). Connecting to compete: trade logistics in the global economy. Technical Report; World Bank; Washington, DC. Available...
    • 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...
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno