Research On Real-time Emergency Vehicle Routing Problem Under Different Urgencies

Natural disasters occur frequently in China,and the dispatch of emergency relief materials and vehicles after disasters is widely paid attention by the society.Aiming at the situation that the demand of disaster site appears in real time in the area of strong urgency and weak urgency,this paper explores the problem of the real-time route selection of emergency vehicles considering the rapidity and fairness strategies.The objective function of the fast strategy in the high urgency zone is to minimize the vehicle’s service completion time and delay cost.On this basis,the research of weak urgency area adds the constraint of vehicle capacity limit,and the objective function of fairness strategy takes into account the demand and service time of each disaster point.This paper mainly does the following two aspects of work:(1)The algorithm of real-time route selection for emergency vehicles under strong urgency is studied.Aiming at real-time demand point and fast strategy,this paper discusses the problem of online traveling salesman when the goal of rescue vehicles is completion time and delay time as little as possible.It is proved that neither deterministic algorithm nor randomized algorithm can obtain constant competitive ratio in general metric space,and then the lower bound of line segment network and uniform metric space is proved.An Observe and Move algorithm is proposed on the line segment network,and the Greedy algorithm is given on the uniform metric space.Finally,a numerical analysis on a uniform metric space shows that the algorithm has good applicability.(2)The algorithm of real-time route selection for emergency vehicles under weak urgency is studied.Aiming at real-time demand point and fairness strategy,this paper discusses the problem of online traveling repairman when the target of rescue vehicles is the sum of the product of service time and demand as small as possible,and takes vehicle capacity limitation into account on the basis of the previous chapter.The lower bound of the problem on two different networks is proved,to the point on the network are positive axis the Blindly turn left algorithm is designed.For general network,inverse leverage algorithm is designed,and the competition performance of the two algorithms is analyzed.Finally,the numerical simulation shows that the inverse leverage algorithm has better performance under different network sizes,server capacities and demand point densities.