TY - GEN
T1 - A constraint programming approach for non-preemptive evacuation scheduling
AU - Even, Caroline
AU - Schutt, Andreas
AU - Van Hentenryck, Pascal
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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 non-preemptive 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.
AB - 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 non-preemptive 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.
KW - Actionable plan
KW - Constraint-based evacuation scheduling
KW - Network flow problem
KW - Non-preemptive scheduling
KW - Phased evacuation
KW - Real-world operational constraints
KW - Simultaneous evacuation
UR - http://www.scopus.com/inward/record.url?scp=84944590108&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-23219-5_40
DO - 10.1007/978-3-319-23219-5_40
M3 - Conference contribution
SN - 9783319232188
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 574
EP - 591
BT - Principles and Practice of Constraint Programming - 21st International Conference, CP 2015, Proceedings
A2 - Pesant, Gilles
PB - Springer Verlag
T2 - 21st International Conference on the Principles and Practice of Constraint Programming, CP 2015
Y2 - 31 August 2015 through 4 September 2015
ER -