Lifelong Learner: Discovering Versatile Neural Solvers for Vehicle Routing Problems
This addresses the problem of off-the-shelf application of neural solvers in varying scenarios for researchers and practitioners in optimization and AI, though it is incremental as it builds on existing neural solver methods.
The paper tackles the limited versatility of neural solvers for vehicle routing problems (VRPs) by introducing a lifelong learning framework that incrementally trains a solver to handle VRPs in distinct contexts, achieving the best performance for most VRPs on instances up to 18k nodes.
Deep learning has been extensively explored to solve vehicle routing problems (VRPs), which yields a range of data-driven neural solvers with promising outcomes. However, most neural solvers are trained to tackle VRP instances in a relatively monotonous context, e.g., simplifying VRPs by using Euclidean distance between nodes and adhering to a single problem size, which harms their off-the-shelf application in different scenarios. To enhance their versatility, this paper presents a novel lifelong learning framework that incrementally trains a neural solver to manage VRPs in distinct contexts. Specifically, we propose a lifelong learner (LL), exploiting a Transformer network as the backbone, to solve a series of VRPs. The inter-context self-attention mechanism is proposed within LL to transfer the knowledge obtained from solving preceding VRPs into the succeeding ones. On top of that, we develop a dynamic context scheduler (DCS), employing the cross-context experience replay to further facilitate LL looking back on the attained policies of solving preceding VRPs. Extensive results on synthetic and benchmark instances (problem sizes up to 18k) show that our LL is capable of discovering effective policies for tackling generic VRPs in varying contexts, which outperforms other neural solvers and achieves the best performance for most VRPs.