Çoklu şarj teknolojisine dayalı kısmi şarj politikalı karma filolu araç rotalama problemi: Matematiksel model ve çözüm kurucu sezgisel

Year 2024, Volume: 39 Issue: 1, 1 - 16, 21.08.2023

Sercan Dönmez Çağrı Koç Fulya Altıparmak

https://doi.org/10.17341/gazimmfd.1106198

Abstract

Bu çalışmada Çoklu Şarj Teknolojisine Dayalı Kısmi Şarj Politikalı Karma Filolu Elektrikli Araç Rotalama Problemi (KF-E-ARP) ele alınmıştır. Karma filo, elektrikli araçları (EA) ve konvansiyonel araçları (KA) içermektedir. Konvansiyonel araçların emisyon fonksiyonu ve elektrikli araçların şarj tüketim fonksiyonu içerisinde katedilen mesafe ile birlikte araçta taşınan yük miktarı da dikkate alınmıştır. Ayrıca şarj istasyonunda çoklu şarj konfigürasyonlarından birinin seçilmesi, karma filolu problemlerde ilk defa ele alınmıştır. Problem, müşteri dağıtım taleplerini karşılarken toplam maiyeti enazlayan araç rotalarının elde edilmesi olarak tanımlanabilir. KF-E-ARP için öncelikle karma tamsayılı matematiksel model geliştirilmiştir. Problem NP-zor olduğundan dolayı, orta ve büyük boyutlu problemlere makul sürelerde çözüm elde edebilmek amacıyla ekleme tabanlı bir çözüm kurucu sezgisel algoritma önerilmiştir. Deneysel analizlerde, matematiksel model ile 2 saat içerisinde çözüm bulunamayan tüm orta ve büyük boyutlu problemlere önerilen çözüm kurucu sezgisel algoritmalar ile yaklaşık 1 saniye gibi çok kısada sürede uygun çözümler bulunabildiğini gözlemlenmiştir.

Keywords

Araç rotalama, elektrikli araç, karma filo, ekleme tabanlı çözüm kurucu sezgisel.

References

