Green hybrid fleets using electric vehiclessolving the heterogeneous vehicle routing problem with multiple driving ranges and loading capacities

  1. Sara Hatami 1
  2. Majid Eskandarpour 2
  3. Manuel Chica
  4. Angel A. Juan 1
  5. Djamila Ouelhadj 3
  1. 1 Universitat Oberta de Catalunya
    info

    Universitat Oberta de Catalunya

    Barcelona, España

    ROR https://ror.org/01f5wp925

  2. 2 Universit´e de Lille
  3. 3 University of Portsmouth
    info

    University of Portsmouth

    Portsmouth, Reino Unido

    ROR https://ror.org/03ykbk197

Mostrar afiliaciones +
Revista:
Sort: Statistics and Operations Research Transactions

ISSN: 1696-2281

Año de publicación: 2020

Volumen: 44

Número: 1

Páginas: 141-170

Tipo: Artículo

DOI: 10.2436/20.8080.02.98 DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Sort: Statistics and Operations Research Transactions

Resumen

The introduction of Electric Vehicles (EVs) in modern fleets facilitates green road transportation. However, the driving ranges of EVs are limited by the duration of their batteries, which arise new operational challenges. Hybrid fleets of gas and EVs might be heterogeneous both in loading capacities as well as in driving-range capabilities,whichmakes the design of efficient routing plans a difficult task. In this paper, we propose a newMulti-Round IteratedGreedy (MRIG) metaheuristic to solve the Heterogeneous Vehicle Routing Problem with Multiple Driving ranges and loading capacities (HeVRPMD). MRIG uses a successive approximations method to offer the decision maker a set of alternative fleet configurations,with different distance-based costs and green levels. The numerical experiments show that MRIG is able to outperform previous works dealing with the homogeneous version of the problem, which assumes the same loading capacity for all vehicles in the fleet. The numerical experiments also confirm that the proposed MRIG approach extends previous works by solving a more realistic HeVRPMD and provides the decision-maker with fleets with higher green levels.

€ Ver financiación

Información de financiación

This work is jointly supported by the Spanish Ministry of Science (RED2018-102642-T), the Andalusian Government, the National Agency for Research Funding AEI, and ERDF (EU) under grants EXASOCO (PGC2018-101216-B-I00), AIMAR (A-TIC-284-UGR18), SIMARK (PY18-4475) and the Ramón y Cajal program (RYC-2016-19800).

Financiadores

Referencias bibliográficas

  • AbdAllah, A. M. F., D. L. Essam, and R. A. Sarker (2017). On solving periodic re-optimization dynamic vehicle routing problems. Applied Soft Computing, 55, 1–12.
  • Achtnicht, M., G. Bühler, and C. Hermeling (2012). The impact of fuel availability on demand for alternative-fuel vehicles. Transportation Research Part D: Transport and Environment, 17, 262–269.
  • Almouhanna, A., C. L. Quintero-Araujo, J. Panadero, A. A. Juan, B. Khosravi, and D. Ouelhadj (2020). The location routing problem using electric vehicles with constrained distance. Computers & Operations Research, 115, 104864.
  • Andreatta, G., M. Casula, C. De Francesco, and L. De Giovanni (2016). A branch-and-price based heuristic for the stochastic vehicle routing problem with hard time windows. Electronic Notes in Discrete Mathematics, 52, 325–332.
  • Baldacci, R., M. Battarra, and D. Vigo (2008). Routing a heterogeneous fleet of vehicles. In The Vehicle Routing Problem: Latest Advances and New Challenges, Chapter 10, pp. 3–27. Springer.
  • Belloso, J., A. A. Juan, and J. Faulin (2019). An iterative biased-randomized heuristic for the fleet size and mix vehicle-routing problem with backhauls. International Transactions in Operational Research, 26, 289–301.
  • Brito, J., F. J. Martı́nez, J. A. Moreno, and J. L. Verdegay (2015). An ACO hybrid metaheuristic for close– open vehicle routing problems with time windows and fuzzy constraints. Applied Soft Computing, 32, 154–163.
  • Calvet, L., A. A. Juan, C. Serrat, and J. Ries (2016). A statistical learning based approach for parameter fine-tuning of metaheuristics. SORT-Statistics and Operations Research Transactions, 40, 201–224.
  • Chan, C. C., Y. S. Wong, A. Bouscayrol, and K. Chen (2009). Powering Sustainable Mobility: Roadmaps of Electric, Hybrid, and Fuel Cell Vehicles. Proceedings of the IEEE, 97, 603–607.
  • Chebbi, O. and J. Chaouachi (2015). Multi-objective Iterated Greedy Variable Neighborhood Search Algorithm For Solving a full-load automated guided vehicle routing problem with battery constraints. Electronic Notes in Discrete Mathematics, 47, 165–172.
  • Clarke, G. and J. W. Wright (1964). Scheduling of Vehicles from a Central Depot to a Number of Delivery Points. Operations Research, 12, 568–581.
  • Crainic, T. G. (2000). Service network design in freight transportation. European Journal of Operational Research, 122, 272–288.
  • Dell’Amico, M., M. Monaci, C. Pagani, and D. Vigo (2007). Heuristic approaches for the fleet size and mix vehicle routing problem with time windows. Transportation Science, 41, 516–526.
  • Dominguez, O., A. A. Juan, I. A. de la Nuez, and D. Ouelhadj (2016). 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 E. Miller-Hooks (2012). A Green Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review, 48, 100–114.
  • Faulin, J., S. E. Grasman, A. A. Juan, and P. Hirsch (2019). Sustainable transportation: concepts and current practices. In Sustainable Transportation and Smart Logistics, pp. 3–23. Elsevier.
  • Faulin, J., F. Lera-López, and A. A. Juan (2011). Optimizing routes with safety and environmental criteria in transportation management in spain: a case study. International Journal of Information Systems and Supply Chain Management, 4, 38–59.
  • Feillet, D. (2010). A tutorial on column generation and branch-and-price for vehicle routing problems. 4OR A Quarterly Journal of Operations Research, 8, 407–424.
  • Felipe, N., M. T. Ortuño, G. Righini, and G. Tirado (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–128.
  • Ferone, D., A. Gruler, P. Festa, and A. A. Juan (2019). Enhancing and extending the classical grasp framework with biased randomisation and simulation. Journal of the Operational Research Society, 70, 1362– 1375.
  • Ferreira, J., P. Pereira, P. Filipe, and J. Afonso (2011). Recommender system for drivers of electric vehicles. ICECT 2011 2011 3rd International Conference on Electronics Computer Technology, 5, 244–248.
  • François, V., Y. Arda, Y. Crama, and G. Laporte (2016). Large neighborhood search for multi-trip vehicle routing. European Journal of Operational Research, 255, 422–441.
  • Ghannadpour, S. F., S. Noori, R. Tavakkoli-Moghaddam, and K. Ghoseiri (2014). A multi-objective dynamic vehicle routing problem with fuzzy time windows: Model, solution and application. Applied Soft Computing, 14, 504–527.
  • Goeke, D. and M. Schneider (2015). Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research, 245, 81–99.
  • González-Martı́n, S., A. A. Juan, D. Riera, Q. Castellà, R. Muñoz, and A. Pérez (2012). Development and assessment of the sharp and randsharp algorithms for the arc routing problem. AI Communications, 25, 173–189.
  • Hatami, S., R. Ruiz, and C. Andrés-Romano (2015). Heuristics and metaheuristics for the distributed assembly permutation flowshop scheduling problem with sequence dependent setup times. International Journal of Production Economics, 169, 76–88.
  • Hiermann, G., J. Puchinger, S. Ropke, and R. F. Hartl (2016). The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations. European Journal of Operational Research, 252, 995–1018.
  • Hokama, P., F. K. Miyazawa, and E. C. Xavier (2016). A branch-and-cut approach for the vehicle routing problem with loading constraints. Expert Systems with Applications, 47, 1–13.
  • Jie, W., J. Yang, M. Zhang, and Y. Huang (2019). The two-echelon capacitated electric vehicle routing problem with battery swapping stations: Formulation and efficient methodology. European Journal of Operational Research, 272, 879–904.
  • Juan, A. A., J. Faulin, J. C. Cruz, B. B. Barrios, and E. Martinez (2014a). A successive approximations method for the heterogeneous vehicle routing problem: analysing different fleet configurations. European Journal of Industrial Engineering, 8, 762.
  • Juan, A. A., J. Goentzel, and T. Bektaş (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., C. A. Mendez, J. Faulin, J. De Armas, and S. E. Grasman (2016). Electric vehicles in logistics and transportation: A survey on emerging environmental, strategic, and operational challenges. Energies, 9, 1–21.
  • Karakatič, S. and V. Podgorelec (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27, 519–532.
  • Kek, A. G. H., R. L. Cheu, and Q. Meng (2008). Distance-constrained capacitated vehicle routing problems with flexible assignment of start and end depots. Mathematical and Computer Modelling, 47, 140–152.
  • Keskin, M. and B. Çatay (2016). Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 65, 111–127.
  • Koç, C. a., T. Bektaş, O. Jabali, and G. Laporte (2016). Thirty years of heterogeneous vehicle routing. European Journal of Operational Research, 249, 1–21.
  • Laporte, G. (2009). Fifty Years of Vehicle Routing. Transportation Science, 43, 408–416.
  • Laporte, G., M. Desrochers, and Y. Nobert (1984). Two exact algorithms for the distance-constrained vehicle routing problem. Networks, 14, 161–172.
  • Li, C.-L., D. Simchi-Levi, and M. Desrochers (1992). On the distance constrained vehicle routing problem. Operations research, 40, 790–799.
  • Lin, J., W. Zhou, and O. Wolfson (2016). Electric Vehicle Routing Problem. Transportation Research Procedia, 12, 508–521.
  • Martin, D., R. del Toro, R. Haber, and J. Dorronsoro (2009). Optimal tuning of a networked linear controller using a multi-objective genetic algorithm and its application to one complex electromechanical process. International Journal of Innovative Computing, Information and Control, 5, 3405–3414.
  • Mattila, T. and R. Antikainen (2011). Backcasting sustainable freight transport systems for Europe in 2050. Energy Policy, 39, 1241–1248.
  • Montoya, A., C. Guéret, J. E. Mendoza, and J. G. Villegas (2014). A multi-space sampling heuristic for the green vehicle routing problem. Transportation Research Part C: Emerging Technologies, 70, 113–128.
  • Osman, I. and C. Potts (1989). Simulated annealing for permutation flow-shop scheduling. Omega, 17, 551–557.
  • Pierre, D. M. and N. Zakaria (2017). Stochastic partially optimized cyclic shift crossover for multi-objective genetic algorithms for the vehicle routing problem with time-windows. Applied Soft Computing, 52, 863–876.
  • Quintero-Araujo, C. L., J. P. Caballero-Villalobos, A. A. Juan, and J. R. Montoya-Torres (2017). A biasedrandomized metaheuristic for the capacitated location routing problem. International Transactions in Operational Research, 24, 1079–1098.
  • Reyes-Rubiano, L., D. Ferone, A. A. Juan, and J. Faulin (2019). A simheuristic for routing electric vehicles with limited driving ranges and stochastic travel times. SORT-Statistics and Operations Research Transactions, 43, 3–24.
  • Ruiz, R. and T. Stützle (2007). A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. European Journal of Operational Research, 177, 2033–2049.
  • Ruiz, R. and T. Stützle (2008). An Iterated Greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research, 187, 1143–1159.
  • Schneider, M., A. Stenger, and D. Goeke (2014). The electric vehicle-routing problem with time windows and recharging stations. Transportation Science, 48, 500–520.
  • Solano-Charris, E., C. Prins, and A. C. Santos (2015). Local search based metaheuristics for the robust vehicle routing problem with discrete scenarios. Applied Soft Computing, 32, 518–531.
  • Solos, I. P., I. X. Tassopoulos, and G. N. Beligiannis (2016). Optimizing shift scheduling for tank trucks using an effective stochastic variable neighbourhood approach. International Journal of Artificial Intelligence, 14, 1–26.
  • Vaz Penna, P. H., H. M. Afsar, C. Prins, and C. Prodhon (2016). A Hybrid Iterative Local Search Algorithm for The Electric Fleet Size and Mix Vehicle Routing Problem with Time Windows and Recharging Stations. IFAC-PapersOnLine, 49, 955–960.
  • Verma, A. (2018). Electric vehicle routing problem with time windows, recharging stations and battery swapping stations. EURO Journal on Transportation and Logistics, 7, 415–451.
  • Wang, C., D. Mu, F. Zhao, and J. W. Sutherland (2015). A parallel simulated annealing method for the vehicle routing problem with simultaneous pickup-delivery and time windows. Computers & Industrial Engineering, 83, 111–122.
  • Williams, J. H., A. Debenedictis, R. Ghanadan, A. Mahone, J. Moore, W. R. M. Iii, S. Price, and M. S. Torn (2012). 2050 : The Pivotal Role of Electricity. Science, 335, 53–60.
  • Wirasingha, S. G., N. Schofield, and A. Emadi (2008). Plug-in hybrid electric vehicle developments in the US: Trends, barriers, and economic feasibility. In 2008 IEEE Vehicle Power and Propulsion Conference, pp. 1–8.
  • Yu, V. F. and S.-Y. Lin (2015). A simulated annealing heuristic for the open location-routing problem. Computers & Operations Research, 62, 184–196.
Fuente de los datos: Dialnet