分流模式下k-避难点选址策略研究

doi:10.16381/j.cnki.issn1003-207x.2021.2181

摘要/Abstract

摘要：

避难点选址是否合理直接影响灾害发生时避难疏散效率。本文在道路通行能力不同的动态路图中，以总避难时间最小化为目标，研究允许分流疏散的 $k$ -避难点选址问题。首先，根据任意相邻避难点间划分点的唯一性，找出最优划分点及其对应的权重划分。其次，考虑道路通行能力约束，分析人流汇合和堵塞的动态变化过程，将原路图转化为无汇合状态的等价路图。接着，基于动态规划方法，设计了时间复杂度为 $O k n 3$ 的求解算法。最后，通过算例分析可知，相比合流模式，分流模式的整体优化效果会随着避难点数量的增加而更加显著。

关键词: 避难点选址, 分流模式, 总避难时间, 动态规划

Abstract:

Over the past few decades， public healthy and security have been threatened by various natural disasters， accidents， and events occurred throughout the world. The losses the disasters bring can be decreased with appropriate emergency shelter locations. In this paper， the $k$ -sink location problem in dynamic path networks under the non-confluent flow constraint is considered， with the goal of minimizing the total completion time. A dynamic path network is consisted of an undirected path with positive edge lengths， general edge capacity， and positive vertex supplies. For each edge， a general traffic speed is given to indicate the time that a unit weight need to travel a unit distance on this edge. The weight on the same vertex can be evacuated to different shelters during the evacuation， i.e.， the non-confluent flow constraint.Firstly， according to the uniqueness of the divider between any two adjacent sinks， the optimal dividers and the corresponding weight division are determined. Secondly， the congestion situation during the evacuation is detailed analyzed， and based on that， the original dynamic path network is transformed to a new path network with new vertex weight. And no congestion occurs during the evacuation on the new dynamic path network. Thirdly， an $O k n 3$ -time algorithm is proposed based on dynamic programming.Numerical experiments and a practical example are both presented in this paper. The practical example is based on a road in Chang’an district， Xi’an. Numerical results show that as the number of sinks increases， the non-confluent flow model is more effective. According to the results of the practical example， the feasibility and effectiveness of the proposed algorithm are verified. To improve the efficiency of evacuation， non-confluent evacuation model will be a general trend. The models and algorithms constructed in this paper can provide theoretical support for future research and practical application.

Key words: sink location problem, non-confluent flow, total completion time, dynamic programming

中图分类号:

O224

李红梅,张湘玥,罗太波,徐寅峰. 分流模式下 $k$ -避难点选址策略研究[J]. 中国管理科学, 2024, 32(2): 108-118.

Hongmei Li,Xiangyue Zhang,Taibo Luo,Yinfeng Xu. Minsum k-sink Location Problem on Dynamic Path Networks with Non-confluent Flow Constraint[J]. Chinese Journal of Management Science, 2024, 32(2): 108-118.

图/表 10

图1

图2

图3

图4

表1

k=5时最优方案"

最优避难点选址	最优划分点及划分点上权重划分情况	单侧避难时间	总避难时间
$x 1 = v 2$	—	12938	17488
$x 1 = v 2$	$v d 2,5 = v 3 ?$ (131,49)	4550	17488
$x 2 = v 5$	$v d 2,5 = v 3 ?$ (131,49)	10616	21857
$x 2 = v 5$	$v d 5,8 = v 6 ?$ (212,48)	11241	21857
$x 3 = v 8$	$v d 5,8 = v 6 ?$ (212,48)	4266	4266
$x 3 = v 8$	$v d 8,10 = v 9$ (0,120)	0	4266
$x 4 = v 10$	$v d 8,10 = v 9$ (0,120)	2856	9091
$x 4 = v 10$	$v d 10,15 = v 12$ (62,58)	6235	9091
$x 5 = v 15$	$v d 10,15 = v 12$ (62,58)	12779	28985
$x 5 = v 15$	—	16207	28985

表1

图5

图6

图7

图8

表2

本文选址方案"

