INViT: A Generalizable Routing Problem Solver with Invariant Nested View Transformer
This addresses a key limitation in routing problem solvers for applications requiring adaptability, though it appears incremental as it builds on existing deep reinforcement learning methods.
The paper tackled the problem of deep reinforcement learning solvers for routing problems struggling to generalize to unseen distributions or scales, and proposed the Invariant Nested View Transformer (INViT) architecture, which achieved dominant generalization performance on TSP and CVRP problems with various distributions and scales.
Recently, deep reinforcement learning has shown promising results for learning fast heuristics to solve routing problems. Meanwhile, most of the solvers suffer from generalizing to an unseen distribution or distributions with different scales. To address this issue, we propose a novel architecture, called Invariant Nested View Transformer (INViT), which is designed to enforce a nested design together with invariant views inside the encoders to promote the generalizability of the learned solver. It applies a modified policy gradient algorithm enhanced with data augmentations. We demonstrate that the proposed INViT achieves a dominant generalization performance on both TSP and CVRP problems with various distributions and different problem scales.