Scheduling Of Emergency Evacuation Vehicles With Multiple Trips And Multiple Time Windows And Split Delivery

When huge-scale emergencies occur,a large number of affected people need to be evacuated to shelters.If the number of the affected people is more than the total capacity of the emergency cars,in another words,the emergency cars are not enough,it is necessary to make each vehicle serve multiple times to ensure that the transportation mission can be done quickly and efficiently.The scheduling problem of emergency vehicles can be regarded as an extended form of Vehicle Routing Problem(VRP).The traditional VRP requires that the demand at each demand site can not be greater than the capacity of vehicles,and all vehicles can only travel once time,and each demand site can only be visited by a single vehicle by just once time.In this paper,the emergency vehicle scheduling problem is transformed into a VRP with multiple trips and multiple time Windows and Split Delivery(VRPMTMTWSD),which means,during the emergency evacuation process,it is allowed that the vehicles can travel multiple times,the demand at each demand site can be split and the site can be served by more than one car.At the same time,the affected people with different degrees of injury are ensured to be evacuated within their required time windows.Based on this,a multiobjective VRPMTMTWSD mathematical model was established,and three scheduling goals,minimize the total completion time of the emergency evacuation,minimize the average arrival time to the shelter of all the victims,and minimize the total delay losses,were considered in the model.This paper simplified the calculation process of delay loss by introducing the definition of virtual sites.And based on the definition of virtual sites,the characteristics of the optimal solution of the mathematical model were analysised.Then an improved genetic algorithm is designed to solve the model,in which the victims are used as the basic unit of the coding and the virtual site numbers were used to represent the victims.Combining this gene encoding form,several format adjustment methods for the solutions of the model were proposed,in which the characteristics of the optimal solutions were used to standardize the solution format.In addition,this paper also designed a re-optimization method for the final convergent solution to make the algorithm more effective.In the end,the feasibility and validity of the model and algorithm were verified by an example.The result shows: the improved algorithm can effectively solve the mathematical model and it has excellent stability,which shows that the mathematical model and algorithm in this paper can provide decision-making guidance for multi-stage scheduling problem of emergency vehicles.