主管:中国科学院
主办:中国优选法统筹法与经济数学研究会
   中国科学院科技战略咨询研究院

Chinese Journal of Management Science ›› 2017, Vol. 25 ›› Issue (9): 133-140.doi: 10.16381/j.cnki.issn1003-207x.2017.09.015

• Articles • Previous Articles     Next Articles

Min-max Multiple Sink Location Problem in Dynamic Path Networks with Different Traffic Capacity Constraint

ZHAO Rong, LIU Ke-yan, REN Pei-yu   

  1. Business School, Sichuan University, Chengdu 610065, China
  • Received:2016-02-25 Revised:2016-06-08 Online:2017-09-20 Published:2017-11-24

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 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.

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

CLC Number: