Latent recursion improves neural routing for vehicle delivery problems
RELAGRAM: Recursive Latent Graph Model for the Capacitated Vehicle Routing Problem
Machine LearningNeural and Evolutionary Computing
Summary
Finding efficient routes for delivery vehicles is a tough problem, especially when vehicles have limited capacity. This paper shows a new neural network approach called RELAGRAM that repeatedly processes graph information to help solve these routing challenges. Using a transformer model that updates relationship information between locations, RELAGRAM produces good routes with fewer parameters compared to some traditional methods. Additionally, it can handle larger delivery problems without being retrained, which suggests it might work well in real-world routing tasks.
What this means in practice
- •For logistics teams: Generate efficient delivery routes for fleets with vehicle capacity limits using a neural model that generalizes to large-scale problems.
- •For autonomous vehicle developers: Incorporate latent recursion models to improve route planning for automated delivery vehicles handling many stops.
Authors
Vladimir Kirill Bickov, Neil Yorke-Smith
Abstract
Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.