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

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

作　　者：罗太波 邓洁 李红梅 LUO Taibo;DENG Jie;LI Hongmei(School of Economics and Management,Xidian University,Xi′an 710126,China;School of Economics and Management,Northwest University,Xi′an 710127,China)

机构地区：[1]西安电子科技大学经济与管理学院,陕西西安710126 [2]西北大学经济管理学院,陕西西安710127

出　　处：《管理工程学报》2024年第5期153-163,共11页Journal of Industrial Engineering and Engineering Management

基　　金：教育部人文社科项目(18YJC630114);国家自然科学基金项目(72101196);陕西省自然科学基金项目(2022JM-425)。

摘　　要：合理的应急避难点选址可以有效提高疏散效率,而道路通行能力的差异性特征是影响避难点选址决策的重要因素。本文在道路通行容量和通行速度不同的情形下,以最大完成时间和总完成时间的组合函数最小化为目标,研究路图上有堵塞时间成本的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 equiva

关 键 词：避难点选址 路图 通行容量 通行速度 组合目标 

分 类 号：O224[理学—运筹学与控制论] C934[理学—数学] TP399[经济管理—管理学]