مکان یابی مراکز امداد موقت و مسیریابی پویای وسایل نقلیه امداد هوایی در شرایط بحران

نوع مقاله : مقاله پژوهشی

نویسندگان

1 دانشگاه صنعتی اصفهان

2 دانشیار، دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان، اصفهان، ایران

3 استادیار، دانشکده مهندسی صنایع و سیستم ها، دانشگاه صنعتی اصفهان، اصفهان، ایران

چکیده

در این مقاله یک مدل ریاضی جدید برای مکان یابی مراکز امداد موقت و مسیریابی پویای وسایل نقلیه امداد هوایی به منظور ارسال کالاهای امدادی به مناطق آسیب دیده در شرایط بحران ارائه‌شده است.تابع هدف مدل پیشنهادی شامل کمینه سازی حداکثر زمان انتقال کالاهای امدادی به مراکز تاسیس شده است. در مدل پیشنهادی مکانیابی مراکز امداد به گونه‌ای انجام می شود که تمامی نقاط آسیب دیده در شعاع پوشش مراکز تاسیس شده قرار گیرند. با توجه به شرایط حاکم به مناطق آسیب دیده  همچون نیاز ضروری به کالاهای امدادی و اهمیت زمان خدمت رسانی،وجود پس لرزه ها، برآوردهای غیر دقیق از میزان خسارتها و مناطق حادثه دیده، و خرابی شبکه راه ها در مدل ارائه‌شده مناطق و میزان تقاضای هر منطقه پویا در نظر گرفته شده و از وسائط نقلیه هوایی به منظور ارسال کالاهای امدادی بهره گرفته شده است. با توجه به NP-Hard، مدل پیشنهادی،  الگوریتم های ژنتیک و جست و جوی پراکنده برای این مسئله ارائه‌شده است، به منظور بررسی عملکرد الگوریتم های پیشنهادی نتایج حاصل از حل دقیق و الگوریتم های فرابتکاری ارائه‌شده مورد مقایسه و تحلیل قرار گرفته است. در حل مسائل نمونه در ابعاد کوچک، میانگین زمان حل برای روش دقیق، الگوریتم  ژنتیک و الگوریتم جستجوی پراکنده به ترتیب  669.8 ،  54.7 و  56.2 ثانیه بدست آمد. از نظر کیفیت جواب‌ها، متوسط خطا برای الگوریتم ژنیک 3.8 درصد و  برای الگوریتم جست و جوی پراکنده 4.1 درصد بدست آمد. در ابعاد بالا از منظر کیفیت جواب الگوریتم ژنتیک از 27 مسئله حل شده، در 17 مورد جواب‌های بهتری نسبت به الگوریتم جست و جوی پراکنده پیداکرده است. نتایج نشان دهنده عملکرد مناسب الگوریتمهای حل پیشنهادی است.

کلیدواژه‌ها

موضوعات


عنوان مقاله [English]

Locating Temporary Relief Centers and Dynamic Routing Air Rescue Vehicles in Times of Crisis

نویسندگان [English]

  • Mohammad Aghaei 1
  • Mehdi Alinaghian 2
  • Mohammad Saeid Sabagh 3
1 MSC. Grad., Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran
2 Assistant Professor, Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran
3 Assistant professor, Department of Industrial Engineering, Isfahan University of Technology, Isfahan, Iran
چکیده [English]

This paper presents a new mathematical model for location of temporary relief centers and dynamic routing of aerial rescue vehicles distributing basic supplies in relief operations. The objective function of the proposed model minimizes the time required to distribute the supplies among the designated relief centers. The proposed model seeks to locate the relief centers in a way that all affected areas get covered by at least one relief center. Considering the importance of quick action amid a post-disaster environment with characteristics such as uncertain demand for relief supplies, inaccurate information regarding victims, aftershocks, and extensively damaged road networks, in the proposed model, location and level of demand are considered to be dynamic, and relief supplies are assumed to be distributed by aerial transport vehicles. The assessed problem is of NP-Hard complexity, so, this paper also presents a scatter search and genetic algorithm to obtain its solutions. To evaluate the performance of the proposed algorithm, it is tested and compared with an exact method and other meta-heuristic algorithms. In small test problems, the average solving time for exact method, genetic algorithm and scatter search algorithm were 669.8, 54.7, and 56.2 respectively.  In view of solutions quality, the average percentage error for genetic algorithm and scatter search algorithm were 3.8 and 4.1 respectively. In the large scale problems, genetic algorithm reached to the better solution in 17 problems from 27 test problems compared to the scatter search algorithm. The results indicate the good performance of proposed algorithms.

کلیدواژه‌ها [English]

  • Dynamic routing
  • covering tour
  • scatter search algorithm
  • Genetic Algorithm
  • crisis logistics
