تخصیص و زمان‌بندی واحدهای امداد در بلایای طبیعی با استفاده از الگوریتم‌های ژنتیک و بهینه سازی ازدحام ذرات

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

نویسندگان

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

چکیده

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

کلیدواژه‌ها


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

Allocation and Scheduling The Rescue Units in Natural Disasters Using Genetic and Particle Swarm Optimization Algorithms

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

  • Sina Nayeri
  • Ebrahim Asadi-Gangraj
  • saeed Emami
Department of industrial engineering, Babol Noshirvani University of Technology, babol, iran
چکیده [English]

Natural disasters, such as earthquakes, tsunamis, and hurricanes cause enormous harm each year. Thus it is necessary to have an intelligent decision support system in these disasters. To allocate and schedule rescue units efficiently, we develop a mix integer nonlinear programming model (MINLP) to minimize the sum of weighted completion times of relief operations with fatigue effect consideration. After relief to several incidents, rescuers become tired and need more time to relief the remaining incidents assigned to them. Because of the complexity of the candidate problem, finding the optimal solution for this complicated problem in a reasonable time using exact optimization tools is very time-consuming; thus, two meta-heuristics, Genetic algorithm (GA) and Enhanced particle swarm optimization (EPSO) are proposed to solve the candidate problem. The experimental results show that the GA has better performance in CPU time criteria and the EPSO generates better solutions for entire test problems.

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

  • Natural disaster management
  • Allocation & scheduling
  • Fatigue effect
  • unrelated parallel machine
