Belirsiz süre altında afet sonrası araç rotalama problemi

Öz

Afet sonrası toplanma bölgelerindeki afetzedelere mümkün olan en kısa süre içerisinde insani yardım malzemelerinin götürülmesi gerekmektedir. Afet sonrası insanların afet bölgesinden uzaklaşmak istemeleri veya yakınlarını merak eden kişilerin bilgi almak için afet bölgesine gitmek istemeleri yollarda trafiğe neden olabilmektedir. Bu nedenle yollardaki ulaşım süresi değişebilir. Öncelikli ulaşım süresi toplamının enküçüklenmesinin amaçlandığı problemde düğümler arasındaki seyahat süresi stokastik olarak ele alınmıştır. Araç rotalama problemi NP-Hard sınıfında bir problem olduğu için problem boyutu büyüdükçe kesin çözüm yöntemleriyle en iyi çözüm elde edilemeyebilir. Bu nedenle sezgisel algoritmalara ihtiyaç duyulmaktadır. Uyarlanabilir büyük komşu arama algoritması bu problemin çözümü için uygulanmıştır. Küçük örneklerde kesin çözüm yöntemiyle sezgisel algoritma ile elde edilen sonuçlar kıyaslanmıştır ve çözüm kalitesinin iyi olduğu görülmüştür. Geliştirilen metasezgisel algoritma orta boyutlu problemlerin çözümü için de kullanılmıştır.

Anahtar Kelimeler

• Stokastik seyahat süresi
• araç rotalama problemi
• afet yönetimi
• metasezgisel algoritma

Post-Disaster Vehicle Routing Problem Under Uncertain Time

Abstract

Humanitarian aid supplies must be delivered to post-disaster victims in post-disaster gathering areas as soon as possible. After a disaster, people want to get away from the disaster area or people who are curious about their relatives want to go to the disaster area to get information, which can cause traffic on the roads. For this reason, transportation time on the roads may vary. In the problem where the primary aim is to minimize the total reaching time, the travel time between nodes is considered stochastic. Since the vehicle routing problem is an NP-Hard class problem, the best solution may not be obtained with exact solution methods as the problem size increases. Therefore, heuristic algorithms are needed. The adaptive large neighborhood search algorithm has been applied to solve this problem. In small examples, the results obtained with the exact solution method and the heuristic algorithm are compared and the solution quality is found to be good. The developed metaheuristic algorithm is also used to solve medium-sized problems.

Keywords

• Stochastic travel time
• vehicle routing problem
• disaster management
• metaheuristic algorithm

Kaynakça

1. [1] Bozorgi-Amiri, A., Khorsi, M., (2016), A dynamic multi-objective location-routing model for relief logistic planning under uncertainty on demand, travel time, and cost parameters. Int J Manuf Technol 85: 1633-1648, DOI 10.1007/s00170-015-7923-3
2. [2] Liu, H., Sun, Y., Pan, N., Li, Y., An, Y., Pan, D., (2022), Study on the optimization of urban emergency supplies distribution paths for epidemic outbreaks, Computers and Operations Research, 146 105912, https://doi.org/10.1016/j.cor.2022.105912
3. [3] Zhang, Y., Liu, J., (2021), Emerceny logistics scheduling under uncertain transportation time using online optimization methods, IEEE Access, Vol. 9, DOI 10.1109/ACCESS.2021.3061454
4. [4] Mohammadi, S., Darestani, S., A., Vahdani, B., Alinezhad, A., (2020). A robust neutrosophic fuzzy-based approach to integrate reliable facility location and routing decisions for disaster relief under fairness and aftershocks concerns. Computers&Industrial Engineering. 148, 106734
5. [5] Molina, J., Lopez-Sanchez, A.,D., Hernandez-Diaz, A.,G., Martinez-Salazar, I., (2018). A multi-start algorithm with intelligent neighborhood selection for solving multi-objective humanitarian vehicle routing problem. Journal of Heuristics, 24:111-133
6. [6] Penna, H., V., P., Santos, A., C., Prins, C., (2017), Vehicle routing problems for last mile distribution after majör disaster, Journal of the Operational Research Society, 69:8, 1254-1268, https://doi.org/10.1080/01605682.2017.1390534
7. [7] Nodoust, S., Pishvaee, M., S., Seyedhosseini, S., M., (2021), Vehicle routing problem for humanitarian relief distribution under hybrid uncertainty, Kybernetes, Vol. 52, No 4, 1503-1527, https://doi.org/10.1108/K-09-2021-0839
8. [8] Anuar, W., K., Lee, S., L., Pickl, S., (2022), Benchmark dataset for multi depot vehicle routing problem with road capacity and damage road consideration for humanitarian operation in critical supply delivery, Data in Brief, 41 107901, https://doi.org/10.1016/j.dib.2022.107901

