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

作者：D. Pedrozo, Prateek Gupta, J. Meira, Fabiano Silva · 发表于：International Conference on Operations Research and Enterprise Systems · 年份：2025 · DOI：10.5220/0013165900003893 · 被引用次数：1 · 研究领域：Computer Science

: 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 meth-ods often rely on the REINFORCE approach with baselines like the Greedy Rollout, which uses a double-actor 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 learn...