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

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

Abstract

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

CLC Number:

O224

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.

Figures/Tables 10

最优避难点选址	最优划分点及划分点上权重划分情况	单侧避难时间	总避难时间
$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

最优避难点选址	最优划分点及划分点上权重划分情况	单侧避难时间	总避难时间
$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

References 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]	XU Yin-feng, ZHI Rong-teng, ZHENG Fei-feng, LIU Ming. Online Strategy and Competitive Analysis of Production Order Scheduling Problem with Rental Cost of Shared Machines [J]. Chinese Journal of Management Science, 2023, 31(4): 142-150.
[2]	LI Fei-fei, XU Zhe. Distributed Multi-project Stochastic Scheduling with Two-stage Coordination Mechanism of Resources Allocation [J]. Chinese Journal of Management Science, 2022, 30(12): 38-51.
[3]	ZHANG Xue-wei, WANG Xi-jie. Study on the Matching of Best Division's Relatedness under Internal Capital Market Inter-temporal Allocation——An Interpretation of the Internal Logic of the Merger and Acquisition Integration of Diversified Enterprises [J]. Chinese Journal of Management Science, 2021, 29(9): 25-35.
[4]	FEI Wei-yin, ZHANG Fan-hong, YANG Xiao-guang. The Impact of Inflation on Executive's Equity Incentive and Work Effort [J]. Chinese Journal of Management Science, 2020, 28(11): 1-11.
[5]	FENG Ling, LEI Li-mei. Research on the Pricing of Treasury Bond Futures Based on Lattice Field Theory and Dynamic Programming [J]. Chinese Journal of Management Science, 2019, 27(9): 36-46.
[6]	ZHAO Rong, LIU Ke-yan, REN Pei-yu. 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.
[7]	HE Xiao-bo, WANG Dong-mei, ZENG Shi-hong. Valuation for Forestry Investment Projects with Carbon Sequestration Benefits——Based on Real Option Pricing Theory [J]. Chinese Journal of Management Science, 2017, 25(3): 39-48.
[8]	ZHANG Peng, ZHANG Wei-Guo, ZHANG Yi-fei. Multi-period Mean-semivariance Portfolio Selection with Minimum Transaction Lots Constraints [J]. Chinese Journal of Management Science, 2016, 24(7): 11-17.
[9]	ZHANG Peng, ZHANG Wei-Guo, ZHANG Yi-fei. Multi-period Mean-semivariance Portfolio Selection with Minimum Transaction Lots Constraints [J]. Chinese Journal of Management Science, 2016, 24(7): 11-17.
[10]	CHANG Hao. Investment and Consumption Model with the Zero-Coupon Bond under the Ho-Lee Interest Rate Model [J]. Chinese Journal of Management Science, 2014, 22(10): 29-37.
[11]	LI Yan-ni, RAN Mao-sheng. The Study of Commercial Bank Liquidity Risk Management Method and Improvement——Application of Dynamic Programs with Simple Recourse Under Fuzzy Qualitative Constraints [J]. Chinese Journal of Management Science, 2011, 19(3): 19-25.
[12]	WU Gang, WEI Yi-Ming. The Optimal Strategies of China’s Strategic Petroleum Reserves in Emergency [J]. Chinese Journal of Management Science, 2011, 19(2): 140-146.
[13]	LI Jian-bin, YANG Rui-na. Optimal Strategies of Procurement Risk Management with Correlated Demand and Spot Price [J]. Chinese Journal of Management Science, 2011, 19(1): 12-20.
[14]	WANG Xiao-jing, LIU Zhi-xue, ZHENG Chang-zheng. An Inventory Rationing Policy in the Newsboy Problem with Multiple Customer classes [J]. Chinese Journal of Management Science, 2010, 18(4): 65-72.
[15]	CHI Guo-tai, YU Fang-ping, WANG Yu-gang. Research on Multi-period Futures Dynamic Hedging Model [J]. Chinese Journal of Management Science, 2010, 18(3): 17-24.

Minsum k-sink Location Problem on Dynamic Path Networks with Non-confluent Flow Constraint

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 23

Related Articles 15

Metrics

Comments

Recommended 0