Abstract:

For the capacitated vehicle routing problem (CVRP), a method is proposed to decouple the capacity constraints using a hierarchical structure, split the complex CVRP into constraint planning and path planning, and perform deep reinforcement learning (DRL) optimisation for solving the problem respectively. Firstly, the upper layer allocates the vehicle distribution tasks based on the attention model and sampling mechanism to plan the set of subpaths that satisfy the constraints. Secondly, the lower layer adopts the pre-trained unconstrained attention model to plan the paths for the set of subpaths. Finally, the network parameters of the upper layer are optimized through the feedback training and iteration of the Reinforce algorithm. Experimental results show that the method generalizes to CVRP and heterogeneous CVRP tasks of different sizes, outperforms the state-of-the-art DRL method. Moreover, compared with other heuristic methods, in batch computing tasks, the solution speed improved by more than 10 times, while maintaining competitive solutions.

Key words: deep reinforcement learning (DRL), vehicle routing problem (VRP), attention model, hiera-rchical optimization