最优避难点选址	最优划分点及划分点上权重划分情况	单侧避难时间	总避难时间
$x 1 = v 4$	—	348402.09	621729.22
$x 1 = v 4$	$v d 4,9 = v 7 ?$ (1544,2966)	273327.13	621729.22
$x 2 = v 9$	$v d 4,9 = v 7 ?$ (1544,2966)	152419.41	152419.41
$x 2 = v 9$	$v d 9,11 = v 10 ?$ (0,5170)	0	152419.41
$x 3 = v 11$	$v d 9,11 = v 10 ?$ (0,5170)	94632.06	329381.71
$x 3 = v 11$	$v d 11,15 = v 13$ (2491,699)	234749.65	329381.71
$x 4 = v 15$	$v d 11,15 = v 13$ (2491,699)	196533.70	423826.10
$x 4 = v 15$	—	227292.40	423826.10

表2

参考文献 23

1	Toregas C， Swain R， ReVelle C， et al. The location of emergency service facilities［J］. Operations Research， 1971， 19（6）： 1363-1373.
2	Farahani R， Asgari N， Heidari N. Covering problems in facility location： a review［J］. Computers and Industrial Engineering， 2012， 62（1）： 368-407.
3	Tansel B C， Francis R L， Lowe T J. Location on networks： a survey. Part I： the p -center and p -median problems［J］. Management Science，1983，29（4）： 482-497.
4	Minieka E. Short notes： the m -center problem［J］. SIAM Review， 1970， 12（1）： 138-139.
5	Goldman A J. Minimax location of a facility in a network［J］. Transportation Science， 1972， 6（4）： 407-418.
6	Berman O， Simchi-Levi D. Conditional location problems on networks［J］. Transportation Science， 1990， 24（1）： 77-78.
7	Teitz M B， Bart P. Heuristic methods for estimating the generalized vertex median of a weighted graph［J］. Operations Research， 1968， 16（5）： 955-961.
8	Alp O， Erkut E， Drezner Z. An efficient genetic algorithm for the p -median problem［J］. Annals of Operations Research， 2003， 122（1）： 21-42.
9	Mamada S， Makino K， Fujishige S. Optimal sink location problem for dynamic flows in a tree network［J］. IEICE Transactions on Fundamentals of Electronics， Communications and Computer Sciences， 2002， 85（5）： 1020-1025.
10	Mamada S， Uno T， Makino K， et al. An O n l o g 2 n algorithm for a sink location problem in dynamic tree networks［J］. Discrete Applied Mathematics， 2006， 154（16）： 2387-2401.
11	Chen D， Golin M. Minmax centered k-partitioning of trees and applications to sink evacuation with dynamic confluent flows［J］. Algorithmica， 2023， 85（7）： 1948-2000.
12	Xu Y F， Li H M. Minimax regret 1-sink location problem in dynamic cycle networks［J］. Information Processing Letters， 2015， 115（2）： 163-169.
13	Benkoczi R， Bhattacharya B， Custic A， et al. Facility location problems in cycle networks［C］ //Proceedings of the 21st Japan Conference on Discrete and Computational Geometry， Graphs， and Games， Tokyo， Japan， October 8-11， Springer， 2017： 139-140.
14	Belmonte R， Higashikawa Y， Katoh N， et al. Polynomial-time approximability of the k -sink location problem［EB/OL］. （2015-03-10）［2021-09-15］. arXiv：.
15	Higashikawa Y， Golin M J， Katoh N. Multiple sink location problems in dynamic path networks［J］. Theoretical Computer Science， 2015， 607： 2-15.
16	Benkoczi R， Bhattacharya B， Higashikawa Y， et al. Minsum k -sink problem on dynamic flow path networks［C］//Proceedings of the 29th International Workshop on Combinatorial Algorithms， Singapore， Singapore， July 16-19， Springer， 2018： 78-89.
17	Bhattacharya B， Golin M J， Higashikawa Y， et al. Improved algorithms for computing k -sink on dynamic path networks［EB/OL］.（2016-09-06）［2021-09-15］. arXiv：.
18	倪冠群，徐寅峰，徐玖平. 考虑道路通行能力的应急避难点选址模型及算法［J］.中国管理科学， 2015， 23（1）： 82-88.
	Ni G Q， Xu Y F， Xu J P. The location models and algorithms for emergency shelter with traffic capacity constraint［J］. Chinese Journal of Management Science， 2015， 23（1）： 82-88.
