Sink location problems on dynamic flow networks

Abstract

Effective evacuation planning is a vital precautionary step for minimizing loss of life during large-scale disasters such as earthquakes, tsunamis, wildfires, hurricanes and so on. The central challenge of evacuation planning is determining optimal locations for evacuation facilities (sinks) to ensure safe and rapid movement of evacuees. Formally, this problem is modelled as the sink location problem, which aims to minimize either the maximum evacuation time (minmax criterion) or the total evacuation time of all evacuees (minsum criterion). In this thesis, for different network structures, we present several algorithmic advancements in sink location problems under both minsum and minmax objectives. We propose an O(nlog2 n) algorithm for the minsum one-sink location problem on balanced binary tree networks with uniform edge capacities. This is the first sub-quadratic algorithm for tree networks, which we achieved by introducing the modified clusters and an efficient cost accounting mechanism that avoids complex data structures while capturing congestion effects dynamically. We also extend the classical k-sink location problem on dynamic path networks with sink capacity constraints, which is a more realistic model for evacuation and logistics applications. For the minmax capacitated sink problem, we design several algorithms based on sorted matrices and parametric search, achieve complexities of O(max{nlog3 n,k log5 n}) and O(nlogn+max{knlog3 n,k2 log5 n}) for arbitrary sink capacity model with general edge capacities. We also present more efficient algorithms for the version with uniform edge capacities, which run in O(max{nlogn, k log3 n}) and O(n+max{k2 log3,knlog2 n}) time, respectively. For the continuous model with uniform sink capacity, we also presented two algorithms which run in O(max{nlog3 n,k log4 n}) using a sorted matrices approach and O(nlogn+max{knlog3 n,k2 log4 n}) time using the parametric search approach for the path network with general edge capacities. We also present the algorithms for the version with uniform edge capacities, which run in O(max{nlogn, k log2 n}) using a sorted matrices approach and O(n+max{k log2 n,knlogn}) time using the parametric search approach. Moreover, we introduce the capacitated k-sink location problem under the minsum objective with arbitrary sink capacity, developing an O(nlogn) time algorithm for the one-sink location problem and a dynamic programming approach for multiple sinks with complexities O(kn2 log3 n) and O(kn2 log4 n) for uniform and general edge capacities, respectively. These results collectively enhance the field of evacuation planning and optimization problems by overcoming enduring complexity challenges and introducing capacity-aware models that more accurately represent real-world limitations. The techniques that were created, especially the use of modified clusters and efficient congestion handling, make it possible for sub-quadratic algorithms to work on more complicated network topologies like trees and general graphs.