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

Yıl 2018, Cilt: 23 Sayı: 4, 27 - 40, 31.12.2018

Merve Köse Küçük , Fatih Çavdur

https://doi.org/10.17482/uumfd.455283

Cited By: 1

Öz

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.

Anahtar Kelimeler

Vehicle routing problem, humanitarian relief logistics, integer programming, transportation plan

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

Öz

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.

Anahtar Kelimeler

Araç rotalama problemi, insani yardım lojistiği, tamsayılı programlama

Kaynakça

• 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
• 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
• 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 Sebatli, A. (2016) Allocation of temporary disaster response facilities under demand uncertainty: An earthquake case study, International Journal of Disaster Risk Reduction, 19, 159-166. doi:10.1016/j.ijdrr.2016.08.009
• Chern, C. C., Chen, Y. L. ve Kung, L. C. (2010) A heuristic relief transportation planning algorithm for emergency supply chain management, International Journal of Computer Mathematics, 87(7), 1638-1664. doi:10.1080/00207160802441256
• Clarke, G. ve Wright, J.W. (1964) Scheduling of Vehicles from a Central Depot to a Number of Delivery Points, Operations Research, 12, 568-581. doi:10.1287/opre.12.4.568
• Cordeau, J. F., Gendreau, M., Laporte, G., Potvin, J. Y. ve Semet, F. (2002) A guide to vehicle routing heuristics, Journal of the Operational Research Society, 53(5), 512-522. doi: 10.1057=palgrave=jors=2601319
• Cornillier, F., Laporte, G., Boctor, F. F. ve Renaud, J. (2009) The petrol station replenishment problem with time windows. Computers and Operations Research, 36(3), 919-935. doi:10.1016/j.cor.2007.11.007
• Dantzig, G.B. ve Ramser, J.H. (1959) The truck dispatching problem, Management Science, 6(1), 80-91.
• Ernst, R. (2003) The academic side of commercial logistics and the importance of this special issue, Forced Migration Review, 18(1), 5-8.
• Franca, P. M., Gendreau, M., Laporte, G., ve Müller, F. M. (1995) The m-traveling salesman problem with minmax objective, Transportation Science, 29(3), 267-275. doi:10.1287/trsc.29.3.267
• Gillett, B.E. ve Miller, L.R. (1971) A Heuristic Algorithm For the Vehicle Dispatch Problem, Operation Research, 22, 340-349. doi:10.1287/opre.22.2.340
• Golden, B., Raghavan, S. ve Wasil, E. (2008) The vehicle routing problem latest advances and new challenges, Springer, Berlin.
• Haghani, A. ve Oh, S. (1996) Formulation and solution of a multi-commodity, multi-modal network flow model for disaster relief operations, Transportation Research Part A, 30(3), 231-250. doi:10.1016/0965-8564(95)00020-8
• https://aats.afad.gov.tr/sozluk4.php, Erisim Tarihi: 23.07.2018, Konu: T.C. Başbakanlık Afet ve Acil Durum Yönetimi Başkanlığı Açıklamalı Afet Yönetimi Terimleri Sözlüğü.
• Jotshi, A., Gong, Q. ve Batta, R. (2009) Dispatching and routing of emergency vehicles in disaster mitigation using data fusion, Socio-Economic Planning Sciences, 43(1), 1-24. doi:10.1016/j.seps.2008.02.005
• Laporte, G. (1992) The vehicle routing problem: An overview of exact and approximate algorithms, European Journal of Operational Research, 59(3), 345-358. doi:10.1016/0377-2217(92)90192-C
• Laporte, G. ve Osman, I. H. (1995) Routing problems: A bibliography, Annals of Operations Research, 61(1), 227-262. doi:10.1007/BF02098290
• Laporte, G. (2009) Fifty years of vehicle routing, Transportation Science, 43(4), 408-416. doi:10.1287/trsc.1090.0301
• Lenstra, J.K. ve Kan, A.H.G. (1981) Complexity of Vehicle and Scheduling Problems, Networks, 11(2), 221-227. doi:10.1002/net.3230110211
• Liberatore, F., Pizarro, C., Simon de Blas, C., Ortuno, M.T. ve Vitoriano, B. (2013) Uncertainty in Humanitarian Logistics for Disaster Management. A Review, Book Chapter, Decision Aid Models for Disaster Management and Emergencies, Atlantis Computational Intelligence Systems, Atlantis Press.
• Mete, H.O ve Zabinsky, Z.B. (2010) Stochastic optimization of medical supply location and distribution in disaster management, International Journal of Production Economics, 126(1), 76-84. doi:10.1016/j.ijpe.2009.10.004
• Nagurney, A., Yu, M. ve Qiang, Q. (2011) Supply chain network design for critical needs with outsourcing, Papers in Regional Science, 90(1), 123-142. doi:10.1111/j.1435-5957.2010.00317
• Natarajarathinam, M., Capar, I. ve Narayanan, A. (2009) Managing supply chains in times of crisis: a review of literature and insights, International Journal of Physical Distribution and Logistic Management, 39(7), 535-573. doi:10.1108/09600030910996251
• Ozdamar, L., Ekinci, E. ve Kucukyazici, B. (2004) Emergency logistics planning in natural disasters, Annals of Operations Research, 129, 217–245. doi:10.1023/B:ANOR.0000030690.27939.39
• Ozdamar, L. ve Demir, O. (2012) A hierarchical clustering and routing procedure for large scale disaster relief logistics planning, Transportaion Research Part E, 48(3), 591-602. doi.org/10.1016/j.tre.2011.11.003
• Pessoa, A., Uchoa, E. ve Poggi de Aragao, M. (2009) A robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem, Networks: An International Journal, 54(4), 167-177. doi:10.1002/net.20330
• Rawls, C.G. ve Turnquist, M.A. (2010) Pre-positioning of emergency supplies for disaster response, Transportation Research Part B, 44(4), 521-34. doi:/10.1016/j.trb.2009.08.003
• Salman, F.S. ve Gul, S. (2014) Deployment of field hospitals in mass casualty incidents, Computers & Industrial Engineering, 74, 37-51. doi:10.1016/j.cie.2014.04.020
• Shen, Z., Dessouky, M. ve Ordonez, F. (2005) Stochastic vehicle routing problem for large-scale emergencies, Technical Report, University of Southern California, Los Angeles.
• Sheu, J. B., Chen, Y. H., ve Lan, L. W. (2005) A novel model for quick response to disaster relief distribution. Proceedings of the Eastern Asia Society for Transportation Studies, 5(1), 2454-2462.
• Sheu, J.B. (2010) Dynamic relief-demand management for emergency logistics operations under large-scale disasters, Transportation Research Part E, 46(1), 1-17. doi:10.1016/j.tre.2009.07.005
• Toth, P., ve Vigo, D. (2014). Vehicle routing: problems, methods, and applications, Society for Industrial and Applied Mathematics. doi:10.1137/1.9781611973594.fm
• Tzeng, G. H., Cheng, H. J. ve Huang, T. D. (2007) Multi-objective optimal planning for designing relief delivery systems, Transportation Research Part E: Logistics and Transportation Review, 43(6), 673-686. doi:10.1016/j.tre.2006.10.012
• Wen, M., Cordeau, J. F., Laporte, G. ve Larsen, J. (2010) The dynamic multi-period vehicle routing problem, Computers and Operations Research, 37(9), 1615-1623. doi:10.1016/j.cor.2009.12.002
• Yi, W. ve Kumar, A. (2007) Ant colony optimization for disaster relief operations, Transportation Research Part E: Logistics and Transportation Review, 43(6), 660-672. doi:10.1016/j.tre.2006.05.004
• Yi, W. ve Ozdamar L. (2007) A dynamic logistics coordination model for evacuation and support in disaster response activities, European Journal of Operational Research, 179(3), 1177-1193. doi:10.1016/j.ejor.2005.03.077