研究应对突发事件的避难点选址问题。假定一条直线型动态路径网络上有n个顶点，由n-1条边相连，每个顶点有一个权重，每条边有一个容量。边的容量表示路段通行能力，是单位时间内允许进入该路段的最大聚集量。目标是在此网络中选择k个避难点，并为每个顶点指定一个避难点，使得所有顶点的权重到达各自避难点的最大时间最小。首先根据问题的性质，通过建立动态表结构，结合二分法的思想，在O（nlogn）时间内求解单个避难点选址问题。然后在此基础上，针对k-避难点选址问题，通过更新动态表，结合动态规划方法，设计了时间复杂度为O（knlogn）的递归算法求解。
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.
[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.
