Multi-Objective Vehicle Routing Problem for a Mixed Fleet of Electric and Conventional Vehicles with Time Windows and Recharging Stations

Document Type : Original Article

Authors

School of Industrial Engineering, College of Engineering, University of Tehran, Tehran, Iran

Abstract

The vehicle routing problem as a challenging decision problem has been studied extensively. More specifically, solving it for a mixed fleet requires realistic calculation of the performance of electric and combustion vehicles. This study addresses a new variant of the vehicle routing problem for a mixed fleet of electric and combustion vehicles under the presence of time windows and charging stations. A bi-objective mixed-integer programming model is developed which aims at minimizing cost and pollution level concurrently. To accurately quantify travel quantities, such as fuel consumption, emission, and battery charge level, a set of realistic mathematical formulas are used. The model is first converted to a single-objective counterpart using the epsilon-constraint method and a simulated annealing algorithm is tailored to obtain Pareto optimal solutions. A discussion is also made on how the final solution can be selected from the Pareto frontier according to the design objectives. The presented framework can find a set of Pareto optimal solutions as a trade-off between cost and pollution objectives by considering different combinations of electric and combustion vehicles. It was shown that those solutions that involve more electric fleet than combustion fleet, lead to higher total costs and smaller emissions and vice versa.

Keywords

Main Subjects

