A Constraint Programming Approach for Non-Preemptive Evacuation Scheduling
Even, Caroline; Schutt, Andreas; Van Hentenryck, Pascal
2015-08-31
Conference Material
International Conference on Principles and Practice of Constraint Programming
Cork, Ireland
Large-scale controlled evacuations require emergency services to select evacuation routes, decide departure times, and mobilize resources to issue orders, all under strict time constraints. Existing algorithms almost always allow for preemptive evacuation schedules, which are less desirable in practice. This paper proposes, for the first time, a constraint-based scheduling model that optimizes the evacuation flow rate (number of vehicles sent at regular time intervals) and evacuation phasing of widely populated areas, while ensuring a nonpreemptive evacuation for each residential zone. Two optimization objectives are considered: (1) to maximize the number of evacuees reaching safety and (2) to minimize the overall duration of the evacuation. Preliminary results on a set of real-world instances show that the approach can produce, within a few seconds, a non-preemptive evacuation schedule which is either optimal or at most 6% away of the optimal preemptive solution.
constraint-based evacuation scheduling - non-preemptive scheduling - phased evacuation - simultaneous evacuation - actionable plan - real-world operational constraints - network flow problem
http://booleconferences.ucc.ie/cp2015
nicta:8715
Even, Caroline; Schutt, Andreas; Van Hentenryck, Pascal. A Constraint Programming Approach for Non-Preemptive Evacuation Scheduling. In: International Conference on Principles and Practice of Constraint Programming; Cork, Ireland. 2015-08-31. nicta:8715. http://hdl.handle.net/102.100.100/92105?index=1
Loading citation data...
Citation counts
(Requires subscription to view)