19	Arumugam G P， Augustine J， Golin M J， et al. Optimal evacuation flows on dynamic paths with general edge capacities［EB/OL］.（2016-06-23）［2021-09-15］. arXiv：.
20	赵容，刘克艳，任佩瑜. 路段通行能力不同的避难点选址模型及算法［J］.中国管理科学， 2017，25（9）： 133-140.
	Zhao R， Liu K Y， Ren P Y. Min-max multiple sink location problem in dynamic path networks with different traffic capacity constraint［J］.Chinese Journal of Management Science， 2017， 25（9）： 133-140.
21	Benkoczi R， Bhattacharya B， Higashikawa Y， et al. Minsum k -sink problem on path networks［J］. Theoretical Computer Science， 2020， 806： 388-401.
22	Higashikawa Y， Katoh N， Teruyama J， et al. Almost linear time algorithms for minsum k -sink problems on dynamic flow path networks［J］. Theoretical Computer Science， 2021， 873： 87-113.
23	Higashikawa Y， Augustine J， Cheng S W， et al. Minimax regret 1-sink location problem in dynamic path networks［J］. Theoretical Computer Science， 2015， 588： 24-36.

[1]	刘昕睿, 雒兴刚, 姬朋立, 张忠良. 基于实时信息的游客行程动态规划研究[J]. 中国管理科学, 2023, 31(3): 124-132.
[2]	李飞飞, 徐哲. 基于两阶段资源分配协调机制的分布式多项目随机调度[J]. 中国管理科学, 2022, 30(12): 38-51.
[3]	张学伟, 王玺杰. 内部资本市场跨期配置下最优分部相关性匹配研究——对多元化企业并购整合内在逻辑的诠释[J]. 中国管理科学, 2021, 29(9): 25-35.
[4]	费为银, 张繁红, 杨晓光. 通胀对高管的股权激励和工作努力策略的影响[J]. 中国管理科学, 2020, 28(11): 1-11.
[5]	冯玲, 雷丽梅. 基于晶格场理论和动态规划的国债期货定价研究[J]. 中国管理科学, 2019, 27(9): 36-46.
[6]	赵容, 刘克艳, 任佩瑜. 路段通行能力不同的避难点选址模型及算法[J]. 中国管理科学, 2017, 25(9): 133-140.
[7]	贺晓波, 王冬梅, 曾诗鸿. 附碳汇收益的林业投资项目价值评估——基于实物期权定价理论[J]. 中国管理科学, 2017, 25(3): 39-48.
[8]	张鹏, 张卫国, 张逸菲. 具有最小交易量限制的多阶段均值-半方差投资组合优化[J]. 中国管理科学, 2016, 24(7): 11-17.
[9]	张鹏, 张卫国, 张逸菲. 具有最小交易量限制的多阶段均值-半方差投资组合优化[J]. 中国管理科学, 2016, 24(7): 11-17.
[10]	常浩. Ho-Lee利率模型下带有零息票债券的投资-消费模型[J]. 中国管理科学, 2014, 22(10): 29-37.
[11]	李研妮, 冉茂盛. 商业银行流动性风险管理方法的改进研究——基于模糊定性约束下的动态规划补偿模型应用[J]. 中国管理科学, 2011, 19(3): 19-25.
[12]	吴刚, 魏一鸣. 突发事件情景下的中国战略石油储备应对策略研究[J]. 中国管理科学, 2011, 19(2): 140-146.
[13]	李建斌, 杨瑞娜. 现货价格和需求关联时期权组合合约模式下采购风险管理策略[J]. 中国管理科学, 2011, 19(1): 12-20.
[14]	汪小京, 刘志学, 郑长征. 多类顾客环境下报童模型中库存分配策略研究[J]. 中国管理科学, 2010, 18(4): 65-72.
[15]	张明玺, 李昆鹏. 混合离散差分进化算法在单机批处理调度中的应用[J]. 中国管理科学, 2010, 18(4): 114-123.