A Constraint-Based Model for Fast Post-Disaster Emergency Vehicle Routing
DOI:
https://doi.org/10.9781/ijimai.2013.248Keywords:
DSS, Disaster Recovery, ProgrammingAbstract
Disasters like terrorist attacks, earthquakes, hurricanes, and volcano eruptions are usually unpredictable events that affect a high number of people. We propose an approach that could be used as a decision support tool for a post-disaster response that allows the assignment of victims to hospitals and organizes their transportation via emergency vehicles. By exploiting the synergy between Mixed Integer Programming and Constraint Programming techniques, we are able to compute the routing of the vehicles so as to rescue much more victims than both heuristic based and complete approaches in a very reasonable time.Downloads
References
[1] N. Altay and W. G. Green, “OR/MS research in disaster operations management,” European Journal of Operational Research, vol. 175, no. 1, pp. 475–493, 2006.
[2] S. Tufekci and W. Wallace, “The Emerging Area Of Emergency Management And Engineering,” Engineering Management, IEEE Transactions on, vol. 45, no. 2, pp. 103–105, 1998.
[3] G. Erdogan, E. Erkut, A. Ingolfsson, and G. Laporte, “Scheduling ambulance crews for maximum coverage,” JORS, vol. 61, no. 4, pp. 543–550, 2010.
[4] I. Nouaouri, N. Jean-Christophe, and J. Daniel, “Reactive Operating Schedule in Case of a Disaster: Arrival of Unexpected Victims,” in WCE, ser. Lecture Notes in Engineering and Computer Science. International Association of Engineers, 2010, pp. 2123–2128.
[5] T.-Q. Chu, A. Drogoul, A. Boucher, and J.-D. Zucker, “Interactive Learning of Independent Experts' Criteria for Rescue Simulations,” J. UCS, vol. 15, no. 13, pp. 2701–2725, 2006.
[6] N.A.M. Nordin, N. Kadir, Z.A. Zaharudin, and N.A. Nordin, “An application of the A* algorithm on the ambulance routing,” IEEE Colloquium on Humanities, Science and Engineering (CHUSER), 2011, pp. 855–859.
[7] S. A. Suarez and C. G. Quintero, and J. L. de la Rosa, “A Real Time Approach for Task Allocation in a Disaster Scenario,” PAAMS, 2010, pp. 157–162.
[8] M. Lombardi, and M. Milano, “Optimal methods for resource allocation and scheduling: a cross-disciplinary survey,” Constraints, vol. 17, no. 1, pp. 51–85, 2012.
[9] R. Amadini
[10] , I. Sefrioui, J. Mauro, and M. Gabbrielli, “Fast Post-Disaster Emergency Vehicle Scheduling,” Distributed Computing and Artificial Intelligence, ser. Advances in Intelligent Systems and Computing, Springer International Publishing, 2013, vol. 217, pp. 219–226.
[11] N. Beldiceanu, M. Carlsson, S. Demassey, and T. Petit, “Global Constraint Catalogue: Past, Present and Future,” Constraints, vol. 12, no. 1, pp. 21–62, 2007.
[12] “Gurobi - The overall fastest and best supported solver available,” http://www.gurobi.com
[13] “GECODE - An open, free, efficient constraint solving toolkit,” http://www.gecode.org
[14] J. McCaffrey, “Improved Combinations with the BigInteger Data Type,” http://visualstudiomagazine.com/Articles/2012/08/01/BigInteger-Data-Type.aspx?Page=3 2013.
[15] N. Nethercote, P. J. Stuckey, R. Becket, S. Brand, G. J. Duck, and G. Tack, “MiniZinc: Towards a Standard CP Modelling Language,” in CP, 2007.
[16] T. Andersson, S. Petersson, and P. Värbrand, “Decision Support for Efficient Ambulance Logistics,” ser. ITN research report. Department of Science and Technology (ITN), Linköping University, 2005.
[17] K. Ufuk, T. Ozden, and T. Saniye, “Emergency Vehicle Routing in Disaster Response Operations,” in Proceedings of the 23rd Annual Conference on Production and Operation Management Society, 2012.
[18] S. Paquet, N. Bernier, and B. Chaib-draa, “Multiagent Systems Viewed as Distributed Scheduling Systems: Methodology and Experiments,” in Advances in Artificial Intelligence, ser. Lecture Notes in Computer Science, Springer Berlin Heidelberg, 2005, vol. 3501, pp. 43–47.
[19] S. Suarez and B. Lopez, “Reverse Combinatorial Auctions for Resource Allocation in the Rescue Scenario,” in ICAPS Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problems, 2006.
[20] B. Lopez, S. Suarez, and J. D. L. Rosa, “Task allocation in rescue operations using combinatorial auctions,” in Proceedings of the sixth Catalan Congress on Artificial Intelligence. IOS Press, 2003.
[21] M. Sedaghat, L. Nejad, S. Iravanian, and E. Rafiee, “Task Allocation for the Police Force Agents in RoboCupRescue Simulation,” in RoboCup 2005, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2006, vol. 4020, pp. 656–664.
[22] Nair, Ranjit and Ito, Takayuki and Tambe, Milind and Marsella, Stacy, “Task Allocation in the RoboCup Rescue Simulation Domain: A Short Note,” in RoboCup 2001, Springer-Verlag, 2002, pp. 751–754.
[23] N. Giuseppe, M. Venkatesh, N. Lewis, R. Dianne, T. Marc, H. Liza, P. Ian, and M. Bud, “Complexities, Catastrophes and Cities: Unraveling Emergency Dynamics,” in InterJournal of Complex Systems, vol. 4068, no. 1745, 2006.
[24] G. Narzisi, V. Mysore, and B. Mishra, “Multi-objective evolutionary optimization of agent-based models: An application to emergency response planning,” in Computational Intelligence, 2006, pp. 228–232.
[25] M. Nanjanath, A. J. Erlandson, S. Andrist, A. Ragipindi, A.A. Mohammed, A. S. Sharma, and M. Gini, “Decision and coordination strategies for robocup rescue agents,” in SIMPAR, Springer-Verlag, 2010, pp. 473–484.
[26] S. Paquet, N. Bernier, and B. Chaib-draa, “Comparison of Different Coordination Strategies for the RoboCupRescue Simulation,” in Innovations in Applied Artificial Intelligence, ser. Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2004, vol. 3029, pp. 987–996.
[27] J. Habibi, S. H. Yeganeh, M. Habibi, A. Malekzadeh, A. Malekzadeh, S. H. Mortazavi, H. Nikaein, M. Salehe, M. Vafadoost,
and N. Zolghadr, “Impossibles08 Team Description RoboCup Rescue Agent Simulation,” July 2008.
[28] O. A. Ghiasvand, and M. A. Sharbafi, “Using earliest deadline first algorithms for coalition formation in dynamic time-critical environment,” Education and Information Tech, vol. 1, no. 2, pp. 120–125, 2011.
[29] “Odyssey website,” http://www.plain.co.uk/index.php?option=com_content&task=view&id=67&Itemid=98
[30] “GeoFES,website,” http://www.dhigroup.com/MIKECUSTOMISEDbyDHI/GeoFES.aspx
Downloads
Published
-
Abstract33
-
PDF18
Submit Article
Information