References

  1. Perera, F., "Pollution from fossil-fuel combustion is the leading environmental threat to global pediatric health and equity: Solutions exist", International Journal of Environmental Research and Public Health, Vol. 15, No. 1, (2018), 16. https://doi.org/10.3390/ijerph15010016
  2. Agancy, E.E. Eu ghg emission inventory reported under the unfccc and the kyoto protocol. 2022; Available from: https://www.eea.europa.eu/themes/climate/eu-greenhouse-gas-inventory.
  3. Kucukoglu, I., Dewil, R. and Cattrysse, D., "The electric vehicle routing problem and its variations: A literature review", Computers & Industrial Engineering, Vol. 161, (2021), 107650. https://doi.org/10.1016/j.cie.2021.107650
  4. Schneider, M., Stenger, A. and Goeke, D., "The electric vehicle-routing problem with time windows and recharging stations", Transportation Science, Vol. 48, No. 4, (2014), 500-520. https://doi.org/10.1287/trsc.2013.0490
  5. Erdoğan, S. and Miller-Hooks, E., "A green vehicle routing problem", Transportation Research Part E: Logistics and Transportation Review, Vol. 48, No. 1, (2012), 100-114. https://doi.org/10.1016/j.tre.2011.08.001
  6. Romet, P., Tabusse, R., Gechter, F., Aglzim, E.-H., Jemei, S., Bouquain, D. and Chrenko, D., "Autonomous electric vehicle routing problem using ant colony optimization with consideration of the battery state-of-health", in 2021 IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), IEEE. Vol., (2021), 475-480. https://doi.org/10.1109/ICTAI52525.2021.00077
  7. Hiermann, G., Hartl, R.F., Puchinger, J. and Vidal, T., "Routing a mix of conventional, plug-in hybrid, and electric vehicles", European Journal of Operational Research, Vol. 272, No. 1, (2019), 235-248. https://doi.org/10.1016/j.ejor.2018.06.025
  8. Macrina, G., Laporte, G., Guerriero, F. and Pugliese, L.D.P., "An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows", European Journal of Operational Research, Vol. 276, No. 3, (2019), 971-982. https://doi.org/10.1016/j.ejor.2019.01.067
  9. Bektaş, T. and Laporte, G., "The pollution-routing problem", Transportation Research Part B: Methodological, Vol. 45, No. 8, (2011), 1232-1250. https://doi.org/10.1016/j.trb.2011.02.004
  10. Zhou, Z., Ha, M., Hu, H. and Ma, H., "Half open multi-depot heterogeneous vehicle routing problem for hazardous materials transportation", Sustainability, Vol. 13, No. 3, (2021), 1262. https://doi.org/10.3390/su13031262.
  11. Davis, B.A. and Figliozzi, M.A., "A methodology to evaluate the competitiveness of electric delivery trucks", Transportation Research Part E: Logistics and Transportation Review, Vol. 49, No. 1, (2013), 8-23. https://doi.org/10.1016/j.tre.2012.07.003.
  12. Goeke, D. and Schneider, M., "Routing a mixed fleet of electric and conventional vehicles", European Journal of Operational Research, Vol. 245, No. 1, (2015), 81-99. https://doi.org/10.1016/j.ejor.2015.01.049
  13. Sivagnanam, A., Ayman, A., Wilbur, M., Pugliese, P., Dubey, A. and Laszka, A., "Minimizing energy use of mixed-fleet public transit for fixed-route service", in Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35, (2021), 14930-14938. https://doi.org/10.1609/aaai.v35i17.17752
  14. Macrina, G., Pugliese, L.D.P., Guerriero, F. and Laporte, G., "The green mixed fleet vehicle routing problem with partial battery recharging and time windows", Computers & Operations Research, Vol. 101, (2019), 183-199. https://doi.org/10.1016/j.cor.2018.07.012
  15. Demir, E., Bektaş, T. and Laporte, G., "A review of recent research on green road freight transportation", European Journal of Operational Research, Vol. 237, No. 3, (2014), 775-793. https://doi.org/10.1016/j.ejor.2013.12.033
  16. Kopfer, H.W., Schönberger, J. and Kopfer, H., "Reducing greenhouse gas emissions of a heterogeneous vehicle fleet", Flexible Services and Manufacturing Journal, Vol. 26, No. 1, (2014), 221-248. https://doi.org/10.1007/s10696-013-9180-9
  17. Ghannadpour, S.F. and Zarrabi, A., "Multi-objective heterogeneous vehicle routing and scheduling problem with energy minimizing", Swarm and Evolutionary Computation, Vol. 44, (2019), 728-747. https://doi.org/10.1016/j.swevo.2018.08.012
  18. Abad, H.K.E., Vahdani, B., Sharifi, M. and Etebari, F., "A bi-objective model for pickup and delivery pollution-routing problem with integration and consolidation shipments in cross-docking system", Journal of Cleaner Production, Vol. 193, (2018), 784-801. https://doi.org/10.1016/j.jclepro.2018.05.046
  19. Androutsopoulos, K.N. and Zografos, K.G., "An integrated modelling approach for the bicriterion vehicle routing and scheduling problem with environmental considerations", Transportation Research Part C: Emerging Technologies, Vol. 82, (2017), 180-209. https://doi.org/10.1016/j.trc.2017.06.013
  20. Hiermann, G., Puchinger, J., Ropke, S. and Hartl, R.F., "The electric fleet size and mix vehicle routing problem with time windows and recharging stations", European Journal of Operational Research, Vol. 252, No. 3, (2016), 995-1018. https://doi.org/10.1016/j.ejor.2016.01.038
  21. Alsumairat, N. and Alrefaei, M., "Solving hybrid-vehicle routing problem using modified simulated annealing", International Journal of Electrical & Computer Engineering (2088-8708), Vol. 11, No. 6, (2021).
  22. Markel, T., Brooker, A., Hendricks, T., Johnson, V., Kelly, K., Kramer, B., O’Keefe, M., Sprik, S. and Wipke, K., "Advisor: A systems analysis tool for advanced vehicle modeling", Journal of Power Sources, Vol. 110, No. 2, (2002), 255-266.
  23. Vincent, F.Y., Redi, A.P., Hidayat, Y.A. and Wibowo, O.J., "A simulated annealing heuristic for the hybrid vehicle routing problem", Applied Soft Computing, Vol. 53, No., (2017), 119-132. https://doi.org/10.3390/ijerph15010016
  24. Lin, J., Zhou, W. and Wolfson, O., "Electric vehicle routing problem", Transportation Research Procedia, Vol. 12, No., (2016), 508-521. https://doi.org/10.1016/j.trpro.2016.02.007
  25. Feng, W. and Figliozzi, M.A., "Conventional vs electric commercial vehicle fleets: A case study of economic and technological factors affecting the competitiveness of electric commercial vehicles in the USA", Procedia-Social and Behavioral Sciences, Vol. 39, (2012), 702-711. https://doi.org/10.1016/j.sbspro.2012.03.141
  26. Energy, U.S.D.o. Navistar estar vehicle performance evaluation – cumulative. 2014, August; Available from: https://www.nrel.gov/docs/fy14osti/61899.pdf.
  27. Motors, I. Isuzu introduces all-new elf truck(n-series) in japan. 2006, December 13; Available from: https://www.isuzu.co.jp/world/press/2006/p_1213.html.
International Journal of Engineering
Volume 35, Issue 12
TRANSACTIONS C: Aspects
December 2022
Pages 2359-2369

Files

Cited by

Share

How to cite

Statistics