Models And Algorithms For Post Disaster Rescue Route Optimization

Natural disasters occur frequently in China.Responding to natural disasters mainly depend on three aspects: pre-disaster prevention,post-disaster response and recovery.Because natural disasters are unevenly distributed and difficult to predict,post-disaster response is irreplaceable in responding to natural disasters.This thesis studies the routing optimization problem in natural disaster emergency rescue.Compared with the general commercial logistics optimization problem,the emergency rescue logistics optimization has the following basic characteristics.First of all,the supply capacity is limited.Because of the need to respond within a short period of time after the disaster occurs,it is often difficult to meet all the needs of the disaster area in the first time after the disaster;Secondly,the demand for materials is difficult to obtain accurately.Because disasters are sudden,the time and space distribution of demand,the types and quantities of demand are difficult to predict accurately;Finally,the pursuit of social benefits,different from the commercial logistics optimization problem,emergency logistics optimization pays more attention to the social benefits of the material transportation process rather than economic benefits,that is,the efficiency indicators such as rescue time and rescue risk are often used as optimization targets.Based on above basic characteristics of emergency logistics optimization problems,this paper studies the multi-location emergency rescue routing problem under sufficient supplies,the emergency rescue location-routing-allocation problem with limited supplies and the emergency rescue location-routing problem with stochastic demand.The mathematical models of the above problems are based on the classic vehicle routing problem(VRP)and location-routing problem(LRP)in operational research.The contents of each part are as follows.Firstly,A rescue routing optimization model considers safety risk and time expenditure is established for the case where multiple groups of rescuers can be dispatched from the departure point and return to replenishment point simultaneously.Based on the multi-objective evolutionary algorithm,this paper proposed a genetic algorithm for solving the preceding model.The crossover and mutation procedure ensure the path obtained is always feasible.The elite preservation strategy chooses optimal solution among the Pareto non-dominated solutions.Secondly,in view of the limited supply of various types of relief supplies in the first time after a disaster,a multi-objective two-echelon location-routing-allocating optimization model considering multi-depot and heterogeneous materials is proposed.The arriving time,satisfaction degree of demand nodes and the fairness of material supply are the optimization goals.The multi-objective optimization problem is solved by three single-objective sub-iterative processes and a multi-objective iterative process based on the method using the differential evolution strategy and the constrained optimization strategy.The vehicle routes and material distribution is optimized at the same time.Finally,in view of the difficulty in accurately estimating the material demand in the disaster area after the disaster,the total time spent on rescue is taken as the optimization goal,and the location-routing optimization model of single-depot and multi-satellite with random demand is established.The model assumes that the material demand in the disaster area is a random variable that satisfies certain distribution,constraints containing random variables are transformed into chance constraints,and obtains the equivalent form of the chance constraint,thus the original stochastic programming model is transformed into a deterministic integer programming model.The large neighborhood search algorithm is used to optimize the assignment of satellite nodes and the demand nodes,as well as the vehicle routing.Each part verifies the effectiveness of the algorithm through test data of different scales.