关键词: 避难点选址, 分流模式, 环形路, 应急疏散

Abstract: All kinds of natural disasters and emergency events have taken place in the whole world frequently in the past decades, which makes the research and development of emergency management system urgent. As an important part of emergency management, efficient emergency shelter locations can protect people’s lives and property from disasters. To improve evacuation efficiency, evacuees from the same evacuation point may not evacuate to the same emergency shelter location. This paper considers the k-sink location problem in a dynamic cycle network under the non-confluent flow constraint, with the goal of minimizing the maximum completion time.The non-confluent flow constraint and the confluent flow constraint refer to the condition on which evacuees from the same evacuation point can evacuate to different emergency shelter locations and only to the same emergency shelter location, respectively.
In the first part of this paper, problem formulations and related properties are provided. The fact that any two evacuation paths never cross each other in the optimal evacuation planning is shown. A continuous part of the cycle network C is referred to as a sub-cycle in this paper. Thus, our problem requires k sink points and k division points which means dividing the original cycle network into k sub-cycles. A division point means the weight on this vertex may be evacuated to different sink points. The corresponding weight division should always be given precisely with a division point. The second part of this paper focuses on the optimal evacuation planning between all two adjacent sinks. Firstly, the uniqueness of the evacuation planning between any two adjacent sinks is proved. In other words, with two given adjacent sink points, the division point and the corresponding weight division is unique. Then, by finding the optimal division point with the confluent flow constraint, the optimal division point and the corresponding optimal weight division are then derived with the non-confluent flow constraint. Thus, the optimal evacuation planning between any two adjacent sinks can be found in O(n) time. It is noteworthy that the weight of division point should always evacuate to the same sink point with the confluent flow constraint. The third part of this paper gives the algorithm to solve the-sink location problem with non-confluent flow constraint. Firstly, the optimal division scenarios and the corresponding optimal maximum completion times are obtained for all possible sub-cycles. Secondly, based on the structural characteristics of the optimal solution, the k-sink location problem in the dynamic cycle network is converted to multiple k-sink location problems in the dynamic path network. Then, an O(kn³)-time algorithm based on dynamic programming is designed.
A numerical experiment is presented in the last part of this paper. Firstly, to solve the 5-sink location problem in a dynamic cycle network with 18 vertices, the algorithm is shown step by step. Then the maximum completion time with confluent and non-confluent flow constraint are compared. The results show that the non-confluent flow constraint can decrease the maximum completion time efficiency. The improvement of evacuation efficiency depends on the number of evacuation points and sink points.
In summary, allowing evacuees at the same evacuation point to evacuate to different sink point via different path, this paper studies the problem of locating k-sink points on a dynamic cycle network. To solve this problem, original cycle network is equated to a limited number of paths based on any two adjacent sink points, and then a division point and the corresponding weight division should be determined. It is assumed that sink point should be located on vertex only, such that the number of sub-cycles is limited. An O(kn³)-time algorithm is proposed based on dynamic programming. Since the weight on the same vertex can be evacuated to different sink points, the evacuation with non-confluent flow constraint is more efficient compared with evacuation with confluent flow constraint. The models and algorithms constructed in this paper can provide theoretical support for practical application. The robust optimization model with uncertain weights will be considered in future studies.

Key words: sink location; non-confluent flow; cycle network; emergency evacuation