A Constraint Programming Approach for Non-Preemptive Evacuation Scheduling

Select |




Print


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.http://hdl.handle.net/102.100.100/92105?index=1



Loading citation data...

Citation counts
(Requires subscription to view)