Evacuation planning for homeland defense

LEAD PRESENTER: Prof. Shashi Shekhar

Computer Science Department, University of Minnesota

200 Union Street SE #4 192, Minneapolis, MN 55455

(612) 624-8307 :fax: (612) 625-0572 :email: shekhar@cs.umn.edu


Evacuation route-schedule planning identifies paths and schedules to move at-risk population out to safe areas in the event of terrorist attacks, catastrophes, or natural disasters. Its goal is to identify near-optimal evacuation routes and schedules to minimize evacuation time despite limited transportation network capacity and the possibly large at- risk population. Finding the optimal solution is computationally exorbitant due to the extremely large size of the transportation networks (million nodes and edges) and the limited capacities. We propose novel geo-spatial algorithms to determine competent evacuation plans. Evaluation of our methods for evacuation planning for a disaster at the Monticello nuclear power plant near Minneapolis/St. Paul Twin Cities metropolitan area shows that the new methods lowered evacuation time relative to existing plans by providing higher capacities near the destination and by choosing shorter routes.


US Army Research Laboratory is sponsoring the work via AHPCRC on use of high performance computing techniques to reduce computation time to produce evacuation plans quickly. Federal Highway Authority (federal agency) will sponsor follow-on work via CTS to determine contra-flow configurations of the transportation networks to increase outbound capacities and reduce total evacuation time. Collaborators include Mr. QingSong Lu, Mr. Sangho Kim, Prof. Eil Kwon (Minnesota State University), Ms. Sonia Pitt (Mn/DOT) and Mr. Mike Sobolesky (MnDOT).