-Abounacer, R. Rekik, M. and Renaud, J. (2014) “An exact solution approach for multi-objective location–transportation problem for disaster response”  ,Computers & Operations Research, Vol.41, No.1, pp.83-93.
-Afshar, Abbas and Haghani, Ali (2012)  “ Modeling integrated supply chain logistics in real-time large-scale disaster relief operations ,Socio-Economic Planning Sciences, Vol. 46, No.4, pp. 327-338.
-Balcik, B. and Beamon, B. M. (2008) Facility location in humanitarian relief , International Journal of Logistics Research and Applications, Vol. 11, No.2, PP. 101-121.
-Barbaroso glu, G., Ozdamar, L. and  Evik, A. (2002) “An  interactive approach for hierarchical analysis of helicopterlogistics in disaster relief operations”, European Journal of Operational Research, Vol. 140, No.1, pp. 118-133.
-Caunhye, A. M., Nie, X. and Pokharel, S. (2012) “Optimization models in emergency logistics: A literature review”, Socio-Economic Planning Sciences, Vol.46, No.1, pp. 4-13.
-Caunhye, A. M., Nie, X. and Pokharel, S. (2012) “Optimization models in emergency logistics: A literature review”, Socio-Economic Planning Sciences,Vol. 46, No.1, pp. 4-13.
-Chang, M. S., Tseng, Y. L. Chen, J. W. (2007) “A scenario planning approach for the flood emergency logistics preparation problem under uncertainty,  Transportation Research Part E, Vol. 43, No.l, pp. 734-751.
-Chou, H. W., Hsueh, C. F. and Chen, H. K. (2008) “Dynamic vehicle routing for relief logistics in natural disasters, INTECH Open Access Publisher.
-Fontem, B., Melouk, S. H., Keskin, B. B. and Bajwa, N. (2016) “A decomposition-based heuristic for stochastic emergency routing problems. Expert Systems with Applications, Vol 59, No. 1, pp 47-59.
-Ferrucci, F., Bock, S. and Gendreau, M. (2013) “A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods”,  European Journal of Operational Research, Vol. 225, No.1, pp.130-141.
-Goldberg, D. E. and Holland, J. H. (1988) “ Genetic algorithms and machine learning, Machine learning,Vol. 3, No.2, pp. 95-99.
-Chen, Huey-Kuo, Hsueh, Che-Fu and Chang, Mei-Shiang (2006) “The real-time time-dependent vehicle routing problem, Transportation Research Part E, Vol.42, pp. 383–408.
- Ege,  Jose A. (2007) “Improved scatter search for the global optimization of computationally expensive and support in disaster response activities “, European Journal of Operational Research, Vol.179, No.1, pp.1177–1193.
-Jang, H. C., Lien, Y. N. and Tsai, T. C.) 2009) “Rescue information system for earthquake disasters based on MANET emergency communication platform, Proceedings of the 2009 International Conference on Wireless Communications and Mobile Computing: Connecting the World Wirelessly, ACM, pp. 623-627.
-Knott, R. (1987) “The logistic of bulk relief supplies”, Disasters, Vol.11, No.2, pp.113-115.
-Mete, O.H. Zabinsky, Z.B(2007) “Stochastic optimization of medical supply location and distribution in disaster management, International Journal of Production Economics, Vol. 126, No.1 , PP. 76-84.
-Najafi, M., Farahani, R. Z., De Brito, M. P.and Dullaert, W. (2015) “Location and distribution management of relief centers: a genetic algorithm approach”, International Journal of Information Technology & Decision Making, Vol.14, No.4, pp.769-803.
-Nolz, P. C.و Doerner, K. F., Gutjahr, W. J. and Hartl, R. F. (2010) “A bi-objective metaheuristic for disaster relief operation planning, In: Coello, C.A. et al. (Eds.) A dv. in Multi- Objective Nature Inspired Computing, Vol. 272, No.1,  pp.167–187.
-Rivera, J. C., Afsar, H. M. and Prins, C. (2016) “Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem”, European Journal of Operational Research, Vol.249. No.1, pp.93-104.
-Ozdamar, Linet (2007) “A dynamic logistics coordination model for evacuation namic models, Journal of Global Optimization, Vol.43, No.1, pp. 175-190
-Ozdamar, L. Ekinci, E. and Kucukyazici, B. (2004) “Emergency logistics planning in natural disasters, AnnOperations Res, Vol.129, pp.217–245.
-Sakakibara, H., Kajitani, Y. and Okada, P. (2004) “.Road network robustness for avoiding functional isolation in disasters”, J. Transport. Engng –ASCE, Vol.130, pp.560–567.
-Taguchi, G. Chowdhury, S. and Wu, Y. (2005) “Taguchi's quality engineering handbook”, Wiley.
-Pillac, Victor, Gendreau ,  Michel, Gueret, Christelle and Medaglia, Andres (2013). “A review of dyanamic vehicle routng problem”, European Journal of Operational Research, Vol.225, pp. 1–11.
-Victoria, J. F., Afsar, H. M. and Prins, C. (2016) “ Column generation based heuristic for the vehicle routing problem with time-dependent demand”, IFAC-PapersOnLine, Vol. 49, No. 12, pp. 526-531.
-Yi, W. and Özdamar, L. (2007) “A dynamic logistics coordination model for evacuation and support in disaster response activities, European Journal of Operational Research, Vol. 179, pp. 1177-1193.