From the viewpoint of disaster prevention from city planning and evacuation planning, it is important to establish effective evacuation planning systems against large scale disasters. Considering the different roads have different capacity, the k-sink location problem in dynamic network with different capacity is proposed.
In our model, each vertex supplies with a certain nonnegative value and each edge has a capacity representing the least upper bound for the units flowing into the edge per unit time. It is found that the time for a vertex weight ω to go through the edge e which have a capacity ce and a length le is leτ+ω/ce-ω/c, where τ is a constant representing the time required for traversing the unit distance of per unit weight and c is the flow of ω. Our goal is to find k sinks and k-1 divides which minimize the maximum time for all units flowing into the corresponding sink that the divides have provided. First, the 1-sink location problem is analyzed and it is found the monotonicity and unimodality of the evacuation completion time. Then based on some new properties, the linked list data structure is used to store the completion time and the minimum road capacity on their way to the sink of the maximum congestion points, which make the solution process easier. On this basis, an O(nlogn) time algorithm is developed to solve the 1-sink location problem. Finally, an O(knlogn) time recursive algorithm is developed to solve the k-sink location problem based on dynamic programming, where n is the number of vertices in the given network.
Since we are the first to analyze the sink location problem in dynamic network with different capacity, our research may be useful to the further research such as the sink location problem in dynamic tree network with different capacity and the sink location problem in dynamic network with interval weight and different capacity.
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
.
DOI: 10.16381/j.cnki.issn1003-207x.2017.09.015
[1] Toregas C, Swain R, Revelle C, et al. The location of emergency service facilities[J]. Operations Research, 1971, 19(6):1363-1373.
[2] Adel A A, A. White J A. Probabilistic formation of the emergency service location problem[J]. Journal of Operational Research Society, 1978, 29(12):1167-1179.
[3] Shier D, Dearing P. Optimal locations for a class of nonlinear single-facility location problems on a network[J]. Operations Research, 1983, 31(2):292-303.
[4] Cheng S, Higashikawa Y, Katoh N, et al. Minimax regret 1-sink location problems in dynamic path networks[C]//Proceedings of the 10th International Comference on Theory and Applincations of models of Computation Hongkong,China,May 20-22,2013.
[5] Higashikawa Y, Augustine J, Cheng S, et al. Minimax regret 1-sink location problem in dynamic path networks[J]. Theoretical Computer Science,2015, 24-36.
[6] Wang Haitao. Minmax regret 1-facity location on uncertain path networks[J]. European Journal of Operational Research, 2014, 239(3):636-643.
[7] Li Hongmei, Xu Yinfeng, Ni Guanqun. Minimax regret vertex 2-sink location problem in dynamic path networks[J]. Journal of Combinatorial Optimization, 2014.
[8] Ni Guanqun, Xu Yinfeng, Dong Yucheng. Minimax regret k-sink location problem in dynamic path networks[C]//Proceedinys of the 10th International Conference on Algorithmic Aspects in Information and Management, Vancouver,Canada,July 8-11,2014.
[9] Arumugam G, Augustine J, Golin, et al. A polynomial time algorithm for minimax-regret evacuation on a dynamic path[J].Computerscience,2014,588(c):1404-5448.
[10] Bhattacharya B, Kameda T. Improved algorithms for computing minmax regret sinks on dynamic path and tree networks[J]. Theoretical Computer Science, 2014, 607:411-425.
[11] Higashikawa Y, Golin M, Katoh N. Minimax regret sink location problem in dynamic tree networks with uniform capacity[M]. 2014, 8344:125-137.
[12] Xu Xinfeng,Li Hongmei. Minimax regret 1-sink location problem in dynamic cycle networks[J]. Information Processing Letters, 2015, 115(2):163-169.
[13] Naoyuki K, Katoh N. The universally quickest transshipment problem in a certain class of dynamic networks with uniform path-lengths[J]. Discrete Applied Mathematics, 2014, 178:89-100.
[14] Li Hongmei, Xu Yinfeng. Minimax regret 1-sink location problem with accessibility in dynamic general networks[J]. European Journal of Operational Research, 2015,250(2):360-366.
[15] 倪冠群, 徐寅峰, 徐久平. 考虑道路通行能力的应急避难点选址模型及算法[J]. 中国管理科学, 2015, 23(1):82-88.
[16] Higashikawa Y, Golin M, Katoh N. Multiple sink location problems in dynamic path networks[J]. Theoretical Computer Science,2015,607:2-15.
[17] Higashikawa Y, Golin M, Katoh N. Improved algorithms for multiple sink location problems in dynamic path networks[J]. Computer Science,2014:1405-2014.
[18] Mamada S, Uno T, Makino K, et al. An algorithm for the optimal sink location problem in dynamic tree networks[J]. Discrete Applied Mathematics, 2006, 154(16):2387-2401.
