RL Hyper-Heuristic For Robust Vehicle Routing Problem With Uncertainty

With the rapid development of information technology,people pay more and more attention to modern logistics industry.The combination of information technology and logistics industry has given birth to a series of modern logistics transportation and distribution industries using big data and artificial intelligence technology.In fact,in transportation and distribution,the needs of customers are constantly changing,and potential customers will appear or disappear with the change of time and place.How to improve customer satisfaction and potential profit of logistics enterprises is of great significance.The classic vehicle routing problem(VRP)is a research hotspot in the field of logistics transportation and distribution,which takes various factors in vehicle transportation as conditions to find the shortest path planning scheme.In order to avoid the uncertainty of various factors in transportation,this paper studies the development of VRP(vehicle routing problem with uncertainty,UVRP),which is based on data-driven and robust optimization of uncertainty model to improve customer satisfaction and reduce logistics transportation and distribution costs.In this paper,based on the analysis of the theoretical development and practical significance of VRPUD,VRPUC and robust optimization methods in UVRP,this paper studies the model and algorithm,establishes UVRP model,and designs hyper heuristic algorithm based on reinforcement learning.The research work mainly includes the following aspects:(1)Firstly,the robust optimization methods for uncertain problems are summarized.The research status of robust optimization and its application in vehicle routing are reviewed.The shortcomings of robust optimization in vehicle routing are analyzed.In this paper,two kinds of models of robust optimization,i.e.the model of robust optimization with unknown distribution information about set and the model of distributed robust optimization with known partial distribution information,are summarized,and the necessity of using data-driven to reduce the degree of robust conservatism is proposed.(2)A hyper heuristic algorithm based on DQN reinforcement learning was designed and successfully solved the CVRP problem.In the high-level selection strategy of hyper heuristic algorithm,for the first time,we use DQN reinforcement learning algorithm to evaluate the performance of low-level operators;in the acceptance criteria,we use the combination of reward and punishment value and simulated annealing to establish a sequence pool for high-quality solutions,which leads the algorithm to search solution space more effectively.The clustering idea is used to improve the quality of initial solution.The standard example of CVRP is calculated and compared with other algorithms.The experimental results show that the proposed algorithm is effective and stable in solving CVRP,and the overall solution effect is better than that of the comparative algorithm,which paves the way for the following research of hyper heuristic algorithm based on reinforcement learning.(3)The robust optimization of VRPUD based on data-driven is studied.The uncertain parameters of customer demand are introduced and the uncertain model is established.The uncertain model is transformed into a robust model with adjustable parameters.At the same time,using the least square method in data-driven and historical data samples,the function of robust adjustable parameters related to the maximum demand,the range of demand and the given vehicle load is designed to optimize the robust robust robust model.Improve the reinforcement learning algorithm based on dqn for FMVRP to solve the robust model.Through the test experiment,it is proved that the robust optimization model can effectively reduce the customers affected by the uncertainty,greatly improve the customer satisfaction,effectively reduce the total cost,and the improved algorithm also has a good effect.(4)The distributed robust optimization of VRPUC based on data-driven is studied.In this paper,the customer demand service is introduced as the uncertain parameter of random probability,the vehicle path model of uncertain customer is established,and the uncertain model is optimized by distributed robust optimization method.Combined with the kernel density estimation method in data-driven,the distribution feature set of historical data samples is fitted to optimize the robust model.The reinforcement learning algorithm based on Q-learning algorithm is designed to solve the above model.The experimental results show that compared with the deterministic method,the distributed robust model can effectively reduce the total cost and the robust conservatism while ensuring the customer satisfaction.