Research On Modeling And Optimization Of Emergency Material Distribution Problem

The model of Capacity Vehicle Routing Problem(CVRP)is widely used in the field of traffic,emergency relief materials distribution.In the emergency relief work,there are very high requirements on the timeliness of material distribution.We should ensure the timely distribution of the whole goods and materials in disaster areas,and also ensure the interests of a few affected areas and victims.Significant delays in one location cannot be exchanged for timely delivery of others.This requires carefully scheduling to minimize any delays and minimize overall delivery times.In order to better achieve the above goals,the emergency degree attribute of the settlement point is introduced,and the CVRP model considering the emergency degree is established.The two situations of the emergency degree determination and the emergency degree uncertainty are studied respectively,and the genetic algorithm combining the problem characteristics is designed to solve the problem.In the first step,the emergency relief CVRP problem with deterministic degree of urgency was studied,and the optimization goal is to reduce the delay time of relief material distribution and the total transportation time of relief vehicles.A vehicle routing problem model for disaster relief materials based on urgency is established and an improved genetic algorithm is designed to solve the model.Firstly,a task reallocation algorithm based on urgency is proposed as a local search operator.According to the urgency,the algorithm can rearrange the distribution vehicles or adjust the distribution order for the delay resettlement points,so as to reduce the delay time.For the vehicles without delay,the route should be optimized to reduce the total transportation time,so as to achieve the optimal goals of delay time and total transportation time.Secondly,multiple strategies are used to generate initial population.Compared with the First Come First Served(FCFS)Algorithm,Sorted by Urgency(URGS)Algorithm and Genetic Algorithm(GA)Algorithm on 17 datasets,the results show that: Compared with GA,Genetic Algorithm with Task Redistribution Strategy Based on priority Degree(TRUD-GA)has an average delay time reduction of 25.0% and an average transportation time reduction of 1.9%,and they are more obviously improved than FCFS and URGS algorithms.In the second step,the CVRP problem of emergency relief with uncertain emergency degree was investigated.With the optimization objectives of the total delay time and the total transportation time as,an emergency logistics planning model with uncertain emergency degree was established to simulate the change of emergency degree in disaster areas with Beta distribution,and the prediction was made meanwhile.In this thesis a path adjustment algorithm based on urgency is designed in the local search phase of genetic algorithm.The experimental results of 12 groups of data show that the proposed model and solution algorithm(Genetic Algorithm with Urgency-Dependent Path Adjustment),denoted as UDGA,can effectively reduce the delay and transportation time,which is significantly improved compared with some existing classical algorithms.Compared with URGS algorithm,the delay time is reduced by 89.7% and the transportation time is reduced by 38.0%.The UDGAalgorithm is stable and very robust.