Topology-aware model improves routes in vehicle delivery problems
TRCM: Topology-Aware Route-Consistency Modeling for Robust Neural Vehicle Routing
Machine LearningArtificial Intelligence
Summary
Vehicle routing problems involve figuring out the best routes for delivering goods to many locations. The authors noticed that most AI models decide one stop at a time without clearly understanding how stops group into routes. They designed a new approach that explicitly predicts which stops belong together on the same route, helping the AI make better decisions overall. Their method led to small but consistent improvements in routing efficiency across multiple tests.
What this means in practice
- •For delivery route planners: Generate more efficient delivery routes by explicitly modeling which customers should be grouped together.
- •For logistics software developers: Integrate pairwise customer assignment signals to improve neural vehicle routing algorithms in commercial logistics systems.
Authors
Peiheng Jian, Zhenwei Wang, Tiehua Zhang, Lei Zhang, Zhishu Shen, Ruibin Bai, Zhijun Ding
Abstract
Neural combinatorial optimization has enabled fast constructive solvers for the Capacitated Vehicle Routing Problem (CVRP), yet most autoregressive models still construct solutions through sequential node selection and represent route organization only implicitly. We investigate whether route-level customer co-assignment can be modeled explicitly and used to guide this node-level decision process. To this end, we propose TopologyAware RouteConsistency Modeling (TRCM), which reuses node representations from a standard autoregressive construction pipeline to predict pairwise same-route probabilities and injects them into customer selection as a route-consistency signal. Because sameroute supervision is both class-imbalanced and structurally uneven, TRCM combines structure-preserving augmentation with Topological Entropy (TE)- based reweighting to emphasize locally ambiguous customer pairs. Under matched decoding budgets, TRCM reduces the optimality gap from 3.67% to 3.28% on CVRP50 and from 2.11% to 1.99% on CVRP100; under 8-fold augmented inference, it reduces the CVRP100 gap from 1.61% to 1.49%. On XML100, TRCM*8Aug improves the average objective by 0.24%, with larger gains on several structurally informative factors. A controlled demand-reassignment test over 500 variants further shows more concentrated objective fluctuations. These results support explicit route-consistency modeling as an effective structural principle for autoregressive neural routing.