الگوریتم شاخه و کران برای مسئله‌ برون‌بری- مکان‌یابیِ (ایستا و پویای استوار) در لجستیکِ اضطراری

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

نویسندگان

1 دانشجوی دکتری، دانشکده مهندسی صنایع و سیستم‌ها، دانشگاه تربیت مدرس، تهران، ایران

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

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

4 دانشیار، دانشکده مهندسی صنایع، دانشگاه علم و صنعت ایران،‌ تهران، ایران

چکیده

فرآیند تخلیه از کلیدی‌ترین فعالیت‌های همزمان با بحران هنگام رخداد فجایع است. در پژوهش‌های مدیریت بحران، فرض بر وجود مکان‌های اسکان اضطراریِ از پیش‌تعیین‌شده‌ای است که تخلیه افراد از نواحی بحران‌زده به سوی آن‌ها انجام می‌شود. ما در این مقاله در پیِ یافتن یک پایگاه اسکان از میان مجموعة پایگاههای پیش‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌‌بینی‌شده هستیم که جریان تخلیه افراد از ناحیة بحران را بیشینه می‌کند و بنابراین امکان تصمیم‌‌گیری دربارة مکان‌های امن را همزمان با وقوع بحران برای تصمیم‌‌گیرندگان فراهم می‌کند. این مسئله را به صورت دو مدل غیرخطی در حالت ایستا و پویا، و با رویکرد شبکة جریان مدل‌سازی می‌کنیم. علاوه بر این یک مدل استوار پویا برای مسئلة تخلیه-مکان‌یابی توسعه داده‌ایم تا عدم قطعیت مربوط به ظرفیت مسیرها در هنگام رخداد بحران را نیز در نظر بگیریم. در این مقاله، برای نخستین بار متغیر تصمیم مکان‌یابی را در مدل بیشینه جریان وارد کرده‌ایم. سپس با استفاده از ساختار مدل‌ها دو کران بالا و دو الگوریتم بهینه برای حل آنها توسعه می‌دهیم. الگوریتم‌های بهینه را بر پایه‌ی ترکیب روش‌های موجود برای بیشینه‌سازی جریان شبکه با روش شاخه و کران توسعه داده‌ایم. عملکرد کران‌های بالا را با حل مسئله‌های تصادفی هم از نظر زمان حل و هم فاصله با حل بهینه می‌سنجیم. زمانِ اجرای الگوریتم‌های دقیق را نیز بر روی همین مسئله‌های تصادفی می‌آزماییم و نتیجة مقایسه را گزارش می‌نماییم. در پایان نیز، الگوریتم‌های پیشنهادی را برای داده‌های واقعی یک شبکه شهری به کار گرفته و نتایج آن را گزارش کرده‌ایم.

واژگان کلیدی: لجستیک بحران، مسئله تخلیه-مکان‌یابی، مسئله شبکه جریان، شبکه جریان ایستا، شبکه جریان پویا، ‌مدل استوار پویا

کلیدواژه‌ها

موضوعات


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

Branch and Bound Algorithms for Static and Robust Dynamic Evacuation-Location Problem in Emergency Logistics

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

  • Mina Mazrae Farahani 1
  • Seyed Kamal Chaharsooghi 2
  • Isa Nakhaei Kamalabadi 3
  • Ebrahim Teymouri 4
1 Ph.D. Student, Department of Industrial Engineering and Systems, Tarbiat Modares University, Tehran, Iran
2 Associate Professor, Department of Industrial Engineering and Systems, Tarbiat Modares University, Tehran, Iran
3 Professor, Department of Industrial Engieering and Systems, Kurdestan University, Sanandaj, Iran
4 Associate Professor, Department of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
چکیده [English]

