Journals / Uludağ Üniversitesi Mühendislik Fakültesi Dergisi / 2018 / Cilt: 23 - Sayı: 4

Use of Route Generation-Elimination Algorithm and Integer Programming for Post-Disaster Relief Supplies Distribution

AFET SONRASI YARDIM MALZEMESİ DAĞITIMI İÇİN ROTA ÜRETME-ELEME ALGORİTMASI VE TAMSAYILI PROGRAMLAMA KULLANIMI

Pages
27–40
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

The proposed approach is tested on an earthquake case study for a sample region and the results are analyzed.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:In this study, the problem of post disaster relief supplies transportation is modeled as a capacity-constrained vehicle routing problem.
📊
Key Findings & Data:In the first phase of the proposed approach, a route generation-elimination algorithm is used to generate feasible routes that satisfy the capacity constraints.
💡
Conclusion & Impact:The proposed approach is tested on an earthquake case study for a sample region and the results are analyzed.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Araç rotalama problemi · insani yardım lojistiği · tamsayılı programlama

Abstract

In this study, the problem of post disaster relief supplies transportation is modeled as a capacity-constrained vehicle routing problem. A two-phase solution approach is proposed to solve the problem. In the first phase of the proposed approach, a route generation-elimination algorithm is used to generate feasible routes that satisfy the capacity constraints. In the second phase, the feasible routes generated by the algorithm are used as the input of the proposed integer programming model to determine the transportation plan showing the routes through which the relief supplies are transported. Despite the long solution times due to the NP-hard structure of the capacity-constrained vehicle routing problem, it is aimed at obtaining a solution in a shorter time period with the generated route generation-elimination algorithm. Since the vehicle capacity constraints are taken into consideration in the route generation-elimination algorithm, the corresponding capacity constraint in the integer programming model is removed which significantly reduces the complexity of the problem. This situation represents the positive effect of the developed algorithm on the solution time. The proposed approach is tested on an earthquake case study for a sample region and the results are analyzed.

Özet

Bu çalışmada, afet sonrası yardım malzemesi taşıma problemi, literatürde yer alan kapasite kısıtlı araç rotalama problemi olarak kurgulanmış ve çözümü için iki-aşamalı çözüm yaklaşımı geliştirilmiştir. Geliştirilen yaklaşımın ilk aşamasında, rota üretme-eleme algoritması ile araç kapasite kısıtını sağlayan uygun rotaların üretilerek, bu kısıtı sağlayamayan rotalar ise elenmiştir. İkinci aşamada ise, algoritma ile üretilen uygun rotalar, önerilen tamsayılı programlama modelinin girdisi olarak kullanılmış olup, bu model ile yardım malzemelerinin hangi rotalar üzerinden ve hangi araçlarla taşınacağını gösteren bir taşıma planı oluşturulmuştur. Kapasite kısıtlı araç rotalama probleminin NP-zor yapısı sebebiyle oluşan uzun çözüm sürelerine karşın, geliştirilen rota üretme-eleme algoritması ile daha kısa sürede çözüm elde edilmesi sağlanmıştır. Rota üretme-eleme algoritmasında, araç kapasite kısıtı dikkate alındığından dolayı, tamsayılı programlama modelinde bu kısıt ortadan kaldırılmış, bu sayede problemin karmaşıklığında önemli oranda azalma sağlanmıştır. Bu durum, geliştirilen algoritmanın çözüm süresine olumlu etkisini ortaya koymaktadır. Geliştirilen yaklaşım bir deprem örnek olayı üzerinde ve örnek bir bölge için test edilmiş ve sonuçları analiz edilmiştir.

🔖

Cite This Article

KÖSE-KÜÇÜK, M., ÇAVDUR, F. (2018). Use of Route Generation-Elimination Algorithm and Integer Programming for Post-Disaster Relief Supplies Distribution. Uludağ Üniversitesi Mühendislik Fakültesi Dergisi, Cilt: 23 - Sayı: 4, 27–40. https://ajindex.com/articles/330158

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (3)

  1. Altay, N. ve Green, W.G. (2006) OR/MS research in disaster operations management, European Journal of Operational Research, 175(1), 475-493. doi:10.1016/j.ejor.2005.05.016 Applegate, D., Cook, W., Dash, S. ve Rohe, A. (2002) Solution of a min-max vehicle routing problem. INFORMS Journal on Computing, 14(2), 132-143. doi:10.1287/ijoc.14.2.132.118 Averbakh, I. ve Berman, O. (1996) A heuristic with worst-case analysis for minimax routing of two travelling salesmen on a tree, Discrete Applied Mathematics, 68(1-2), 17-32. doi:10.1016/0166-218X(95)00054-U Balcik, B. ve Beamon, B. M. (2005) Distribution network design for humanitarian relief chains, INFORMS Annual Meeting, San Francisco. Balcik, B. ve Beamon, B. M. (2008) Facility location in humanitarian relief, International Journal of Logistics: Research and Applications, 11(2),101–121. doi: 10.1080/13675560701561789 Balcik, B., Beamon, B. M. ve Smilowitz, K. (2008) Last mile distribution in humanitarian relief, Journal of Intelligent Transportation Systems, 12(2), 51-63. doi:10.1080/15472450802023329 Barbarosoglu, G., Ozdamar, L. ve Cevik, A. (2002) An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations, European Journal of Operations Research, 140(1) 118–133. doi:10.1016/S0377-2217(01)00222-3
  2. Barbarosoglu, G., Ozdamar, L. ve Cevik, A. (2002) An interactive approach for hierarchical analysis of helicopter logistics in disaster relief operations, European Journal of Operational Research, 140(1), 118-133. doi:10.1016/S0377-2217(01)00222-3
  3. Barbarosoglu, G. ve Arda, Y. (2004) A two-stage stochastic programming framework for transportation planning in disaster response, Journal of the Operational Research Society, 55(1), 43-53. doi:10.1057/palgrave.jors.2601652 Beamon, B. M. (2004) Humanitarian Relief Chains: Issues and Challenges, Proceedings of the 34th International Conference on Computers and Industrial Engineering, San Francisco, USA. Beamon, B. M. ve Kotleba, S. A. (2006) Inventory modeling for complex emergencies in humanitarian relief operations, Technical report, University of Washington, Seattle. Bellmore, M. ve Nemhauser G.L. (1966) The Travelling Salesman Problem: A Survey, Operations Research, 16(3), 538-558. doi:10.1287/opre.16.3.538 Caunhye, A. M., Nie, X. ve Pokharel, S. (2012) Optimization models in emergency logistics: A literature review, Socio-economic Planning Sciences, 46(1), 4-13. doi:10.1016/j.seps.2011.04.004 Cavdur, F., Kose-Kucuk, M. ve Se