NONLINEAR MIXED INTEGER PROGRAMMING MODELS AND ALGORITHMS FOR FAIR AND EFFICIENT LARGE SCALE EVACUATION PLANNING
Tarih:
Başlangıç Zamanı: Starting Time 05:00 pm ~ 06:00 pm
Konum: Senate Meeting Room
Abstract: Shelters are safe facilities that protect a population from possible damaging effects of
a disaster. Traffic management during an evacuation and the decision of where
to locate the shelters are of critical importance to the performance of an
evacuation plan. From the evacuation management authority's point of view, the
desirable goal is to minimize the total evacuation time by computing a system
optimum (SO). However, evacuees may not be willing to take long routes enforced
on them by a SO solution; but they may consent to taking routes with lengths
not longer than the shortest path to the nearest shelter site by more than a
tolerable factor. We develop a model that optimally locates shelters and
assigns evacuees to the nearest shelter sites by assigning them to shortest
paths, shortest and nearest with a given degree of tolerance, so that the total
evacuation time is minimized. As the travel time on a road segment is often
modeled as a nonlinear function of the flow on the segment, the resulting model
is a nonlinear mixed integer programming model. We develop a solution method
that can handle practical size problems using second order cone programming
techniques. Using our model, we investigate the trade-off between efficiency
and fairness.
Disasters are uncertain events. Related studies and real-life practices show that a significant uncertainty regarding the evacuation demand and the impact of the disaster on the infrastructure exists. The second model we propose is a scenario-based two-stage stochastic evacuation planning model that optimally locates shelter sites and that assigns evacuees to shelters and paths to minimize the expected total evacuation time, under uncertainty. The model considers the uncertainty in the evacuation demand and the disruption in the road network and shelter sites. We present a case study for an impending earthquake in Istanbul, Turkey. We compare the performance of the stochastic programming solutions to solutions based on single scenarios and mean values.
We also propose an exact algorithm based on Benders decomposition to solve the stochastic problem. To the best of our knowledge, ours is the first algorithm that uses duality results for second order cone programming in a Benders decomposition setting. We solve practical size problems with up to 1000 scenarios in moderate CPU times. We investigate methods such as employing a multi-cut strategy, deriving pareto-optimal cuts, using a reduced primal subproblem and preemptive priority multiobjective program to enhance the proposed algorithm. The dual subproblem contains a constraint for each path and hence its size gets large as the tolerance level increases. To deal with this issue, we propose a cutting plane framework to solve the dual subproblem. Computational results confirm the efficiency of our algorithm as it is considerably faster and can solve instances with larger number of scenarios compared to solving the extended formulation with an off-the-shelf solver. Further, employing a cutting plane framework enables us to solve instances with larger networks and higher tolerance levels.
This research is supported by TUBITAK, The Scientific and Technological Research Council of Turkey with project number 213M434.
Bio: Vedat Bayram is a Postdoctoral Research Fellow at the University of Waterloo, Faculty of Engineering, Department of Management Sciences. Prior to his current position, he worked for many years as a Senior Operations Research Analysis Officer at the Project Management Division of Turkish General Staff Headquarters. He received his PhD. from Bilkent University, the Department of Industrial Engineering in 2015. His research interests include large scale optimization, convex optimization and stochastic programming applications with an emphasis on disaster management, transportation and logistics, homeland security and defense planning and renewable energy systems. He has commanded and served in different units and divisions of Turkish Armed Forces as an Artillery Officer and Operations Research Analyst both in Turkey and abroad. He holds an M.S. degree in Operations Research from U.S. Naval Postgraduate School and a B.S. degree in Systems Engineering from Turkish Army Academy. He worked as a researcher in a TUBITAK funded research project titled “Nonlinear Mixed Integer Programming Models for Evacuation Planning”. He was also the former Turkish Armed Forces representative for Systems Analysis and Studies (SAS) Panel in NATO Science and Technology Organization through 2012-2016.