Rethinking Neural Vehicle Routing as Multi-Agent Decision Making

Vehicle Routing Problems (VRPs) are a fundamental class of combinatorial optimization problems with broad applications in logistics and mobility. A VRP inherently involves multiple vehicles cooperating to serve a shared set of customers. However, the dominant neural paradigm, including recent VRP foundation models, casts it as a single-agent sequential decision-making process in which a single policy constructs routes one at a time. We rethink VRPs from a multi-agent perspective and observe that this framing flattens a relational problem into a temporal one, hiding the cross-agent state, intent, and allocation structure that the problem naturally exposes. Our proposed approach jointly represents agents and actions, lets agents communicate during concurrent route construction, and adapts multi-start rollouts to the multi-agent setting. Our method matches or outperforms state-of-the-art neural baselines on cross-task VRPs and generalizes substantially better to unseen distributions and tasks. Our findings suggest that the multi-agent structure of VRPs is an underexplored axis for understanding and advancing neural combinatorial optimization.