Chain-of-Context Learning: Dynamic Constraint Understanding for Multi-Task VRPs
This work improves routing efficiency for logistics and transportation by incrementally enhancing constraint handling in multi-task VRPs.
The paper tackles the problem of multi-task Vehicle Routing Problems (VRPs) by addressing the oversight of constraint and node dynamics in existing solvers, proposing Chain-of-Context Learning (CCL) to capture evolving context for fine-grained adaptation, resulting in state-of-the-art performance on 48 VRP variants, including best results on all in-distribution tasks and most out-of-distribution tasks.
Multi-task Vehicle Routing Problems (VRPs) aim to minimize routing costs while satisfying diverse constraints. Existing solvers typically adopt a unified reinforcement learning (RL) framework to learn generalizable patterns across tasks. However, they often overlook the constraint and node dynamics during the decision process, making the model fail to accurately react to the current context. To address this limitation, we propose Chain-of-Context Learning (CCL), a novel framework that progressively captures the evolving context to guide fine-grained node adaptation. Specifically, CCL constructs step-wise contextual information via a Relevance-Guided Context Reformulation (RGCR) module, which adaptively prioritizes salient constraints. This context then guides node updates through a Trajectory-Shared Node Re-embedding (TSNR) module, which aggregates shared node features from all trajectories' contexts and uses them to update inputs for the next step. By modeling evolving preferences of the RL agent, CCL captures step-by-step dependencies in sequential decision-making. We evaluate CCL on 48 diverse VRP variants, including 16 in-distribution and 32 out-of-distribution (with unseen constraints) tasks. Experimental results show that CCL performs favorably against the state-of-the-art baselines, achieving the best performance on all in-distribution tasks and the majority of out-of-distribution tasks.