Multi-Agent Route Construction for Routing Foundation Models

Routing foundation models pretrain one policy across vehicle routing variants and transfer it when constraints, fleets or objectives change. We develop a multi-agent interface organized around vehicle and partial-route states and route–customer extensions. Allocation-driven rollouts diversify pretraining of separate source backbones on 16 CVRP variants, and configuration comparisons link multi-depot transfer to route-slot tokens and a geometric prior. We evaluate weight-frozen transfer under supplied constraint features and feasibility masks, and fine-tuning with new vehicle attributes and objectives. Frozen reuse gives in-distribution costs comparable to the strongest baseline, a 17.19% mean gap on 32 unseen variants at $N=100$ against 34.89% for that baseline with the lowest gap on 28 of them, and the lowest neural gap on 37/65 CVRPLib instances. At 1M fine-tuning samples, our adaptation pipeline has lower costs than both adapted multi-task baselines in all min-max cells and in three of four min-sum cells. Within our architecture and a fixed recipe, pretrained fine-tuning at 200K target exposures reaches lower mean cost than scratch training at 1M in each of three fleet settings over three downstream seeds.