Elektrikli Araçların Şarj İstasyonu Kapasite Kısıtı Altında Rotalanması Problemi için Üst Sınır Bulma Algoritmaları ve Matematiksel Modeller

Öz

Sürdürülebilirliğin önem kazanmasıyla birlikte elektrikli araç rotalama problemi (EARP) birçok çalışmada ele alınmıştır. EARP, klasik içten yanmalı motorlu araç rotalama problemine göre farklılıklar içermektedir. Bir elektrikli araç (EA) belirli bir şarj kapasitesine sahiptir ve gerekli olması halinde uygun şarj istasyonunda durur ve şarj edilerek rotasını tamamlar. Gerçek hayatta şarj istasyonlarının kapasitesi sınırlıdır. Bir istasyonda aynı anda şarj edilen araç sayısı, ilgili istasyondaki şarj ünitesi sayısını geçemez. Bu çalışmada, her istasyonda aynı anda yalnızca bir EA'nın şarj edilebileceği varsayılmıştır. Bu çalışmada, ilgili problem için şarj istasyonu için kopya düğümleri olan ve olmayan matematiksel modeller önerilmiştir. Ayrıca, problem için iki adet üst sınır bulma algoritması önerilmiştir. Üst sınır bulma algoritmaları çözüm süresi ve kalitesi açısından karşılaştırılmıştır. Sonuç olarak, matematiksel modelin makul sürelerde çözüm bulamadığı problemler için önerilen üst sınır bulma algoritmaları ile daha kısa sürede uygulanabilir çözümler elde edilmiştir.

Anahtar Kelimeler

• Elektrikli araç rotalama
• Şarj istasyonu kapasite kısıtı
• Üst sınır bulma algoritmaları
• Matemetiksel model

Upper Bound Finding Algorithms and Mathematical Models for Electric Vehicle Routing Problem with Charging Station Capacity Constraint

Öz

Electric vehicle routing problem (EVRP) has been addressed in many studies since the sustainability has gained importance. The EVRP has differences compared to the classical internal combustion engine vehicle routing problem. An electric vehicle (EV) has a certain charging capacity and it stops in case of necessity at the appropriate charging station and it is charged to complete its route. In real life, the capacity of charging stations is limited. The number of vehicles charged simultaneously at a station cannot exceed the number of charging units at the related station. In this study, it is assumed that only one EV can be charged at each station at a time. In this study, mathematical models with and without charging station copy nodes are proposed for the relevant problem. Additionally, two upper bound finding algorithms are proposed for the problem. Upper bound finding algorithms are compared in terms of solution time and quality. As a result, feasible solutions are obtained in a shorter time with the proposed upper bound finding algorithms for the problems that mathematical model could not obtain a solution in reasonable times.

Anahtar Kelimeler

• Electric vehicle routing problem
• charging station capacity constraint
• upper bound finding algorithms
• mathematical model

Kaynakça

1. [1] Bruglieri M., Mancini S. and Pisacane O., “The green vehicle routing problem with capacitated alternative fuel stations”, Computers and Operations Research, 112, 104759, (2019).
2. [2] Dagistanli H.A., “Cok urunlu cok depolu arac rotalama problemi: Askeri ilac fabrikasi ornegi”, Politeknik Dergisi, 27 (3): 1017- 1027, (2024).
3. [3] Tezcan B., Alakas H.M., Ozcan E. and Eren T., “Afet sonrasi gecici depo yeri secimi ve cok aracli arac rotalama uygulamasi: Kirikkale ilinde bir uygulama, Politeknik Dergisi, 26 (1): 13- 27, (2023).
4. [4] Akcakoca A.E., Aydogan E.K., Delice Y. and Himmetoglu S., “Heterojen filolu ve kapasite kisitli yesil arac rotalama problemi icin bir matematiksel model ve endustriyel bir uygulama”, Politeknik Dergisi, 27 (4): 1345- 1352, (2024).
5. [5] Erdelic T. and Taric T., “A survey on the electric vehicle routing problem: Variants and solution approaches”, Journal of Advanced Transportation, 5075671, (2019).
6. [6] Conrad R.G. and Figliozzi M.A., “The recharging vehicle routing problem”, Proceedings of the 2011 Industrial Engineering Research Conference, 1-8.
7. [7] Erdogan S. and Miller-Hooks E., “A green vehicle routing problem”, Transportation Research Part E, 48: 100- 114, (2012).
8. [8] Felipe A., Ortuno M.T., Righini G. and Tirado G., “A heuristic approach for the green vehicle routing problem with multiple technologies and partial rechargers”, Transportation Research Part E, 71: 111-128, (2014).