Evacuating people to the safe zones is the most crucial operation in managing many disasters. We have presented mathematical models in this paper, in order to combine the locational decisions with the max-flow problem in order to select the safe destination that maximizes the number of dispatched people, both for the static and dynamic cases. Existing frameworks for emergency logistics, address the evacuation process based on fixed and pre-determined destinations usually with a strategic perspective. The unpredictable and turbulent nature of a disaster may, however, disrupt the predictions. Furthermore, the primary goal in emergency situations is to dispatch people from the danger zone to a safe place, no matter where. A non-linear integer programming model is developed in this paper for selecting one destination in a capacitated network. We have also formulated the robust counterpart of the dynamic model in order to contribute the uncertainty of the capacity of routes during a disaster. The special structure of the model and its similarity to the max-flow problem let us develop exact algorithms and heuristics for the single destination location problem. The solution methods are based on combining a branch and bound approach with the existing algorithms for the max-flow problem. Our proposed heuristics use the idea of adding a super-sink to the network to generate upper bounds very fast. The exact algorithms as well as the heuristics are tested on randomly generated instances as well as a real world network. The mean and variance of their computation times are reported. They are compared according to their performance (gap to optimality) and their behavior amongst different categories of the graphs. We have also used the real data for Mitte-center Berlin to implement our algorithms for an existing data set. The results of the algorithms for this case are also reported in the results section.

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

  • Branch and bound algorithms
  • Evacuation
  • Disasters
  • mathematical models
  • heuristics
