Neural method builds vehicle routes by merging partial routes flexibly
Depot-Closed Multi-Component Construction for Neural Vehicle Routing
Machine Learning
Summary
Finding the best way to plan routes for vehicles is tough because decisions about which stops belong to which route are usually made one route at a time. The authors introduce a new approach that keeps track of many partial routes at once and merges them in any order, which allows better overall planning. They use a special way of looking at partial routes as if they already return to the depot, helping the method learn effectively. Their approach works better than some existing neural methods on various problem sizes and under different conditions.
What this means in practice
- •For logistics planners: Create better vehicle route plans by combining many incomplete routes flexibly to reduce total travel costs.
- •For supply chain software teams: Improve routing algorithms in software that must handle large and varied vehicle capacity constraints efficiently.
Authors
Shinichiro Hamada, Hisashi Kashima
Abstract
Most neural constructive solvers for the vehicle routing problem (VRP) use route-by-route construction, extending one route until completion before starting the next. This commits route membership early and hinders global coordination across routes. We propose multi-component construction, which maintains many route components simultaneously and merges them in an arbitrary order. This removes the depot-return cue that route-by-route construction obtains from the remaining capacity; to compensate, we introduce an interpretation in which every component is treated as an implicitly depot-closed route. Under this depot-closed interpretation, every intermediate state of standard CVRP construction is a complete feasible solution, and the exact cost reduction of a merge is the Clarke-Wright saving. The neural policy combines this CW-saving signal with the evolving component state to learn what to connect and when to connect. A policy trained only on CVRP100 outperforms the reported results of representative neural solvers on CVRP100-500 with greedy inference and, reused for ruin-and-reconstruct, performs strongly at all evaluated sizes up to CVRP1000. In a zero-shot Constraint Tightness evaluation with capacities from $C=10$ to $500$, it outperforms the reported neural solvers at every capacity. Controlled analyses show that robustness persists without CW grounding and point to learned route-closing behavior as a plausible contributor to the tight-regime degradation of learned route-by-route solvers.