关键词: 车辆路径, 深度强化学习, 局部表征, 上下文多尺度信息, Greedy Rollout

Abstract: Vehicle routing problem is a combinatorial optimization model widely used in the field of modern logistics and transportation, involving many fields such as resource allocation, process optimization, network planning, logistics and transportation. It is a typical NP-hard combinatorial optimization problem with high complexity and many constraints. The traditional vehicle routing problem solving methods include exact algorithm, heuristic algorithm and approximate algorithm, but it is difficult to obtain the optimal solution under multi-objective and multi-constraint conditions. In recent years, the deep reinforcement learning method has been gradually applied in the field of vehicle routing problem solving, through the construction of neural network models to autonomously learn the characteristics of problems and optimize in complex scenarios. However, the existing methods based on deep reinforcement learning usually face the problems with long time, slow solving speed and difficulty to obtain accurate solutions in practical applications. To solve them, this paper proposes an improved multi-objective vehicle path planning method based on deep reinforcement learning.
This method uses a variety of encoders to dig into multi-source information, and introduces a context-based multi-scale information decoder structure to construct an accurate decision sequence. In the encoder part, each sub-problem in the multi-objective combinational optimization problem is encoded to realize the deep mining and comprehensive capture of multi-source information. The decoder constructs an accurate and coherent decision sequence based on the context multi-scale interaction space. During the model training phase, the Greedy Rollout baseline method in the REINFORCE algorithm is adopted to improve the solving quality and stability of the model and accelerate the convergence process.
To verify the validity of the proposed method, experimental data are obtained from classical vehicle routing problem datasets and evaluated by generating problem sets of different sizes through simulation. Through experiments on problems of different scales and comparison with existing deep reinforcement learning algorithms, the results show that the proposed algorithm is superior to existing deep reinforcement learning algorithms in solution quality and speed, and shows excellent robustness and generalization in generalization experiments. Specifically, in terms of solution quality, the proposed algorithm can solve the multi-objective combinatorial optimization problem accurately, and the result quality is significantly improved. In terms of solving speed, the learning stability of the model is improved with the REINFORCE algorithm based on the Greedy Rollout baseline, the convergence process is accelerated, and the efficiency is significantly improved. In terms of generalization, the excellent robustness and efficiency of the algorithm in dealing with complex, and high and multi-variable interaction problems are verified by generalization experiments.
The improved model and algorithm proposed in this paper provide a new solution to the multi-objective vehicle path planning problem, which has important theoretical and practical significance. In future studies, we can further optimize the model structure, expand its application in dynamic VRP problems and try to combine with other optimization methods to improve the model performance.

Key words: vehicle routing, deep reinforcement learning, local representation, contextual multi-scale information, Greedy Rollout