-Abdelgawad H. and Abdulhai, B. (2009) “Emergency evacuation planning as a network design problem: A critical review”, Transportation Letters: The International Journal of Transportation Research, Vol. 1, No. 1, pp.41-58.
-Ahmadi, M., Seifi, A. and Tootooni, B. (2015) “A humanitarian logistics model for disaster relief operation considering network failure and standard relief time: a case study on San Francisco district”, Transp Res Part E Vol. 75, pp.145–163
-Ahuja, R. K., Magnanti, Th. K. and Orlin. J. B. (1993) “Network flows”, Prentice Hall, New Jersey.
-Akgün, İ., Gümüşbuğa, F. and Tansel, B. (2015) "Risk based facility location by using fault tree analysis in disaster management", Omega, Vol. 52, pp.168-179.
- Bar-Gera, H. (2005) “Berlin mitte center network”, https://github.com/bstabler/TransportationNetworks/tree/master/Berlin-Mitte-Center.
-Bell, M. G. H., Fonzone, A. and Polyzoni, C. (2014) “Depot location in degradable transport networks”, Transp. Res. Part B Methodol. Vol. 66, pp. 148–161. doi:10.1016/j.trb.2013.11.003.
-Ben-Tal, A. and Nemirovski, A. (2002) “Robust optimization–methodology and applications”, Mathematical Programming, Vil. 92, No. 3,  pp.453-480.
-Ben-Tal, A., Goryashko, A., Guslitzer, E. and Nemirovski, A. (2004) “Adjustable robust solutions of uncertain linear programs”, Mathematical Programming, Vol. 99, No. 2, pp.351-376.
-Boonmee, C., Arimura, M. and Asada, T. (2017) “Facility location optimization model for emergency humanitarian logistics”, International Journal of Disaster Risk Reduction, Vol. 24, pp. 485-498.
-Cavdur, F., Kose-Kucuk, M. and Sebatli, A. (2016) "Allocation of temporary disaster response facilities under demand uncertainty: An earthquake case study", International Journal of Disaster Risk Reduction, Vol. 19, pp.159-166.
-Chalmet L. G., Francic, R. L. and Saunders, P. B. (1982) “Evacuation network models for building evacuation”, Management Science, (January), Vol. 18, No. 1, pp 90-113.
-Chen, A.Y., Yu, T.-Y., Lu, T.-Y., Chuang, W.-L., Lai, J.-S., Yeh, C.-H. and Sun, W.-Z. (2015) “Ambulance service area considering disaster-induced disturbance on the transportation infrastructure”, J. Test. Eval. 43, 20140084. DOI:10.1520/JTE20140084.
-Chen, A. Y. and Yu, T. Y. (2016) "Network based temporary facility location for the Emergency Medical Services considering the disaster induced demand and the transportation infrastructure in disaster response", Transportation Research Part B: Methodological, Vol. 91, pp.408-423.
-Fleischer, L. and Skutella, M. (2002) “The quickest multicommodity flow problem”, In W. J. Cook and A. S. Schulz, “Integer Programming and Combinatorial Optimization”, Vol. 2337 of Lecture Notes in Computer Science, pp. 36–53.
-Fleischer, L. and Skutella, M. (2006) “The quickest multicommodity flow problem”, In Integer Programming and Combinatorial Optimization (pp. 36-53). Springer Berlin Heidelberg.
-Fleischer, L. (2001) “Faster algorithms for the quickest transshipment problem”, SIAM J. on Optimization, Vol. 12, No. 1, pp. 18–35.
-Fleischer, L. (2001) “Universally maximum flow with piecewise-constant capacities”, Networks, Vol. 38, No. 3, pp.115–125.
-Ford L. R. and Fulkerson, D. R. (1958) “Constructing maximal dynamic flows from static flows”, Operations Research, Vol. 6, pp.419–433.
-Ford, L. R. and Fulkerson, D. R. (1962) “Flows in networks”, Princeton University Press”, Princeton, NJ.
-Friesz, T. L., Lee, I. and Lin, C. C. (2011) “Competition and disruption in a dynamic urban supply chain”, Transportation Research Part B, Vol. 45, No. 8, pp. 1212–1231.
-Ghatreh Samani, M. and Hosseini-Motlagh, S. M. (2017) “A hybrid algorithm for a two-echelon location-routing problem with simultaneous pickup and delivery under fuzzy demand”, International Journal of Transportation Engineering, Vol. 5, No. 1, pp. 59-85.
-Ghezavati, V., Soltanzadeh, F. and Hafezalkotob, A. (2015) "Optimization of reliability for a hierarchical facility location problem under disaster relief situations by a chance-constrained programming and robust optimization", Proceedings of the Institution of Mechanical Engineers, Part O: Journal of Risk and Reliability, Vol. 229, No. 6, pp. 542-555.
-Hamacher, H.W., Heller, S. and Rupp, B. (2013) “Flow location (FlowLoc) problems: dynamic network flows and location models for evacuation planning”, Annals of Operations Research, Vol. 207, No. 1, pp. 161-180.
-Hoppe B. and Tardos. É. (1994) “Polynomial time algorithms for some evacuation problems”, In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 433–441.
-Horner M. W. and Downs, J. A. (2010) “Optimizing hurricane disaster relief goods distribution: model development and application with respect to planning strategies”, Disasters, Vol. 34, No. 3, pp.821e44.
-Hoyos, M. C., Morales, R. S. and Akhavan-Tabatabaei, R. (2015) "OR models with stochastic components in disaster operations management: A literature survey", Computers & Industrial Engineering, Vol. 82, pp.183-197.
-Huang, M., Smilowitz, K. R. and Balcik, B. (2013) “A continuous approximation approach for assessment routing in disaster relief”, Transp. Res. Part B: Methodology. Vol. 50, pp. 20–41. DOI:10.1016/j.trb.2013.01.005.
-Jia H., Ordóñez F. and Dessouky, M. M. (2007) “Solution approaches for facility location of medical supplies for large-scale emergencies”, Computers and Industrial Engineering; Vol. 52, No. 2, pp.257-276.
-Klinz, B. and Woeginger, G. J. (2004) “Minimum-cost dynamic flows: The series-parallel case”, Networks, Vol. 43, pp. 153–162. DOI:10.1002/net.10112.
-Köhler, E. and Skutella. M. (2002) “Flows over time with load-dependent transit times”, Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’02), pp. 174–183.
-Kotnyek, B. (2003) “An annotated overview of dynamic network flows”, France: Institut National de Rechereche Informatique ET en Automatique.
-Najafi, M., Eshghi, K. and Dullaert, W. (2013) “A multi-objective robust optimization model for logistics planning in the earthquake response phase”, Transp. Res. Part E, Vol. 49, pp. 217–249.
-Nappi, M. M. L. and Souza, J. C. (2015) "Disaster management: Hierarchical structuring criteria for selection and location of temporary shelters", Natural Hazards, Vol. 75, No. 3, pp. 2421-2436.
-Özdamar, L. and Ertem, M. A. (2015) "Models, solutions and enabling technologies in humanitarian logistics", European Journal of Operational Research, Vol. 244, No. 1, pp. 55-65.
-Peng, P., Snyder, L.V., Lim, A. and Liu, Z. L. (2011) “Reliable logistics networks design with facility disruptions”, Transportation Research Part B, Vol. 45 No. 8, pp. 1190–1211.
-Philpott, A. B. (1990) “Continuous-time flows in networks”, Mathematics of Operations Research, Vol. 15 No. 4, pp-640–661.
 -Powell, W. B., Jaillet, P. and Odoni, A. (1995) “Stochastic and dynamic networks and routing”,  In M. O. et al. Ball, editor, Handbooks in Operations Research and Management Science – Network Routings, Volume 8, Chapter 3. Elsevier Science.
