关键词: 道路通行能力, 动态网络, 动态规划, 应急管理

Abstract: 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 c_e and a length l_e is l_eτ+ω/c_e-ω/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.

Key words: road capacity, dynamic network, dynamic programming, emergency management