• Arslan, O., 2021. The location-or-routing problem. Transportation Research Part B: Methodological 147, 1–21.
• Arslan, O., Yıldız, B., Karaşan, O. E., 2015. Minimum cost path problem for plug-in hybrid electric vehicles. Transportation Research Part E 80, 123–141.
• Arslan, O., Karaşan, O. E., Mahjoub, A. R., Yaman, H., 2019. A branch-and-cut algorithm for the alternative fuel refueling station location problem with routing. Transportation Science, 53, 1107-1125.
• Conrad, R.G., Figliozzi, M.A., 2011. The recharging vehicle routing problem. In: Doolen, T., Van Aken, E. (Eds.), Proceedings of the 2011 Industrial Engineering Research Conference.
• Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y., and Semet, F., A Guide to Vehicle Routing Heuristic, The Journal of the Operational Research Society, 53, 512-522, 2002.
• Desaulniers, G., Errico, F., Irnich, S., Schneider, M., 2016. Exact algorithms for electric vehicle-routing problems with time windows. Operations Research 64, 1388–1405.
• Felipe, Á., Ortuño, M.T., Righini, G., Tirado, G., 2014. A heuristic approach for the green vehicle routing problem with multiple technologies and partial recharges. Transportation Research Part E 71, 111–128.
• Gajpal, Y., Abad, P., Saving-Based Algorithms for Vehicle Routing Problem with Simultaneous Pickup and Delivery, The Journal of the Operational Research Society, 61, 10,1498-1509, 2010.
• Goeke, D., Schneider, M., 2015. Routing a mixed fleet of electric and conventional vehicles. European Journal of Operational Research 245, 81–99.
• Gonçalves, F., Cardoso, S. R., Relvas, S., Barbosa-Póvoa, A., 2011. Optimization of a distribution network using electric vehicles: A VRP problem. In: 15th Congresso Nacional da Associação Portuguesa de Investigação Operacional, pp. 18–20.
• Keçeci B., Altıparmak F., Kara İ., Heterogeneous Vehicle Routing Problem with Simultaneous Pickup and Delivery: Mathematical Formulations and a Heuristic Algorithm, Journal of the Faculty of Engineering and Architecture of Gazi University, 30 (2), 185-195, 2015.
• Keskin, M., Çatay, B., 2016. Partial recharge strategies for the electric vehicle routing problem with time windows. Transportation Research Part C 65, 111–127.
• Keskin, M., Çatay, B., 2018. A matheuristic method for the electric vehicle routing problem with time windows and fast chargers. Computers & Operations Research 100, 172–188.
• Keskin, M., Çatay, B., Laporte, G., 2021. A simulation-based heuristic for the electric vehicle routing problem with time windows and stochastic waiting times at recharging stations. Computers & Operations Research 125, 105060.
• Koç, Ç., Karaoğlan, İ., 2012, A mathematical model for the vehicle routing problem with time windows and multiple use of vehicles. Journal of the Faculty of Engineering and Architecture of Gazi University 27, 569-576.
• Koç, Ç., Karaoğlan, İ., 2014. A mathematical model for the time-dependent vehicle routing problem. Journal of the Faculty of Engineering and Architecture of Gazi University 29, 549-558.
• Koç, Ç., Karaoglan, I., 2016. The green vehicle routing problem: A heuristic based exact solution approach. Applied Soft Computing 39, 154–164.
• Koç, Ç., Jabali, O., Mendoza, J. E., Laporte, G., 2019. The electric vehicle routing problem with shared charging stations. International Transactions in Operational Research 26, 1211–1243.
• Lin, J., Zhou, W., Wolfson, O., 2016. Electric vehicle routing problem. Transportation Research Procedia 12, 508–521.
• Macrina, G., Pugliese, L. D. P., Guerriero, F., Laporte, G., 2019a. The green mixed fleet vehicle routing problem with partial battery recharging and time windows. Computers & Operations Research, 101, 183–199.
• Macrina, G., Laporte, G., Guerriero, F., Pugliese, L. D. P., 2019b. An energy-efficient green-vehicle routing problem with mixed vehicle fleet, partial battery recharging and time windows. European Journal of Operational Research 276, 971–982.
• Montoya, A., Guéret, C., Mendoza, J. E., Villegas, J. G., 2017. The electric vehicle routing problem with nonlinear charging function. Transportation Research Part B 103, 87–110.
• Pelletier, S., Jabali, O., Laporte, G., Veneroni, M., 2017. Battery degradation and behaviour for electric vehicles: Review and numerical analyses of several models. Transportation Research Part B 103, 158–187.
• Ropke, S., Pisinger, D., 2006a. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science 40, 455–472.
• Ropke, S., Pisinger, D., 2006b. A unified heuristic for a large class of vehicle routing problems with backhauls. European Journal of Operational Research 171, 750–775.
• Sassi, O., Cherif, W. R., Oulamara, A., 2014. Vehicle routing problem with mixed feet of conventional and heterogenous electric vehicles and time dependent charging costs. Technical Report. https://hal.archives-ouvertes.fr/hal-01083966.
• Schiffer, M., Walther, G., 2017. The electric location routing problem with time windows and partial recharging. European Journal of Operational Research 260, 995–1013.
• Schiffer, M., Walther, G., 2018. An adaptive large neighborhood search for the location-routing problem with intra-route facilities. Transportation Science 52, 331–352.
• Schneider, M., Stenger, A., Goeke, D., 2014. The electric vehicle routing problem with time windows and recharging stations. Transportation Science 48, 500–520.
• Turkeš, R., Sörensen, K., Hvattum, L. M., 2021. Meta-analysis of metaheuristics: Quantifying the effect of adaptiveness in adaptive large neighborhood search. European Journal of Operational Research 292, 423-442.
• Vidal, T., Laporte, G., Matl, P., 2020. A concise guide to existing and emerging vehicle routing problem variants. European Journal of Operational Research 286, 401-416.
• Vincent, F. Y., Jodiawan, P., Gunawan, A., 2021. An adaptive large neighborhood search for the green mixed fleet vehicle routing problem with realistic energy consumption and partial recharges. Applied Soft Computing 105, 107251.
• Yaşar Boz, E., Aras, F. 2021. Yeşil araç rotalama problemi araştırması: geçmiş ve gelecekteki eğilimler. Journal of Turkish Operations Management, 5 (2), 806-821.
• Yang, J., Sun, H., 2015. Battery swap station location-routing problem with capacitated electric vehicles. Computers and Operations Research 55, 217–232.
• Yıldız, E.A., Karaoğlan, I., Altıparmak, F., 2021. A mixed integer mathematical model and a heuristic approach for two-echelon location routing problem with simultaneous pickup and delivery, Journal of the Faculty of Engineering and Architecture of Gazi University, 36 (2), 807-822.