Abstract: Various natural disasters, accidents, and events that endanger public health or security have occurred throughout the world over the past few decades. An appropriate emergency shelter location can decrease the losses the disasters bring. Due to the uniqueness of emergencies, uncertain information should be considered in location decision making. The uncertainty of vertex weight has been studied in many related researches. Taking the uncertainty of edge capacities into consideration, this paper studies the emergency shelter location problem in a dynamic path network. With a given dynamic path network, each vertex is assigned a positive weight which indicates that the number of people should be evacuated, and each edge has a positive length and an uncertain capacity. The edge capacity is the maximum number of people that can enter the edge per unit time. For each edge, although the capacity is not known exactly, the interval to which it belongs is given. A vertex probably gets congested if too many people try to get in the corresponding edge at the same time. The time spent due to congestion should be noted during the evacuation. The problem requires a location so that the maximum regret of the maximum completion time is minimized.
The first part of this paper gives basic definitions of the problem and some useful properties are also presented. The capacity of each shelter (sink) is assumed to be infinite. The evacuation is completed as soon as the weight reaches a shelter, so if a shelter is located exactly on a vertex, then all the weight of this vertex can complete evacuation with no time. Based on the uncertainty of edge capacity, congestion situation during the evacuation progress is analyzed in detail, and then critical edge capacity leading to changes in congestion situation is successively calculated, so we can get the maximum completion time. With a given scenario, that is to say, the capacity of each edge is given, the maximum completion time of the left or the right part from a sink point is proved to be unimodal with the sink location moving on a path network. Then the effect of critical edge capacity on the maximum completion time is analyzed.
In the second part of this paper, a polynomial algorithm to solve the sink location problem on a dynamic path network with uncertain edge capacities is proposed. First, based on the congestion changing during the evacuation, the marginal value of edge capacity that causes a change in the last congestion point is analyzed. The special structural characteristics of the maximum regret scenarios are analyzed to ascertain the worst case scenario for all possible maximum regret values. And the number of all possible worst case scenarios is restricted to polynomial. Then, all the locations located on vertices and edges are treated separately. To find the min-max regret sink location, linear programming model is applied in this part.An O(n³)-time algorithm is developed to solve the 1-sink location problem. Then the uncertainty of vertex weight is taken into consideration at the same time further, and an O(n⁵)-time algorithm is proposed.
A practical example is presented in the third part of this paper. The practical example is proposed based on Xianyang Lake Scenic Spot which is abstracted to a path network with 12 vertices. Compared with present emergency shelter location, the new location has a good performance when the worst case scenario happens. This result can provide a theory gist for emergency shelter location and network building.
In summary, this paper studies the min-max regret 1-sink location problem on a dynamic path network with interval edge capacity. To obtain the maximum completion time, the dynamic congestion progress of all the weight during the evacuation is analyzed in detail. It is proved that the maximum completion time is unimodal. Although the number of edge capacity scenarios is infinite in theory, this paper limits the possible worst case scenarios to polynomial, which is based on the special structural characteristics of the maximum regret scenarios. For each edge, the min-max regret sink point is obtained by applying linear programming model. Considering all the locations on vertices and edges separately, the algorithm proposed in this paper gets a time complexity of O(n³). An O(n⁵) time algorithm is also proposed to solve this problem when the vertex weight is also given as interval data. In our future research, the multiple sink location problem will be considered. In addition, this problem will be also studied with more general dynamic networks, such as trees and general connected networks.

Key words: sink location, uncertain edge capacities, min-max regret, algorithm design and analysis

摘要： 道路通行能力的不确定性是影响应急避难点选址决策的重要因素。本文在道路通行能力为区间值的动态路图中,以最小化所有避难者完成疏散时间的最大后悔值为目标,研究应急避难点的选址问题。首先,基于避难疏散过程中拥堵的动态变化特征,分析拥堵点转移所对应道路通行能力的临界值。其次,通过证明道路通行能力最坏情景的结构特征,将所有可能的最坏情景限制在多项式内。接着,采用点线分离的优化思想,设计了时间复杂度为O(n³)的求解算法。当顶点权重也同时为区间值时,给出了时间复杂度为O(n⁵)的求解算法。最后,给出相应的实际应用算例验证了选址策略的有效性。研究结果能为实际中的应急避难点选址问题提供相应的理论指导。

关键词: 避难点选址, 通行能力不确定, 最小最大后悔值, 算法设计与分析