-Qi, L., Shen, Z. M. and Snyder, L. V. (2010) “The effect of supply disruptions on supply chain design decisions”, Transportation Science, Vol. 44, No. 2, 274–289.
-Rezaei-Malek, M., Tavakkoli-Moghaddam, R., Zahiri B. and Bozorgi-Amiri, A. (2016) “An interactive approach for designing a robust disaster relief logistics network with perishable commodities”, Comput Ind Eng Vol. 94, pp.201–215
-Salman, F. S. and Yücel, E. (2015) "Emergency facility location under random network damage: Insights from the Istanbul case", Computers & Operations Research, Vol. 62, pp.266-281.
 -Sbayti, H. and Mahmassani, H. (2006) “Optimal scheduling of evacuation operations”, Transportation Research Record: Journal of the Transportation Research Board, Vol. 1964, pp. 238–246.
-Schneeberger, K., Doerner, K. F., Kurz, A. and Schilde, M. (2016) "Ambulance location and relocation models in a crisis", Central European Journal of Operations Research, Vol. 24, No. 1, pp. 1-27.
-Shen, Z. M., Zhan, R. and Zhang, J. (2011) “The reliable facility location problem: formulations, heuristics, and approximation algorithms”, Informs Journal on Computing, Vol. 23, No. 3, pp. 470–482.
-Tofighi, S., Torabi, S. A. and Mansouri, S. A. (2016) “Humanitarian logistics network design under mixed uncertainty”, European Journal of Operations Research, Vol. 250, No. 1, pp.239–250
-Ye, F., Zhao, Q., Xi, M. and Dessouky, M. (2015) “Chinese national emergency warehouse location research based on VNS Algorithm”, Electronic Notes in Discrete Mathematics, Vol. 47, pp.61-68.
 -Yuan, Y. and Wang, D. (2009) “Path selection model and algorithm for emergency logistics management”, Computers & Industrial Engineering, Vol. 56, No. 3, pp.1081–1094.
آقایی، م.، علینقیان، م. و  صباغ، م. س. (1396) "مکان یابی مراکز امداد موقت و مسیریابی پویای وسایل نقلیه امداد هوایی در شرایط بحران"،فصلنامه علمی - پژوهشی مهندسی حمل و نقل.، دوره 9، شماره 4، ص. 519-548
 ترابی، س.ع. و خلیلی، س. م. (1391) "ارائه یک مدل مکان­یابی- تخصیص دو هدفه برای توزیع کالاهای امدادی در فاز مدیریت بعد از بحران"، دومین کنفرانس ملی مدیریت بحران.