环形路上可分流的多避难点选址模型及算法

Model and Algorithm for Multiple Sink Location Problem in DynamicCycle Networks with Non-confluent Flow Constraint

合理规划应急避难点选址能够有效提高避难效率。考虑疏散过程中人群可分流,以最大疏散完成时间最小为目标,研究环形路上k-避难点选址问题。首先,根据最优疏散方案中人流必不交叉的性质,证明了相邻避难点间权重分流的唯一性,进一步找出所有可能的最优划分情景。其次,基于最优解的结构特征,将环形路上的多避难点选址问题等价为有限个路径上的选址问题。接着,采用动态规划方法设计了时间复杂度为O(kn^(3))的求解算法。最后给出数值算例,对比了分流模式与合流模式下的疏散效率,结果表明适当的人群分流可以有效提高疏散效率。

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^(3))-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 3)-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.