Improving Cross-Problem Vehicle Routing with Locally Augmented Preferences and Representation Disentanglement

Imagine you're building a logistics system that needs to efficiently route vehicles for various delivery scenarios, like food delivery, package shipping, or ride-sharing. Currently, many systems require separate models for each type of routing problem, which is inefficient and time-consuming. When using reinforcement learning, you often run into issues where the rewards become less informative as the model improves, leading to stagnation. Similarly, preference optimization can get stuck when the generated solutions become too similar, limiting the model's ability to learn from diverse experiences. This is what's called reward-scale disparity and solution stagnation, respectively.

To tackle these challenges, the authors propose a new approach that combines a refined training algorithm with a more flexible architecture. The training method, called Preference Optimization with Locally Augmented Refinement (POLAR), enhances the learning process by refining the best solutions before forming comparisons, which helps the model learn more effectively. On the architecture side, the Progressive Layered Extraction (PLE) encoder separates common routing structures from specific constraints, allowing for better generalization across different routing tasks. Together, these innovations lead to a 21.3% improvement over previous benchmarks and better performance on unseen variants, making it easier for builders to create robust multi-task routing systems.

The introduction of POLAR and PLE offers a significant advancement in multi-task vehicle routing problem solvers.

The experiments demonstrate clear improvements over existing methods with solid ablation studies.