A Hybrid Solution Approach for Electric Vehicle Routing Problem with Soft Time-Windows

Year 2021, Volume: 8 Issue: 2, 994 - 1006, 31.05.2021

Burak Urazel , Kemal Keskin

https://doi.org/10.31202/ecjse.908159

Cited By: 3

Abstract

An electric vehicle routing problem (EVRP) with time windows is carried out using a hybrid algorithm. Through the modeling of problem, not only the energy consumptions and the charging durations of the EDVs, but also the conventional vehicle flow formulations and the soft time window constraints are taken into account. A hybrid solution method is proposed to solve EVRP. The proposed method combines genetic algorithm and simulated annealing algorithm to complement each other. In order to demonstrate the effectiveness of the proposed approach, simulations are carried out on a case study with 25 customers, 2 charging stations, a depot and 3 identical EDVs. The performance of the proposed method has been compared with the standalone genetic algorithm. It is resulted that the hybrid algorithm outperforms the genetic algorithm in terms of both solution accuracy and computational time.

Keywords

Electric Vehicle Routing Problem, Hybrid Algorithm, ,Genetic Algorithm

Supporting Institution

Eskisehir Osmangazi University Scientific Research Projects Coordination Unit

Project Number

202015008

Thanks

This work has been supported by Eskisehir Osmangazi University Scientific Research Projects Coordination Unit under grant number 202015008.

Yumuşak Zaman Pencereli Elektrikli Araç Rotalama Problemi için Hibrit Çözüm Yaklaşımı

Abstract

Bu çalışmada elektrikli araç rotalama problemi zaman pencereleri göz önünde bulundurularak ve hibrit bir algoritma kullanılarak ele alınmaktadır. Problemin modellenmesi aşamasında sadece elektrikli araçların enerji tüketimleri ve şarj süreleri değil aynı zamanda geleneksel araç akış formülasyonları ve yumuşak zaman pencereleri kısıtları da hesaba katılmaktadır. Elektrikli araç rotalama probleminin çözümü için bir hibrit yaklaşım önerilmektedir. Önerilen yöntem birbirlerinin eksikliklerini kapatacak şekilde Genetik Algoritma ve Benzetilmiş Tavlama Algoritmalarını birleştirmektedir. Önerilen yaklaşımın etkinliğini gösterebilmek için, 25 müşteri, 2 şarj istasyonu, bir depo ve 3 aynı özelliklere sahip elektrikli araç ile bir durum çalışması benzetimi yapılmaktadır. Performans olarak, önerilen hibrit yaklaşım, yalın Genetik Algoritma ile karşılaştırılmaktadır. Sonuçlar, hibrit algoritmanın hem çözüm hassasiyeti hem de hesaplama süresi açısından daha iyi sonuç verdiğini göstermektedir.

Keywords

Elektrikli Araç Rotalama Problemi, Hibrit Algoritma, Genetik Algoritma

Project Number

202015008

References