1. Comfort, L. K., Ko, K., & Zagorecki. (2004). Coordination in rapidly evolving disaster response systems the role of information. American Behavioral Scientist, 48, 295–313
2. Bektas, T. (2006). The multiple traveling salesman problem:An overview of formulations and solution procedures.
Omega, 34, 209–219
3. Ajami, S., & Fattahi, M. (2009). The role of earthquake information management systems (EIMSs) in reducing destruction: A comparative study of Japan, Turkey and Iran. Disaster Prevention and Management, 18, 150–161.
4. Altay, N., & Green, W. G. III, (2006). OR/MS research in disaster operations management. European Journal
of Operational Research, 175, 475–493.
5. IFRC (2012). Disaster management – IFRC 
6. Gasparini, P., Manfredi, G., & Zschau, J. (Eds.) (2007).Earthquake early warning systems. Berlin, Heidelberg:Springer
7. Nisha de Silva, F. (2001). Providing spatial decision support for evacuation planning: A challenge in integrating technologies. Disaster Prevention and Management, 10, 11–20.
8. Pollak, E., Falash, M., Ingraham, L., & Gottesman, V. (2004). Operational analysis framework for emergency operations center preparedness training. In Proceedings of the 36th conference on winter simulation. Piscataway, NJ: IEEE.
9. Svensson, A., Holst, J., Lindquist, R., & Lindgren, G. (1996). Optimal prediction of catastrophes in autoregressive moving-average processes. Journal of Time Series Analysis, 17, 511–531.
10. UN/ISDR (2005). Hyogo framework for action:
building the resilience of nations and communities
to disasters.
11. GAO. (2006). Disaster relief: Government wide
framework needed to collect and consolidate information
to report on billions in federal funding for
the 2005 gulf coast hurricanes: GAO-06-834.
12. Saleem, K., Luis, S., Deng, Y., Chen, S.-C., Hristidis,
V., & Li, T. (2008). Towards a business continuity
information network for rapid disaster recovery,
Proceedings of the 2008 international conference on
digital Government Research ACM international
conference proceeding series.
13. Sherali, H. D., Carter, T. B., & Hobeika, A. G. (1991).
A location–allocation model and algorithm for evacuation
planning under hurricane/flood conditions.
Transportation Research Part B: Methodological, 25,
439–452.
14. Chen, R., Sharman, R., Rao, H. R., & Upadhyaya, S.
J. (2008). Coordination in emergency response management.
Communications of the ACM, 51, 66–73.
15. Airy, G., Mullen, T., & Yen, J. (2009). Market based adaptive resource allocation for distributed rescue teams. In J. Landgren & S. Jul (Eds.), Proceedings of the 6th conference on information systems for crisis response and management (ISCRAM 2009). Gothenburg, Sweden
16. Comes, T., Conrado, C., Hiete, M., Kamermans, M., Pavlin, G., & Wijngaards, N. (2010). An intelligent decision support system for decision making under uncertainty in distributed reasoning frameworks, Proceedings of the 7th international conference on information systems for crisis response and management (ISCRAM 2010). Seattle, USA.
17. Lambert, J. H., & Patterson, C. E. (2002). Prioritization
of schedule dependencies in hurricane recovery
of transportation agency. Journal of Infrastructure Systems,
8, 103–111.
18. Reijers, H. A., Jansen-Vullers, M. H., Zur Muehlen, M., & Appl, W. (2007). Workflow management systems + swarm intelligence = dynamic task assignment for emergency management applications, Proceedings of the 5th international conference on business process management (BPM 2007). Berlin, New York: Springer.
19. Tamura, H., Yamamoto, K., Tomiyama, S., & Hatono, I. (2000). Modeling and analysis of decision making problem for mitigating natural disaster risks. European Journal of Operational Research, 122, 461–468.
20. Fiedrich, F., Gehbauer, F., & Rickers, U. (2000). Optimized
resource allocation for emergency response
after earthquake disasters. Safety Science, 35, 41–57.
21. Leifler, O. (2008). Combining technical and humancentered
strategies for decision support in command
and control: The ComPlan approach, Proceedings of
the 5th conference on information systems for crisis
response and management (ISCRAM 2008). Washington,
DC.
22. Van de Walle, B., & Turoff, M. (2008). Decision support
for emergency situations, Handbook on decision
support systems 2 international handbooks on
information systems. Berlin, Heidelberg: Springer.
23. Faraj, S., & Xiao, Y. (2006). Coordination in fastresponse
organizations. Management Science, 52,
1155–1169.
24. Falasca, M., Zobel, C. W., & Fetter, G. M. (2009). An
optimization model for humanitarian relief volunteer
management, Proceedings of the 6th conference
on information systems for crisis response and management
(ISCRAM 2009). Gothenburg, Sweden.
25. Rolland, E., Patterson, R., Ward, K., & Dodin, B.
(2010). Decision support for disaster management.
Operations Management Research, 3, 68–79.
26. Wex, F., Schryen, G., & Neumann, D. (2011). Intelligent
decision support for centralized coordination
during emergency response. Proceedings of the 8th
international conference on information systems for
crisis response and management (ISCRAM 2011).
27. Wex, F., Schryen, G., & Neumann, D. (2012). Operational emergency response under informational uncertainty: A fuzzy optimization model for scheduling and allocating rescue units. Proceedings of the 9th international conference on information systems for crisis response and management (ISCRAM 2012).
28. Wex, F., Schryen, G., & Neumann, D. (2013). Decision modeling for assignments of collaborative rescue units during emergency response. In Proceedings of the 46th Hawaii international conference on system science. Wailea, HI: IEEE Computer Society Press.
29. Wex, F., Schryen, G., Feuerriegel, S., & Neumann, D (2014). Emergency response in natural disaster management: Allocation and scheduling of rescue units. European Journal Of Operational Research, 235,697- 708
30. Glover F. & Woolsey, L. (1974). Converting the 0–1
polynomial programming problem to a 0–1 linear
program. Operation Research, 22,180–182.
31. Holland, J. H. (1975). Adaptation in natural and arti
ficial systems: An introductory analysis with applications
to biology, control, and artificial intelligence: U
Michigan Press.
32. Goldberg, D. E., & Holland, J. H. (1988). Genetic algorithms
and machine learning, Machine learning,
Addison-Wesley, Boston.
33. Davis, L. (1991). A genetic algorithms tutorial, Handbook
of genetic algorithms. New York, Informa UK
Limited
34. Eberhart, R. & Kennedy, J. (1995). A New Optimizer
Using Particles Swarm Theory. Proc. Sixth International
Symposium on Micro Machine and Human
Science (Nagoya, Japan), IEEE Service Center, Piscataway,
NJ, 39-43.
35. Kennedy, J. & Eberhart, R. (1995). Particle Swarm
Optimization. IEEE Conference on Neural networks,
(Perth, Australia), Piscataway, NJ, IV, 1942-
1948.
36. Shi, Y. & Eberhart, R. C. (1998). A modified particle
swarm optimizer. In Proceedings of the IEEE Congress
on Evolutionary Computation, 69–73.
37. Clerc, M. & Kennedy, J. (2002). The particle swarm–
explosion, stability, and convergence in a multidimensional
complex space, IEEE Transactions on
Evolutionary Computation, 6 (1), 58–73.
38. Naderi, B., Ghomi S.M.T.F. & Zandieh, M. (2011).
Scheduling open shops with parallel machines to
minimize total completion time. Journal Of Computational
and Applied Mathematics, 235, 1275–1287.
39. Phadke, M.S. (1995). Quality engineering using robust
design, Prentice Hall PTR.
40. Naderi, B., Zandieh, M., Balagh, A.K.G. & Roshanaei, V. (2009). An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness, Expert Systems with Applications, 36, 9625–9633.