Computational Methods and Algorithms for Real-Time Routing of Emergency Response in Unreliable Settings
Tuesday, September 15, 2020 (Central Time) — 2:45PM - 3:30PM
Abstract Prompt and efficient intervention is vital in reducing casualty figures during sudden epidemic outbreaks, natural disasters or terrorism attacks. This can only be achieved if there is a fit-for-purpose emergency response plan in place, incorporating geographical, time and vehicular capacity constraints, with considerations of rapidly changing road network and infrastructure. Existing research works in this area focus on routing and combinatorial optimization for known capacity and demand. Vehicle scheduling problem has also been studied as a separate problem. However, this research aims to develop a combined comprehensive algorithm and computational methods to optimize emergency response activities, through route construction, real-time route improvement, and adding a distinct but similar procedure: vehicle scheduling problem for fleet of different capacities. Three renowned algorithms, one from each of the subject areas, will be analyzed and their best features, in terms of time and space performance evaluations, adopted to form part of the new algorithm. This will be done using available benchmark instances (such as Solomon’s instances) and real-life data from two West African Countries. A novel and improved algorithm, incorporating these procedures will be developed. Our algorithm involves three stages: Selection of depot and clustering; route construction; and real-time route improvement. In the initial phase, locations to be visited are strategically clustered near a depot. The second phase iteratively constructs routes through all locations clustered in a depot, subject to time, population in need and vehicle capacity constraints. Pruning is heuristically implemented, to ensure compliance with all constraints, until a feasible set of solution is obtained. The third phase accepts real-time changes, dynamically re-constructs and improve routing. Our algorithm will be piloted in a most-at-risk region. Keywords: Vehicle Routing Problem. Public Health Emergencies. Algorithms. Artificial Intelligence.