• 1. Laporte, G., “The vehicle routing problem: An overview of exact and approximate algorithms”, European Journal of Operational Research, 59(3):345-358, (1992).
• 2. Gendreau, M., Hertz, A., and Laporte, G., “Tabu Search Heuristic for the Vehicle Routing Problem”, Management Science, 40(10): 1276–1290, (1994).
• 3. Cordeau, J.-F., Gendreau, M., Laporte, G., Potvin, J.-Y., and Semet, F., “A guide to vehicle routing heuristics”, Journal of the Operational Research Society, 53(5): 512–522, (2002).
• 4. Cordeau, J.-F., Gendreau, M., Hertz, A., Laporte, G., and Sormany, J.-S., “New Heuristics for the Vehicle Routing Problem”, In Logistics Systems: Design and Optimization, 279–297, (2005)
• 5. Felipe, Á., Ortuño, M. T., Righini, G., and 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).
• 6. Yang, J., and Sun, H., “Battery swap station location-routing problem with capacitated electric vehicles”, Computers & Operations Research, 55:217–232, (2015).
• 7. Li, J.-Q., “Transit Bus Scheduling with Limited Energy”, Transportation Science, 48(4): 521–539, (2014).
• 8. Verma, A., “Electric vehicle routing problem with time windows, recharging stations and battery swapping stations”, EURO Journal on Transportation and Logistics, 7(4): 415–451, (2018)
• 9. Sassi, O., Cherif-Khettaf, W. R., and Oulamara, A., “v”, In Advances in Intelligent Systems and Computing, 57–68, (2015).
• 10. Goeke, D., and Schneider, M., “Routing a mixed fleet of electric and conventional vehicles”, European Journal of Operational Research, 245(1): 81–99, (2015).
• 11. 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, 27(1): 235–248, (2019).
• 12. Zhen, L., Xu, Z., Ma, C., and Xiao, L., “Hybrid electric vehicle routing problem with mode selection”, International Journal of Production Research, 58(2):562-576, (2019).
• 13. Zuo, X., Zhu, C., Huang, C., and Xiao, Y., “Using AMPL/CPLEX to model and solve the electric vehicle routing problem (EVRP) with heterogeneous mixed fleet”, 29th Chinese Control And Decision Conference (CCDC), Chongqing, China, (2017).
• 14. 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, 252(3):995-1018, (2016).
• 15. Bozorgi, A. M., Farasat, M., and Mahmoud, A., “ATime and Energy Efficient Routing Algorithm for Electric Vehicles Based on Historical Driving Data”, IEEE Transactions on Intelligent Vehicles, 2:308-320, (2017).
• 16. Abousleiman, R., and Rawashdeh, O., “Electric vehicle modelling and energy efficient routing using particle swarm optimisation”, IET Intelligent Transport Systems, 10(2):65-72, (2016).
• 17. Shao, S., Guan, W., and Bi, J., “Electric vehicle-routing problem with charging demands and energy consumption”, IET Intelligent Transport Systems, 12(3):202-212, (2018).
• 18. Baum, M., Dibbelt, J., Pajor, T., Sauer, J., Wagner, D., and Zündorf, T., “Energy-Optimal Routes for Battery Electric Vehicles”, Algorithmica, 82(5):1490-1546, (2017)
• 19. Erdoğan, S., and Miller-Hooks, E., “A Green Vehicle Routing Problem”, Transportation Research Part E: Logistics and Transportation Review, 48(1):100-114, (2012).
• 20. Keskin, M., and Çatay, B., “Partial recharge strategies for the electric vehicle routing problem with time windows”, Transportation Research Part C: Emerging Technologies, 65:111 127, (2016).
• 21. Zhen, L., Xu, Z., Ma, C., and Xiao, L., “Hybrid electric vehicle routing problem with mode selection”, International Journal of Production Research, 58(2):562-576, (2019).
• 22. Cortes-Murcia, D. L., Prodhon, C., and Murat Afsar, H., “The electric vehicle routing problem with time windows, partial recharges and satellite customers”, Transportation Research Part E: Logistics and Transportation Review, 130:184-206, (2019).
• 23. Macrina, G., Di Puglia Pugliese, L., Guerriero, F., and Laporte, G., “The green mixed fleet vehicle routing problem with partial battery recharging and time windows”, Computers & Operations Research, 101:183-199, (2019).
• 24. Mavrovouniotis, M., Ellinas, G., and Polycarpou, M., “Ant Colony optimization for the Electric Vehicle Routing Problem”, IEEE Symposium Series on Computational Intelligence (SSCI), Bangalore, India, (2018).
• 25. Zhang, S., Gajpal, Y., Appadoo, S. S., and Abdulkader, M. M. S., “Electric vehicle routing problem with recharging stations for minimizing energy consumption”, International Journal of Production Economics, 203:404-413, (2018).
• 26. Goldberg, D. E., “Genetic Algorithms in Search, Optimization and Machine Learning (1st. ed.) ”, Addison-Wesley Longman Publishing Co., Inc., USA., (1989).
• 27. Chen, A., Jiang, T., Chen, Z., and Zhang, Y., “A Genetic and Simulated Annealing Combined Algorithm for Optimization of Wideband Antenna Matching Networks”, International Journal of Antennas and Propagation, 2012:1-6, (2012).
• 28. Zhenfeng, G., Yang, L., Xiaodan, J., and Sheng, G., “The electric vehicle routing problem with time windows using genetic algorithm”, 2017 IEEE 2nd Advanced Information Technology, Electronic and Automation Control Conference (IAEAC), Chongqing,China, (2017).