GenRoute: A Minimal Constructive Neural Solver for Multi-Depot Vehicle Routing Variants via Depot-Conditioned Decoding

The multi-depot vehicle routing problem asks how vehicles operating from several depots should serve customers at minimum travel cost. Neural methods can construct solutions quickly, but existing approaches handle multiple depots and operational constraints by adding specialized encoders, expert networks, or fine-tuning a separate model for each variant. We show that a substantially simpler design is sufficient. Building on the Attention-Model/POMO line of constructive solvers, our first contribution is that multi-depot structure needs no specialized machinery: it is enough for the decoder's standard context to carry the currently active depot. This induces an implicit sequential decomposition: a shared encoder represents the complete instance, while the decoder constructs one depot-centered part of the solution at a time, jointly deciding customer allocation and routing without explicit clustering. Each encoder layer augments its attention logits with a lightweight learned bias computed from pairwise distances. A three-stage curriculum first trains the core multi-depot problem and then progressively expands the same architecture into a single model covering 16 combinations of open routes, mixed backhauls, route-length limits, and time windows. On held-out evaluations the core model attains a 2.26% gap to reference solutions, while the final generalist reaches a 3.95% mean gap across 16 multi-depot variants and the lowest gap in 9 of 12 depot-count/problem-size settings.