9. [9] Chang, Kuo-Hao, Hsiung, T-Y, Chang, T-Y, (2022), Multi-commodity distribution under uncertainty in disaster response phase:Model, solution method, and an empirical study, European Journal of Operational research, 303 857-876, https://doi.org/10.1016/j.ejor.2022.02.055
10. [10] Bruni, M., E., Khodaparasti, S., Beraldi, P., (2020), The selective minimum latency problem under travel time variability: An application to post-disaster assessment operations. Omega, 102154, https://doi.org/10.1016/j.omega.2019.102154
11. [11] Ahmadi, M., Seifi, A., Tootooni, B., (2015). A humanitarian logistics model for disaster relief operation considering network failure and standard relief time: A case study on Francisco district, Transportation Research Part E, 75 145-463
12. [12] Elçi, N., Noyan, N., (2018), A chance-constrained two-stage stochastic programming model for humanitarian relief network design, Transportation Research Part B 108, 55-83, https://doi.org/10.1016/j.trb.2017.12.002
13. [13] Uslu, A., Çetinkaya, C., İşleyen, S., K., (2017), Vehicle routing problem in post-disaster humanitarian relief logistics : a case study in Ankara, Sigma Journal of Engineering and Natural Sciences, 35 (3), 481-499
14. [14] Barbarasoğlu, G., Arda, Y., (2004), A two-stage stochastic programming framework for transportation planning in disaster response, Journal of the Operational researh Society 55, 43-53. https://doi.org/10.1057/palgrave.jors.2601652
15. [15] Li, Y., Chung, S., H., (2018), Disaster relief routing under uncertainty: A robust optimisation approach, IISE Transactions, 51:8, 869-886, https://doi.org/10.1080/24725854.2018.1450540
16. [16] Che, Y., Zhang, Z., (2023), An integer L-shaped algorithm for vehicle routing problem with simultaneous delivery and stochastic pickup, Computers&Operations Research 154, 106201
17. [17] Wolgemuth, S., Oloruntoba, R., Clausen, U., (2012), Dynamic vehicle routing with anticipation in disaster relief, Socio-Economic Planning Sciences 46, 261-271, http://dx.doi.org/10.1016/j.seps.2012.06.001
18. [18] Maghfiroh, M., F., N., Hanaoka, S., (2018), Dynamic truck and trailer routing problem for last mile distribution in disaster response, Journal of humanitarian logistics and supply chain management, Vol 8, No2, 252-278, DOI 10.1108/JHLSCM-10-2017-0050
19. [19] Mulumba, T., Diabat, A., (2024), The drone-assisted pickup and delivery problem: An adaptive large neighborhood search metaheuristic, Computers&Operations Research, 161 106435
20. [20] Allahviranloo, M., Chow, J., Y., J., Recker, W., W., (2014), Selective vehicle routing problems under uncertainty without recourse, Transportation Research Part E, 62, 68-88, http://dx.doi.org/10.1016/j.tre.2013.12.004
21. [21] Çetin Kaya, Y., Kaya, M., Akdağ, M., (2021), Route optimization for medication delivery of Covid-19 Patients with drones. Gazi University Journal of Science, Part C: Design and Technology, 9(3): 478-491
22. [22] Anuar, W., H., Lee, L., S., Pickl, S., Seow, Hsin-Vonn, (2021), A vehicle routing optimisation in humanitarian operations: A survey on modelling and optimisation approaches, Applied Sciences 11,667, https://doi.org/10.3390/app11020667
23. [23] Yanez-Sandivari, L., Cortes, C., E., Rey, P., A., (2021), Humanitarian logistics and emergencies management: New perspectives o a sociotechnical problem and its optimization approach management, International Journal of Disaster Risk reduction. 52 101952, https://doi.org/10.1016/j.ijdrr.2020.101952
24. [24] Shi, Y., Liu, W., Zhou, Y., (2023) An adaptive large neighborhood search based approach for the vehicle routing with zone-based pricing, Engineering Applications of Artificial Intelligencei 124 106506
25. [25] Wang, S., Sun, W., Huang, M., (2024), An adaptive large neighborhood search for the multi-depot vehicle routing problem with time windows, Computers& Industrial Engineering 191, 110122
26. [26] Huang, M., Liu, M., Kuang, H., (2024), Vehicle routing problem for fresh products distribution considering customer satisfaction through adaptive large neighborhood search, Computers& Industrial Engineering 190, 110022