Integrating Machine Learning and Optimisation to Solve the Capacitated Vehicle Routing Problem

The Capacitated Vehicle Routing Problem (CVRP) is a fundamental combinatorial optimisation challenge in logistics. It aims to optimise routes so a fleet of vehicles can supply customer’s demands while minimising costs - that can be seem as total distance travelled or time spent. Traditional techniques - exact algorithms, heuristics and metaheuristics - have been thoroughly studied, but this methods often face limitations in scalability and use of computational resources when confronted with larger and more complex instances. Recently, Graph Neural Networks (GNNs) and Graph Attention Networks (GATs) have been used to tackle these more complex instances by capturing the relational structures inherent in graph-based information. Existing methods often rely on the REINFORCE approach with baselines like the Greedy Rollout, which uses a doubleactor architecture that introduces computational overhead that could hinder scalability. This paper addresses this problem by introducing a novel approach that uses a GAT network trained using reinforcement learning with the DiCE estimator. By using DiCE, our method eliminates the need for a double-actor structure, which contributes to lower the computational training cost without sacrificing solution quality. Our experiments indicate that our model achieves solutions close to the optimal, with a notable decrease in training time and resource utilisation when compared with other techniques. This work provides a more efficient machine learning framework for the CVRP.