考虑道路通行能力差异的多应急避难点选址模型及算法

Models and algorithms for emergency shelter location with different edge capacities and traffic speeds

合理的应急避难点选址可以有效提高疏散效率,而道路通行能力的差异性特征是影响避难点选址决策的重要因素。本文在道路通行容量和通行速度不同的情形下,以最大完成时间和总完成时间的组合函数最小化为目标,研究路图上有堵塞时间成本的k个避难点选址问题。首先,本文重点分析不同的道路通行容量和通行速度对疏散过程的影响,对疏散过程中的堵塞变化进行梳理,对路图进行等价转换。其次,本文基于等价路图把组合目标下的多避难点选址问题转化为有限个有最大完成时间限制的、以总完成时间最小化为目标的k避难点选址问题,之后基于动态规划设计多项式时间的求解算法。最后,本文给出相应的数值算例,并对组合目标函数中的权重系数进行敏感性分析。

In recent years,various natural disasters,accidents,and events that endanger public health or security have been occurring throughout the world.To reduce the amount of casualties as much as possible,people need to be evacuated to emergency shelters as soon as possible when a disaster takes place.Since the locations of emergency shelters directly affect the evacuation time,an appropriate location of an emergency shelter is especially important.A good emergency shelter location should not only take edge capacities and traffic speed into consideration,but also balance the maximum completion time and the average completion time.In the meantime,people may have to spend some amount of time in waiting at some vertex due to the edge capacity during the evacuation.More specifically,when too many people need to enter into an edge,it is likely that a proportion of them need to wait at the entry vertex of the edge,i.e.,a congested entry.Taking the combinational function of the maximum completion time and the total completion time as the objective function,this paper considers different edge capacities and traffic speeds at the same time,and studies the k-emergency shelter location problem in a dynamic path network with congestion.The first part of the paper provides some definitions and important properties.Just as in previous studies,the capacity of each shelter is assumed to be infinite in this paper also,and the weight of a vertex can complete the evacuation with no time if a sink is located exactly on this vertex.Firstly,the dynamic congestion during the evacuation process is analyzed.For each vertex,the following three questions should be answered:whether a weight of the vertex will be merged with other weights or not;where the merging will occur and how many weights will be involved;and after the merging,what will happen before the weight arrive the emergency shelter.Then,with a detail analysis and a weight update process,the original dynamic path network is transformed into a path network with no weight merging equivalently.Finally,formulas for calculating the maximum completion time and the total completion time are given.The second part of the paper designs algorithms for the k-emergency shelter location problem in a dynamic path network with different edge capacities and traffic speeds.Firstly,based on the analysis about the optimal location,the objective function is described as a separate representation.Secondly,all the possible maximum completion times are observed according to the location of the key point.Then,the original location question of this paper,i.e.,to minimize the combinational function of the maximum completion time and the total completion time,becomes equivalent to solving multiple mini-sum location problems with known maximum completion time.At last,for solving the equivalence problem,an algorithm based on dynamic program is developed.The third part of the paper gives numerical examples.Firstly,the algorithm is illustrated with the help of a dynamic path network graph of 20 vertices.Then,numerical examples are given to investigate the effect of parameterλ1 on the location decision.The values of different objective functions are compared for differentλ1.In general,attention is paid to the optimization of only one objective of the maximum completion time and the total completion time,the other objective will become worse.If the weight of the total completion time is less,i.e.,the weight of the maximum completion time is larger,optimization of a single objective will not affect the other objective.At this situation,the single objective can be a better substitution of the weighted combinational objective.In summary,in consideration of the variability of an evacuation road,this paper studies the k-emergency shelter location problem on a dynamic path network with different edge capacities and traffic speeds.To calculate the maximum completion time and the total completion time,a detail analysis of the evacuation process is required.All the questions about the congestion process of a unit weight,including whether this weight will be merged with any other weight or not,if yes,then when,where and how,should be answered.Based on the analysis,the original dynamic path network is transformed into a new equivalent path network with new vertex weight on which all the weights can be evacuated to the emergency shelters without any merging.According to the fact that the combinational objective function is a convex function or a monotonic function when the location moves on an edge,the problem under combinational objective function is equivalent to several limited mini-sum location problems.An O(n6)-time algorithm based on dynamic program is proposed.This study extends the emergency location problem by relaxing the uniform edge capacity and traffic speed to a general case,and an effective algorithm is presented.