9. [9] Sassi O., Cherif W.R. and Oulamara A., “Vehicle routing problem with mixed fleet of conventional and heterogeneous electric vehicles and time dependent charging costs”, hal-01083966, (2014).
10. [10] Goeke D. and Schneider M., “Routing a mixed fleet of electric and conventional vehicles”, European Journal of Operational Research, 245: 81-99, (2015).
11. [11] 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: 995- 1018, (2016).
12. [12] Keskin M. and Catay B., “A matheuristic method for the electric vehicle routing problem with time windows and fast chargers”, Computers and Operations Research, 100: 172-188, (2018).
13. [13] Macrina G., Laporte G., Guerriero F. and Pugliese L.D.P., “An energy- efficient green- vehicle routing problem with mixed vehixle fleet, partial battery recharging and time windows”, European Journal of Operational Research, 276: 971-982, (2019).
14. [14] Bac U. and Erdem M., “Optimization of electric vehicle recharge schedule and routing problem with time windows and partial recharge: A comparative study for an urban logistics fleet”, Sustainable Cities and Society, 70, 102883, (2021).
15. [15] Zuo X., Xiao Y., You M., Kaku I. and Xu Y., “A new formulation of the electric vehicle routing problem with time windows considering concave nonlinear charging function”, Journal of Cleaner Production, 236, 117687, (2019).
16. [16] Yu V.F., Jodiawan P. and Gunawan A., “An adaptive large neighborhood search for the green mixed fleet vehicle routing problem with realistic energy consumption and partial rechargers”, Applied Soft Computing, 105, 107251, (2021).
17. [17] Montoya A., Gueret C., Mendoza J.E. and Villegas J.G., “The electric vehicle routing problem with nonlinear charging function”, Transportation Research Part B, 103: 87-110, (2017).
18. [18] Yang S., Ning L., Tong L.C. and Shang P., “Optimizing electric vehicle routing problems with backhauls and recharging strategies in multi- dimensional representation network”, Expert Systems with Applications, 176, 114804, (2021).
19. [19] Lam E., Desaulniers G. and Stuckey P.J., “Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations”, Computers and Operations Research, 145, 105870, (2022).
20. [20] Keskin M., Laporte G. and Catay B., “Electric vehicle routing problem with time- dependent waiting times and recharging stations”, Computers and Operations Research, 107: 77-94, (2019).
21. [21] Froger A., Jabali O., Mendoza J.E. and Laporte G., “The electric vehicle routing problem with capacitated charging stations”, Transportation Science, 56(2): 265-564, (2022).
22. [22] Dastpak M., Erico F., Jabali O. and Malucelli F., “Dynamic routing for the electric vehicle shortest path problem with charging station occupancy information”, Transportation Research Part C, 158, 104411, (2024).
23. [23] Bruglieri M., Ferone D., Festa P. and Pisacane O., “A GRASP with penalty objective function for the green vehicle routing problem with private capacitated stations”, Computers and Operations Research, 143, 105770, (2022).
24. [24] Bruglieri M., Mancini S. and Pisacane O., “A more efficient cutting planes approach for the green vehicle routing problem with capacitated alternative fuel stations”, Optimization Letters, 15: 2813-2829, (2021).
25. [25] Bagci I., Oztop H. and Cil Z. A., “Mathematical modelling approaches for integrated single machine scheduling and electric vehicle routing problem”, Journal of Transportation and Logistics, 9(1): 48- 59, (2024).
26. [26] Cicek A. and Erdinc O., “PV- Batarya hibrit sistemi iceren elektrikli arac otoparkinin sarj yonetimi”, Avrupa Bilim ve Teknoloji Dergisi, 15, 466- 474, (2019).
27. [27] Shanmugam P.K. and Thomas P., “Optimization strategies for electric vehicle charging and routing: A comprehensive Review”, Gazi University Journal of Science, 37 (3): 1256- 1285, (2024).
28. [28] Donmez S. and Koc C., Altiparmak F., “The mixed fleet vehicle routing problem with partial recharging by multiple chargers: A formulation and an insertion based constructive heuristic”, Journal of the Faculty of Engineering and Architecture of Gazi University, 39(1): 1-16, (2024).
29. [29] Schneider M., Stenger A. and Goeke D., “The electric vehicle- routing problem with time windows and recharging stations”, Transportation Science, 48 (4): 500- 520, (2014).