Minsum k-sink Location Problem on Dynamic Path Networks with Non-confluent Flow Constraint
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 capac-ity,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(kn3)-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.
万方数据
维普
