Research Of Theory And Method Of Vehicle Routing Problems For Emergency Logistics

With the deterioration of the global environment,emergency incidents have become increasingly frequent,seriously endangering the safety of people's lives and property.In order to reduce the damage,emergency rescue work is particularly important.In emergency rescue,emergency logistics transportation is the key link of emergency rescue,which is closely related to the level of rescue efficiency and the success of post-disaster rescue.However,the relevant researches are still relatively few.The researches of the traditional vehicle routing problems aimed at minimizing the total route length.However,in emergency logistics,constraints such as vehicle restrictions,site restrictions,supply restrictions and road network restrictions need to be taken into consideration to minimize the waiting time in order to deliver relief materials to the disaster sites as soon as possible.To sum up,the research on the vehicle routing problems for emergency logistics(VRPEL)has important research value and social significance.Therefore,aiming at the constraints of vehicles,sites,supply and road network in emergency logistics transportation,several VRPEL models are established and the corresponding algorithms are designed to solve them.The main work of this thesis is as follows:(1)An improved discrete grey wolf optimization algorithm for vehicle routing problem for emergency logistics with minimum latency is proposed.Aiming at the comprehensive transportation scheduling demand of material supply and evacuation of victims in emergency logistics,based on the situation of limited vehicle quantity,taking the objective of minimizing the latency,the model of the vehicle routing problem for emergency logistics with minimum latency(VRPELML)is established.An improved discrete grey wolf optimization algorithm is proposed to solve the model.The algorithm is based on the traditional grey wolf optimizer and uses the integer encoding with routing identification for the transformation between the grey wolf space and the solution space.The discrete grey wolf update operator definition is proposed.The inferior-node heuristic neighborhood search strategy is introduced to enhance algorithm exploration ability and local optimization ability of the algorithm.Through the comparative experiment,the effectiveness of the improved discrete grey wolf optimization algorithm is proved.(2)A memetic grey wolf optimization algorithm for the vehicle routing problem for emergency logistics with capacitated constraint is proposed.Based on the limited number of vehicles and the limited capacity of vehicles,taking the objective of minimizing the latency,the model of the vehicle routing problem for emergency logistics with capacitated constraint(VRPELCC)is established.A memetic grey wolf optimization algorithm is proposed to solve the model.This algorithm is improves based on traditional grey wolf optimizer and the idea of the memetic algorithm for solving VRPELCC,and proposes a two-way transformation strategy based on grouping and recombination to convert a position vector of grey wolf to a vehicle routing group or vice versa.In the grey wolf optimization domain,the definition of hunting location fragment,the grey wolf genetic optimizing strategy and the adaptive grey wolf update strategy are proposed to improve the global search ability.In the problem space domain,the roulette selection neighborhood search optimization strategy and the continual optimization strategy for optimal solution based on routing reconstruction are proposed to the routing group optimization to improve the precision of the algorithm.The validity of the model and the algorithm is proved by the instance analysis experiment,and the validity of the algorithm and the strategies is further proved by the algorithms comparison experiments.(3)A hybrid firework grey wolf algorithm for the vehicle routing problem for emergency logistics with region restriction is proposed.In view of the limited number of vehicles,limited vehicle capacity and limited receiving site,taking the objective of minimizing the latency,the vehicle routing problem for emergency logistics with region restriction(VRPELRR)model is established,where a receiving point is set for each disaster point as the intersection point of the central distribution vehicles and the self-service vehicles of disaster point.A hybrid firework grey wolf algorithm is proposed to solve the model.In this algorithm,2-1 exchange neighborhood search strategy and 3-opt local search strategy are introduced to improve the searching ability of the algorithm,and a location direction prediction method is proposed to improve the searching speed for obtaining receiving points.The experimental results show that this algorithm can effectively solve the distribution order of the disaster points and the location of the receiving points at the disaster points.The waiting time of the proposed model is 14.19%lower than that of the VRPELCC model and 42.11%lower than that of the CVRP model,which fully proves the practicability of the model and the effectiveness of the algorithm.(4)A hybrid sweep grey wolf optimization algorithm for road-independent vehicle routing problem for emergency logistics is proposed.In the emergency scenario where the roads are not available and UAVs are used to replace ground vehicles for the delivery of lightweight critical emergency supplies,based on the limited UAV number and the limited load and electricity capacity of a UAV,as well as the impact of the flying state and the load on energy consumption of a UAV considered,taking the objective of minimizing the latency,a road-independent vehicle routing problem for emergency logistics(RIVRPEL)model is established,and a hybrid sweep grey wolf optimization algorithm is proposed to solve the model.In this algorithm,an integer encoding with start-point separation is proposed to transform the grey wolf space into the RIVRPEL solution space,and the probabilistic selection central position definition is proposed as well as the discrete grey wolf update operator is designed.The initial solution generation strategy using sweep method is proposed to improve the stability of the algorithm.The grey wolf explore strategy using partial inversion operator and the 2-opt local search strategy with azimuth are proposed to improve the global search ability and the local search ability of the algorithm.The experimental results show that the hybrid sweep grey wolf optimization algorithm can effectively solve the RIVRPEL model.The results obtained by solving the RIVRPEL model are 26.49%lower than those by solving the energy-constrained CVRP model,which proves that the model and algorithm have good practicability.(5)A hybrid grey wolf optimization algorithm for vehicle routing problem for emergency logistics with reallocation is proposed.Based on the limited number of vehicles,limited capacity of vehicles and limited supply,and on the basis of the definitions of time satisfaction,material satisfaction and comprehensive satisfaction proposed,a capacitated vehicle routing problem with maximum time satisfaction(CVRP-MTS)model and an emergency material distribution problem with minimum weighted standard deviation of satisfactions(EMDP-MWSDS)model are established,and a two-stage emergency logistics transportation and material reallocation strategy is proposed to solve the models.In the first stage,a hybrid grey wolf optimization algorithm(HGWOA)is proposed to solve the CVRP-MTS.The HGWOA adopts the real random key encoding strategy and the optimal split procedure decoding strategy.The chaotic search strategy,the 2-opt local search strategy and the 1-1 neighborhood search strategy are adopted to improve the search ability of the algorithm.In the second stage,a chaotic grey wolf optimization algorithm(CGWOA)is implemented in this thesis to solve the EMDP-MWSDS.The experimental results show that in the first stage,overall time satisfaction of the CVRP-MTS is 39.31%higher than that of the CVRP model.In the second stage,when 80%of the actual material quantity and 0.75 for the weight coefficient,the standard deviation of the comprehensive satisfaction is 0.0619,and the standard deviation of the supplies satisfaction is 0.0974.The distribution results effectively balance the psychological demands of the victims and supplies utilization efficiency.The two-stage emergency logistics transportation and supplies redistribution distribution strategy can obtain high time satisfaction and good supplies distribution results,which prove the effectiveness of the proposed models and algorithms(6)A dynamic grey wolf optimization algorithm for multi-objective vehicle routing problem for emergency logistics is proposed.Based on the limited number of vehicles,limited vehicle capacity and limited vehicle running time,considering the impact of vehicle unloading time at the demand point,and taking the objective of minimizing the latency and the excess cost of the vehicle running time,a multi-objective vehicle routing problem for emergency logistics(MOVRPEL)model is established,and a dynamic grey wolf optimization algorithm is proposed to solve the model.This algorithm is an improvement of grey wolf optimization algorithm for solving multi-objective problems.The decoding method which combines the equal random keys and the ROV rule is adopted.The dynamic non-dominated solution update strategy is proposed,and the temporary storage mechanism of the non-dominated solution set and the leader wolf generation mechanism based on the dynamic non-dominated solution set are established.A multi-objective improved 2-opt local search strategy for MOVRPEL is proposed to improve the convergence speed of the algorithm.The experimental results show that the proposed dynamic grey wolf optimization algorithm can effectively solve MOVRPEL.Finally,the work of the whole thesis is summarized and the future research directions are prospected.