Mean-Field RL for Large-Scale Unit-Capacity Pickup-and-Delivery Problems
Authors: Kai Cui
Sharif Azem
Christian Fabian
Kirill Kuroptev
Ramin Khalili
Osama Abboud
Florian Steinke
Heinz Koeppl
Venue: Accepted by TMLR ()

Abstract: Solving large-scale vehicle routing problems (VRPs) is NP-hard and poses a computational challenge in numerous applications such as logistics. Meanwhile, mean-field control (MFC) provides a tractable and rigorous approach to controlling many agents. We provide a solution to pickup-and-delivery VRPs via scalable MFC. In combination with reinforcement learning (RL) and clustering, our MFC approach efficiently scales to large-scale VRPs. We perform a theoretical analysis of our MFC-based approximation, giving convergence results for large VRP instances and error bounds for clustering-based approximations. We verify our algorithms on different datasets and compare them against solutions such as OR-Tools, PyVRP and heuristics, showing scalability in terms of speed for mean-field methods, for the first time in discrete optimization. Overall, our work establishes a novel synthesis of MFC-based RL techniques, vehicle routing problems and clustering approximations, to solve a hard discrete optimization problem of practical use in a scalable way.

Published in Transactions on Machine Learning Research (09/2025)
Mean-Field RL for Large-Scale Unit-Capacity Pickup-and- Delivery Problems
Kai Cuil?, Sharif Azem', Christian Fabian', Kirill Kuroptev', Ramin Khalili?, Osama Abboud?, Florian Steinke', Heinz Koepp!'
Technische Universität Dormstaat, "Huawei
(kai tuii.cui.n de, sharifazemm/@gmail. com, fchristian faaiia,ann.abban, kirill. htt...rrropprr/ttuddddsttaatt..
kramin.khalil,, osama. abbbaaaabbddHduuueeeeee com, [florian. saoorinn.tteinke, heinz. koepp]/@tu-darmstaae de
Reviewed on OpenReview: https://openreuue openreview. net/ forum? id- E8JRsudyDR
Abstract
Solving large-scale vehicle routing problems (VRPs) is NP-hard and poses computational challenge in numerous applications such logistics. Meanwhile, mean-field control (MFC) provides tractable and rigorous approach to controlling many agents. We provide solution to pickup-and-delivery VRPs via scalable MFC. In combination with reinforcement learning (RL) and clustering, our MFC approach efficiently scales to large-scale VRPs. We perform a theoretical analysis our MFC-based approximation, giving convergence results for large VRP instances and error bounds for clustering- baased approximations. We verify our algorithms on different datasets and compare them against solutions such as OR-Tools, PyVRP and heuristies, showing scalability in terms of speed for mean-field methods, for the first time in discrete optimization. Overall, our work establishes a novel synthesis of MFC-based RL techniques, vehicle routing problems and clustering approximations, to solve a hard discrete optimization problem of practical use a scalable way.
1
Introduction
Solving large-scale vehicle routing probloms (VRPs) an area of practical interest in operations research.
There are mumerous applications, ranging from dial-a-ridh (Cordeau & Laporte 2007 Ho et al. 2018) over
shared use of autonomous vehicles (Narayanan al. 2020 Lin et al. 2012), or delivery logistics [Bortfeldt &
Yi. 2020
Wang al.] 2021 Arunapuram et al., 2003 Zhang & Lygeros 2023) to agriculture (Bochtis &
specific variant: the unit-capacity pickup-and-delivery problem (PDP), where large fleet of vehicles must serve an equally large number of transport requests. The unit-capacity case can also be solved as a capacitated VRP (CVRP), and beyond unit-capacity our framework also applies, but scalability challenges remain. This problem structure is motivated by emerging large-scale logistics challenges with thousands of agents, such as in ride-sharing, food delivery and last-mile gig-cconomy services (c.g., Amazon Flex). Due to the immense number of vehicles and customers, scalable
Sørensen 2009 2010]. In this work, focus
solutions remain an active area of research (Konstantakkoonloss et al. 2022 Zhang al. 2022).
Motivated by complex applications with many vehicles and tasks, there has been growing interest in solving large-scale VRPs via machine learning. Learning approaches for finding scalable VRP solutions are manifold and differ in their conceptual design. Some learning techniques split the initial VRP into smaller and more tractable subproblems and delegate their solution to subsolvers [Li et al., 2021bb to reduce the overall computational complexity. Other research (Lei et al.; 2022) uses transformers to increase the scalability of
learning algorithms. For recent overviews on learning VRPs, see Li et al. (2022); Bogyrbayeva et al. 2024).
1.1 Contribution
Scaling solutions for very large NP-hard problems can be difficult. For this reason, our approach based on mean-field control (MFC) (Fornasier Solombrino. 2014 Bensoussan al. 2013) the cooperative form of

---

Published in Transactions on Machine Learning Research (09/2025)
mean-field games (Lasry & Lions 2007 Saldi et al. 2018). This will allow method to scale arbitrarily large problem sizes, with constant problem complexity in the limiting problem, and linear complexity in the number of agents / objectives for the actual finite problem, by sampling agent routes. The idea of MFC is to abstract a large number of indistinguishable agents - in our case vehicles - into their mean-field (MF) probability distribution. Working with the MF distribution entails both solid theoretical properties as well as reduced computational complexity which, in turn, paves the way for scalable learning algorithms. In contrast. to existing works, our MF-based solution allows to solve arbitrarily large problems at constant computational complexity. We propose JJFC-based reinforcement learning (RL) for solving large-scale VRPs with pickup and delivery, where our learning approach scales to arbitrarily large numbers of vehicles and deliveries.
Our contributions are summarized as: (i) We present a first formulation of vehicle routing a hard discrete optimization problem - as MFC & RL; (ii) We give general and special finettned algorithms for solving large-scale vehicle routing problems, considering both general pretraining as well as fine-tuning to problems; (iii) We prove convergence to the MF limit for the case of large-scale VRPs with many vehicles and locations. Moreover, we show approximate probable optimality of MFC solutions and give error bounds for general metric spaces with clustering approximations; (iv) We empirically evaluate by comparing against OR-Tools, PyVRP and hcuristics, showing potential generalization capabilities and speeds of MFC for different large-scale settings, where existing methods for discrete optimization can be expensive.
1.2 Related Work
In comparison to our work, a majority of recent related work does not consider pickup-and-ddeiverr problems. We also find that few other RL works allow few minute fine-tuning times for large instances, a speed our method achieves. Morcover, very few works consider largo-scale VRPs with tens of thousands of nodes and vehicles. In the following, we discuss those works that are most related to our work.
VRP. For example, Zhou et al. (2024) consider different variants of VRPs, but no pickup-and-deliver focusing multi-task settings with generalization and presented for up to 100 nodes. Similar smaller settings are found in the following works, such as DPN (Zheng et al. 2024), which considers min-max VRPs via sequential RI-based partition and navigation methods. In contrast, we consider near-arbitrarily large VRP. In Liu et al. (0244) VRP with heterogeneous capacities are considered via RL-based solutions, and evaluated for small fleet and customer sizes of up to and 100. As for other recent work, Wu et al. (2024) study multi-objective VRPs using collaborative RL, Xiao et al. (022)) demonstrate fast transformer based solutions, and Kikuta et al. (022)) consider smaller variants of VRP for electric vehicles. On the other hand, Min et al.
(2024) propose graph-learning methods for traveling salesman problems (TSP), and Jiang et al. (2023) focus on out-of- distribution generalization. Furthermore, Xia et al. (2024) explore heuristics for the special case of TSPs, highlighting scalability issues with current solutions and proposing scalable Monte Carlo tree search. Our contribution similarly is a method that provides an automatically scaling solution for certain VRPs.
Large-scale combinatorial optimization. As for literature on large-scale combinatorial optimization, recent works include meta-learning and reinforcement learning for combinatorial optimization (Qiu al., 2022), graph-based diffusion solvers (Sun& & Yang. 2023), and methods that generalize pre-trained models or learned heuristics to arbitrarily large TSP or VRP instances (Fu et al. 2021 Hou el al. 2023 Other neural combinatorial optimization approaches also aim for large-scale generalization via encoder- architectures (Luo et al. 2023). In contrast, our MFCCbased RL method provides a methodology for reducing multi-agent RL (MARL) to single-agent RL of constant complerity, regardless of number of agents.
Pickup-and-delivery problems. Lastly, most related to our sctting, also known as pickup-and-ddliven problems (PDP), Li et al. (2021a) and Zong al. (2022) solve single-agent and multi-agent PDP using deep attention-based (mulli-agent) reinforcement learning methods. A direct comparison with these methods can be challenging due to the difference in scale. For instance, the MAPDP framework (Zong et al. 2022 uses a Transformer that computes attention across all nodes, leading to a computational complexity that scales quadratically with the number of nodes. This ually becomes intractable for large problems such as the 50,000-node problems that are a primary focus of our work.
While it is true that recent learning basod routing solvers with heavy decoders, such as BQ-NCO (Drakulic) 2023 L.HD Tuo et al. 2023). and STGD (Pirny & Grimm 2024), in fact demonstrate generalization et al.
2

---

Published in Transactions on Machine Learning Research (09/2025)
to large-scale CVRP instances (c.g,, up to 100k nodes by applying subquadratic attention techniques Luo et al. 2025 ) applying them directly to our problem is non-trivial. First, as discussed, our unit-capacity PDP can only be reformulated as CVRP with asymmetric non- non-Euclidean distances. Second, some adaptation would be needed to handle the specific pickup-and-deliver structure, while higher than unit capacity cannol be modelled as asymmetric CVRP. To use existing solvers in this manner would likely require a distance-mattrix-bass
encoder, such as those in Kwon et al. (2021) or [Son et al. (2025), rather than a node-coordinate-based one. Given these required adaptations, we consider direct benchmark to be beyond the scope of this foundational paper, which instead introduces new paradigm for extreme-scale PDP.
Mcan-field modelling. Modelling agent MFs is done in analogy to general MFC (Angiuli et al. 2022
Carmona et al.) 2023 Cui et al., 2021], with policy gradients (Augiuli et al., 2023 Carmona et al. 2019 Cui et al.) 2024 as a solution for the resulting high-dimensional RL problem. However, VRPs require a generalized formulation with delivery distributions: We first suitably rewrite between VRP and multi-agent control with MFs. Morcover, we have two coupled MFs not modelled by general MFC-based MARL, as the two MFs of agents & objects create double limit, which we resolve by introducing ratio of objects and agents. To our knowledge, our work is the first to consider MF-based combinatorial optimization such VRP, in contrast to related but distinct traffic flow analysis using mean-field games Huang et al. (2021) Importantly, we also obtain probable approximate optimality of any realization in MFVRP, not obtained in standard MFC, via embedding finite MFVRP into the limiting system, see Section 2.5 for a. discussion.
2 Mathematical Framework
In this section, we connect VRP, MARL and MFC. Proofs for theoretical results are found in the Appendix. Notation: For any integers k,1, let [k] = 21,2,..... ... k) and [k] + I == (1 (1+1,.... I + k). For any metric space A, let (A) denote Borel measures bounded by over A, with probability measures P(A) S (A))).
2.1 Capacitated VRP with Pickup and Delivery
The finite problem of interest is vehicle routing problem with pickup and delivery. We consider large number of N vehicles and M objects, each of which needs to be transported from one position to another in some metric space X. The methodology applies to any metric space. For example, X' can be a subset of Euclidean space, or it could be nodes on a road graph with appropriate node distances. We index vehicles and objects by indices in N = [N] and M = [M] + N respectively. We denote distances between objects or vehicles at x. y E X as d(x, y). For example, we consider Euclidean spaces X' S I with the Euclidean distance d(z,)) v) = || yll2 as well as finite spaces embedded into the Euclidean space. More generally, we also include positions on road network or graph. Each object or transport mission j M is specified by its source 8j E X' and destination d,- E X, while each vehicle i E A starts at an initial depot s; E X.
For simplicity of exposition, consider vehicles with carrying capacity of one object. A more general setting with larger capacities can be considered analogously, see also Section 2.5] though the state-action complexity will be exponential in the transport capacity. The goal is to optimize which vehicles transport which objects in which order, such that an overall global transport cost minimized. Formally, the overall cost is given as the total distances travelled. That is, we define the set of all indices V [N M]= -N-UUM and optimize the objective J : ExEN Σisev di for binary decision variables b == (6t) (6ty)oeN, (jjv,,,v,, where by is one whenever vehicle k moves from depot or transport mission i to with induced travel cost between depols or mission sources i,j E
d, = d(s; de) + d(d;, 8,),
(1)
where the depot's source and destination are equal to the depot's position.
We consider a standard tour length constraint C E N as maximum number of missions to perform by any single vehicle, e.g., time or energy constraints. At least for carrying capacity of one, the above problem can also be solved via CVRP by considcring each mission as one location, but with asymmetric distances ! due to differing pickup and delivery locations. The optimization well known to be NP-hard. We introduce MF-approximations for the important case of many missions and vehicles.
3

---

Published in Transactions on Machine Learning Research (09/202))
dag
Abstractinto mean Solds
state
FF
x Vi [N]
612
42
d24
V
P.V
πI
PEOLD (2003) (9699)
Fretz VEP
Figure 1: Simplified overview of finite VRP and MFVRP. Exemplary system with four states, seven trucks and 14 packages and destinations. Orange (blue green / purple) packages should be delivered to orange (blue green purple) destinations / houses. For Euclidean locations, each location is assigned to one state via clustering, see Section B
2.2 VRP as Mean-Field Multi-Agent Control
We consider a soquential solution of VRPs formulated as multi-agent control problem, i.c. performing one delivery per vehicle in each "time step" E N (decision epoch, not real time). The multi-agent control formulation VRP is obtained by assuming an underlying distribution of vehicle and object locations, and introducing both current vehicle states and remaining transportation missions. That is, we assume each location zj of vehicle i E N the vehicle state is sampled from some initial distribution μo P(X), 2) ~ /40- Analogously, the source-destination tuples (sy, dj) of objects j [M] are sampled from object distribution My P(22), (sj.d)) Va- Consider fixed ratio R = M/N of objects per vehicle to transport. Then, due to indiscernibility of objects and vehicles at the same locations, the entire information of a VRP is contained in the parameter R and the empirical distribution of vehicle states μn²" = # E, Sng. and source and destination locations 10 1 E, ((s,,d,) the empirical MFs time zero. Here, the MFs can be understood as "histograms" over and X² respectively, with Dirac measures 5. For a visualization, see the left side of Fig. which is the original VRP and is transformed into a problem of vehicle and object flows.
The current intermediate state of VRP solution during execution at any time t is given by counting the remaining objects to be transported each source and destination, as well as the current positions of vehicles. Indeed, the current state is contained in vy" M ES not transported yet (ssydj)) and N 인/2 E,da; Here, the states of vehicles of are moved by vehicle actions up E X' to x = = When moving, each vehicle transports a random object from of ut, if one exists.
The reward is then given by the negative distance travelled by all vehicles plus reward for each delivered package, ri ca # E, wi), where #. is the number of delivered objects in epoch / and constant ca 2 2 diamm(X). The choice of ensures that optimal undiscounted control maximizing J = E [E. r is also an optimal VRP solution: the reward for a single delivery must outweigh the maximum possible travel distance saved by skipping it. Analogously, we add a final cost for moving back to the depot. We award a larger final reward Thomus whenever all objects have been transported; this is necessary to properly incentivize completion, as agents are also penalized for the final return trip to the depot. times the fraction of objects not delivered is added it is not strictly necessary for optimality. Here, terminate an episode when all objects are delivered after reaching an episode time horizon of Imax C to respect the maximum tour length constraint C' E N.
cost of Cmiss reward shaping term to guide the RL agent, though
2.3 Mean-Field VRP
To obtain tractable MFVRP, in the infinite vehielo-object limit N so with M RN, R 0 the initial empirical MFs are given by #a and ve via law of large numbers. It suffices to describe the system by limiting deterministic MFs pa P(2), us E Bi (2)) at all times Here, at each time i, the MFVRP action is
4

---

Published in Transactions on Machine Learning Research (09/2025)
transportation by each of infinitely many vehicles, i.. we assign all vehicles from current to next location and transport objects on the way. In general, the action at time I is therefore a transport map 7, on X.
For finite X, the action can be numerically represented as a transition matrix T;: X' x X + [0, with TiTi(s, ()) = for all s E X, encoding which fraction Ti(s, d) of vehicles at s E X will move to d E X. Since the vehicle-object-ratio R > O, the remaining transportation tasks decrease according to
Ue41 d) max (1 d) (ss))
(2)
while the MF of vehicles evolves as
Pt- (d)= (d)= (c()))((s.dd)
(3)
SEX
Hence, the MFC problem is single-agent Markov decision problem, with states (j4, (4) and actions 7,, where the reward is given by delivered objects minus distance travelled (on average per agent, which is equivalent to optimizing the total travelled distance)
Tt Σ ca (m d)s d,Ex
(4)
In other words, we learn an "upper-level" MFC policy & via RL, such that Tr ~ #(T, Mey v1). See also Fig. for a visualization. Final rewards and costs are handled analogously. We choose ca > 2diam(2) to ensure optimality of delivering all objects instead of waiting until termination.
The dynamics of our MFVRP formulation exhibit strong connection to Optimal Transport (OT). Equation 3
is transport map that pushes the vehicle distribution 14 forward to 14+1- Equation (2) resembles continuity equation with a sink term, where the mass of the object distribution V, is depleted by the flow of vehicles. Our problem can be interpreted as finding a sequence of conditional transport plans {Ti} that steer the coupled distributions (Me 11) to minimize total transport cost, subject to the constraint. of depleting ii- This perspective links our work to dynamic OT formulations Santambrogio (2010), though our setting is distinguished by the coupled discrete-time dynamies between optimal transport flow μr and object flow vt-
2.4 Theoretical Guarantees
To show optimality of MFC in VRP, the three introducod models are rigorously analyzed. We first sketch how the VRP objective is exactly given by the finite MARL system objective, and then how the MARL objective is approximately solved by the limiting MFVRP MDP.
MARL vs. VRP. The connection is made by noticing that vehicle trajectories in the MARL system (r), up. æ4, u2. correspond to a solution of the VRP. Any objects not transported by the trajectory are handled by postprocessing, by transporting objects by random available vehicles at the end. Assuming optimal behavior of vehicles in the MARL problem and therefore that all objects are transported, the cost. of the VRP as total distance travelled is exactly given by the negative sum of rewards J, up to a constant episodic reward for delivering all objects. Therefore, optimally solving the MARL problem optimally solves the VRP. In other words, for any vehicle i E N, assign 6/ = whenever it transports objects j and then k as well as bi = for moving from depot i to the first object j and by, for the last object, thereby removing any unnecessary in-between movements of each vehicle that does not transport objects.
MARL MFC. MFC solution solves the infinite-vehicle model, and approximates optimal solutions in the finite MARL system by allowing the sampling from T, random realization of the deterministic MFC system (2) and (3) constitutes MARL solution and therefore also VRP solution. Vehicles take actions according to deterministic, or hence equivalently constant, ,, = T, at all times / S 4max up to termination at. time max after which we randomly transport any remaining objects. For a visualization see Fig.
An error analysis of finite VRP gives us estimates of the asymptotic error of MFC assuming an infinitude of vehicles and objects, instead of finitely many. We then learn deterministic MFC policy At e.g., after the
5

---

Published in Transactions on Machine Learning Research (09/2025)
convergence of stochastic policy gradient methods (Schulman et al. 2017], or by using deterministic policy gradients (Silver et al. 2014), which can be provably near-optimal in large finite problems.
Theorem 2.1 (Propagation of Chaos). Let X' be finite and consider some deterministic a. Then, al any time E N, the error between the umite-agent empirical measures and the mean-field measures is O(1/VN), i.e.
E [1l pellso] = -((1/V)) and E [ - vello]] = O(I/VN)
Consequently, l| - pelloo + O and | - no + 0 in probabilily as N + co.
As a result, we can obtain approximate optimality bounds given a finite N-agent VRP.
Corollary 2.2 (Probable Approximate Optimality). Let X' be finite. An optimal MFC solution is probably approzimately optimal in the fonite N-agent system. Specifically, for any foiture probability 5 E (0, 1), there erists a constant C1 independent of N and such that for any N E N, the optimality gap is bounded by SVN with probability at least 1 6.
C2
Our theoretical results show that MFVRP is approximately optimal in large VRP. Moreover, the results are PAC-style guarantees which would give us exact probably-approximate optimality bounds for any fixed finite N-agent VRP instance in practice. The concrete constants can be computed inductively as in the proofs.
2.5 Generality and Limitations
The optimal MFC solution in Corollary 2.2 requires no additional assumptions because we may replace it by an optimal constant MFC policy, leading to deterministic T,. This works only for our MFVRP setting and not for general MFC, since we show that any optimal VRP objective is also obtained exactly in the limiting MFC by suitable MFC policy, see the third inequality in the proof of Corollary 2.2 The advantage of it is constant RL problem size regardless of number of agents / clients around each cluster.
Generality. Even for unit-capacity, MFC-based RL is well-justifeed by virtue of scaling to arbitrarily many agents. The sequential formulation can allow dynamic variants of VRP which are not addressed by standard VRP solvers, e.g., with random arrival of new missions, or stochastic failure of vehicles. MFVRP can further model heterogeneous vehicles, such as heterogeneous fleets with different capacities or speeds, by duplicating the state space for each separate type of vehicle. The methodology also applies to any metric space including non-Fuclidean such on graphs, in practice by using generalized clustering methods. Finally, in case of uncountable X, such as convex subset of IR,, transport maps T, are replacable by couplings on X x X, but the resulting MFVRP MDP is of infinite dimension. Instead, for algorithmic tractability, in the following we consider a discretization-bassee approach, with guarantees of near optimality for sufficiently fine discretization.
Limitations. We note that MFC is not without limitations for solving discrete optimization problems, which are discussed the following. In particular, MFC remains hard to apply for non-pickup-andddeliviil VRPs: First, the special case of multiple traveling salesmen problem (mTSP) under MFC would boil down to clustered version of standard m TSP, since distances between points in the same cluster are zero so they are immediately served by a single same agent. While this case can be considered, there is therefore no methodological novelty in applying MFC to TSPP beyond clustering all the locations and replacing them with their centroid. Meanwhile, constant finite capacities without pickup-and-delivery structure disappear in the limit of infinite agents, and are therefore also difficult to model. For scaling capacities, we obtain back a standard VRP with finite number of agents and not the RL problem we discuss. Further, time constraints are hard to model for MFC.
Beyond Unit Capacity. Lastly, a primary limitation of the current formulation is the focus unit-capacity vehicles. While this simplifies the state representation, it does not directly model many real-world scenarios. However, we can generalize the system to of agents to model picked-up objects, and generalizing transition matrices T, with additional probabilities of picking up objects with particular destination, i.e. the state space is exponential in the number of objects per vehicle. To generalize to a capacity of Cveh > 1, the agent's state space would need to be augmented to track the set of destinations for all carried objects. However, this would lead to a stato-action complexity that scales exponentially with Cyeh, posing significant challenge for the RL algorithm.
problems by exponentiating the state space
6

---

Published in Transactions on Machine Learning Research (09/2025)
For example, consider Cveh = 2. The new state space is X" XUUXXXXX X) with states X, or (x, t) (xxx)
defining agent at location x with an object to be transported to t. Then, the possible agent actions are:
1. Move to E X' and transport as many objects from æ to (including the carried object from ();
2. For an agent x E X: Move to X' while picking up an extra object for & from æ; or
3. For an agent at (z, E (X' x X): Move to while picking up an object for & from x.
Note that the option to pick two objects or model two carried objects is not useful, since agents transporting two objects by triangle inequality must go to one of the destinations for optimality, and lose at least one object at the end of their action. This keeps the persistent state space quadratic and not cubic. The mean-fiell state is thus a pair of distributions (ui: pp) over X' and X' x X' respectively. Let [nexx state/current state) be the policy. The evolution of the mean-field is:
(d) = Σ
(d(sss + (()dd empty moves to
sEX
delivers at d
(d4i(d,ta)
Σ
P ((d
ta) (((s,tt)
#EX
empty at e picks one for tas moves to d
carries one for ta at a, moves to
(s.d))T((d, ta)((s,d) d))
with lond d, picks up for tas delivers
with analogously defined resulting transitions for v and rewards. The last term in the second equation captures the complex action where vehicle at with a load for d picks up second object for ta and immediately travels to d to deliver the first, resulting in the new state (d, (a). As we can see, the dimensionality of the state space X' is squared, and the problem quickly becomes intractable. Analogous considerations hold for higher capacities.
3 Mean-Field Vehicle Routing RL
We present our algorithmic solution, visualized in Fig. ! The idea to solve the MFVRP as a single-agent MDP, via single-agent RL. At the same time, the implementation is multi-agent RL if we directly learn on the finite VRPs. Indeed, this gives two approaches of implementing algorithms for MFVRP. But first, we describe the clustering procedure required for general metric X' with theoretical error analysis.
3.1 Discretization and Clustering
For locations road network or graph, a finite state space X' suffices and avoid infinite-dimensional MFC state-actions, but in general this is not the case. Therefore, one can use Voronoi partitions to trade-off between accuracy of MF approximation and size of MFC problem. This is particularly useful when the objects and vehicles are clustered around a few most relevant locations such as cities, which are not located on a grid. Consider k E [K] cell centroids C₁ E X. Each centroid induces a cell C₁ = {a E X d(x, ((),.x)) e min, d(x, ej)] C X consisting all points in X' which are closest to that particular centroid out of all centroids. Then, minimize the error stemming from MFC approximation, we may use the empirical histogram with cells instead of bins, giving us the approximate MF fractions of objects to be delivered from one cell to another. As result, produce assignment p: M + [K]² such that each object i is assigned to the centroids closest to its source and destination location, p(i) E arg min, d(si, Ck) X arg min; d(d,, ct), where x denotes the Cartesian product. In practice, for simplicity we use k-means to produce a clustering of all source and destination locations, assigning each location to one of the clusters. In general one can use any clustering method, e.g., instead minimizing the non-squared Euclidean distances via k-medoids (Kuffan Rousseeuw 20083. See Fig. 2 for visualization.
We then bound the maximum error of the MFC approximation by the maximum sizes of each cluster.
7

---

Published in Transactions on Machine Learning Research (09/2025)
cluster 1
cluster
Discretized, limiting VRP
Clustering
Real VRP
Figure 2: Simplified overview of the clustering approach for Euclidean VRP in loy example. Observe the correspondence between limiting equations and real VRP, with clustering based discretization.
Theorem 3.1. An optimal discretized MFC solution is probably approzimately optimal in the original (non-discretized) finite N Naagent system. The optimality gap is composed of stochastic error from MF approzimation as in Corollary 2.2 and deterministic clustering error. Specifically, for any faiture probability E (0, 1), there exists consland C1 such that with probability at least - 5, the optimalily gap is bounded by
+ +4M + +2) max diam
NVN
Stochastäc Error
Discretisation Error
Our methodology is hence near-optimal whenever RL converges to an optimal MFC solution, for enough agents and good discretization. Note that time complexity becomes linear the number agents or objects N, M, because we only need to count how many are each bin. In contrast, complexity is shifted to quadratic in the number of clusters K. Thus, as shown the experiments, we achieve high scalability in N M.
3.2 Algorithm and Fine- Mine-Tuning
With the problem of general representation solved, RL solve the otherwise difficult-to-analle optimization or multi-agent control problem. The straightforward approach is to use the limiting equations and to define an environment, and apply single-agent policy gradients to the problem, see Alg.
Algorithm MFVRP-G
1: Input: Po, distance matrix.
2: for iterations n = 1,2,... do
3: for time steps t = 0, .., Bien do
4: Sample MFC action T. ~ 7 (Tr (e, v.).
Compute reward r(ue) and next MF' pc+1, Vi+1 as in Eqs. d+t1 1).
2
3
4
and termination reset flag
end for
7: Update # on minibatch sampled from data {((pe) M:), Te, deti, (e1)))
8: end for

---

Published in Transactions on Machine Learning Research (09/2025)
As discussed in Section 2.4 obtain valid VRP solution by sampling MARL actions for each vehicle, and performing postprocessing step where objects not delivered are appended to the route of some random vehicles. Preprocessing is performed via k-means with negligible run time of less than second per VRP instance, i..,, we assume the data is already clustered into clusters. Moreover, the depot appended as an addit ional cluster centroid at runtime. Whenever vehicle transports an object from cluster cluster j, we randomly iterate through vehicles and assign the nearest not yet transported object from to j, see Fig. 2
For learning general solution under fixed K, we dynamically generate wide range of scenarios by sampling initial object distributions and cluster centroids from flat Dirichlet and uniform distributions, respectively. This can be understood as pretraining on the space of all possible limiting MFVRP scenarios for given K, since we sample from all possible cluster locations and distributions over start and end locations. Alternatively, consider learning on a large fixed data set, e.g. if real data available and clustered.
Datascts Finc- Finc-Tuning Beyond learning a general policy, an improved approach to fine-tune on a specific, fixed VRP instance, using the general policy as warm start. We explore two ways to do this:
MFVRP-F (Mean-Field Fine-tuning): We continue training on the limiting MFVRP MDP, but use the fixed initial distributions (Ho.y)) derived from the specific VRP instance. This approach is fast as it operates entircly in the low-dimensional mean-field space.
MFVRP-FD (Finite-Domain Fine-tuning): We train directly on the finite N-vehicle problem. In each step, we sample actions for all N vehicles from the policy's transport map Tr, execute them in the environment, and update the policy based on empirical reward and state changes. This avoids mean-field approximation error during fine-tuning but is computationally more intensive.
However, we find that the latter gives similar results and takes too much time. We thus mainly focus on the former MFVRP-F method. Overall, the discussed approaches result in Algorithm The advantage of fino-tuning is possibly improved results, at the cost of training time.
The post-processing step for both methods involves assigning any leflover objects to random vehicles. We favor this simple approach because for large N, the fraction of undelivered objects is theoretically guaranteed to be small under an optimal policy, diminishing as consequence of our propagation of chaos result (Thcorem 2.4). We also performed an empirical verification in Appendix C.1
Algorithm MEVRP-E/FD
1: Input: MD), vO², distance matrix, pretrained MFVRP-G model.
2: for iterations n = 1,2,... do
3: for time steps f == O,..., Bien
do
4: Sample MFC action T. ~ * (T; [ee Mt).
(F): Compute reward r(4) and next MFs 1441, ves1 and flag de+1 E {0, 1} as in Alg. for specific VRP instance.
for vehicle = 1,...,, N do
7: (FD): Sample per-vehicle action vf Tr( xt).
8: end for
9: (FD): Perform actions, observe reward rt, next ME ptl,, termination flag de+1 E {0,1)
10: end for
11: Update # on minibatch sampled from data {((pe vi), Te, rt, dei1, 4411,1411 1+1)))
12: end for
In experiments, we consider datasets "finite", "uniform" and "citics". The former consists of finite state space |X'| = K, with distances from randomly sampled locations on [-1, 1J2. The latter takes the latitude and longitude of the 80 largest German cities and randomly samples cities, around which source and destination locations are normal distributed. For both of the above, we randomly sample joint distribution over source and destinations in []1, from a flat Dirichlet. Each object is then sampled from this joint distribution, and in the case of "cities" they are additionally perturbed around the location of the city. Lastly,

---

Published in Transactions on Machine Learning Research (09/2025)
for "uniform" sample source and destination locations uniformly at random from [-1, 1J2, which gives "worst-case" for clustering and MFVRP.
4 Numerical Experiments
In the following, we perform experimental evaluation of our algorithms on large problem instances. The implementation can be found in the supplementary materials.
4.1
Implementation Details
For the implementation, we use JAX with PPO (Schulman et al. 2017 based on PureJaxRL (Lu et al.
2022
We compare against three baselines: the Rools routing problem solver (Perron & Furnon 2023 the recent state-of-the-art PyVRP solver Wouda et al. (0024). and greedy heuristic.
OR-Tools: We use the standard routing solver, which automatically selects from portfolio of advanced heuristies and metaheuristics (e.g., guided local search, simulated anncaling).
PyVRP: A statc-of-tho-art open-source solver based on the powerful HGS algorithm. For both multiplied by 10t and rounded.
OR-Tools and PyVRP, we model the problem as CVRP with asymmetric distances (Eq.
This is heuristic corresponding to the 'PATH CHEAPEST ARC first. solution strategy in OR-Tools, where each vehicle iteratively travels to the start of the nearest available mission.
Greedy Heuristic:
We focus our comparison on these scalable, open-source baselines. Advanced commercial solvers were not included as they are proprictary. Similarly, we did not use standard public PDP benchmarks. While valuable, they typically feature smaller instance sizes (e-g., up to 100 nodes) or include problem aspects like precedence constraints which are beyond the scope of this foundational work, whose primary goal is to demonstrate new algorithmic paradigm for extreme-scale problems.
Each MFVRP-G model is a single policy trained to generalize across diverse problem instances for fixed number of clusters K. MFVRP-F then fino-tunes this general policy on one specific VRP instance. For our training, we used a GPU with 40 GB VRAM and over 19 TFLOPS of FP32 compute performance for a single hour for each fixed K in MFVRP-G (pretraining), and around two to three minutes per MFVRP-F MFVRP-FD run for a particular problem instance.
We learned policies with two hidden layers of 256 nodes and tanh activations. The discount factor is set to 0.99, and with GAE X = 0.95. The minibatch sizes are 10000 for MFVRP-F, as well as annealed from 10000 to 250000 for MFVRP-G, with 8 PPO steps per training batch. The clip parameter is set to 0.2. The learning rate was linearly annealed from 0.00003 down to zero. As usual in RL, our implementation uses discounted objectives and stationary time-independent policies (Guo al. 2022), and we also transform the current time into ooe-hot observation. Unless stated otherwise, we use the parameters K 5, R 5,
C - 15, Gд 50, Cmiss 30, Tbomus 5 and datasets for clustered and uniform scenarios with all locations in X x= [-, generated as described in the Appendix. We perform experiments on the aforementioned 3 types of datasets using the parameter K with 50 instances cach, to be able to assess the performance and generalization of our algorithms in different scenarios. For uniform datasets, in the following K is merely a hyperparameter of the algorithm.
4.2 Experimental Results
In Fig. g we show the training curves for the general MFVRP-G trained on K = 3 and K = 5. The curve is smooth as we chose a sufficiently high batch size (10000 to 250000), making gradient estimates less noisy. We observe that the methodology converges terms of episodic returns, and in turn that the maximization
CCode can be found under http://github. wwcchhubb.oom/eeee http://...o/tttuust//eeeee
10

---

Published in Transactions on Machine Learning Research (09/2023)
K
12.5
1.0
Episodic return
Mean distances
Frac. completed
0.8
335
10.0
0.6
30
7.5
(a)
(b)
0.4
(c)
5.0
0.5
1.0
1.5
0.5
1.0
1.5
0.5
1.0
1.3
Global timesteps
x10
Global timesteps
x10"
Global timesteps
x10
Figure 3: Training curves for MFVRP-G. Comparison of returns, travelled distances, and percentage of completed episodes for MFVRP-G.
of episodic returns indeed minimizes the travelled distances of vehicles while completing all episodes. The results reach a close to 100% completion rate of deliveries while optimizing the distances travelled. This verifies our reward function design.
We can also see that training takes longer as K increases, and uses great number of time steps, as common for RL methods. In particular, the batch sizes were chosen large to obtain stable training behavior, since the MFVRP MDP has the unique RL challenge of high-dimensional continuous action spaces. Nevertheless, we observe that RL begins to reduce the return and fraction of completed episodes when training for too long, and we apply early stopping.
Moreover, Fig. 4 contains the results for MFVRP-F with and without warm-starting from the pretrained solution of MFVRP-G. For the training steps seen in the figure, around minutes of GPU training time were used, see Tables and The pretrained solution provides significant increases in performance for the fine-tuned MFVRP-F solution, in contrast to cold-starting training on given VRP instance.
As result of the fast training time using a JAX-based learning implementation, approach is applicable even in time-critical scenarios despite the very large scale of vehicle routing problems, and therefore may prove ad vanaaageeuus over classical methods such as OR-Tools.
Table 1: Comparison and evaluation of VRP methods on various datasets, each consisting of 50 problems for each configuration (M, K). ) In the finite dataset, = [X], whereas in uniform it is a hyperparameter of our methods, and in cities it also the number of selected city locations. The confidence intervals for the objectives are in the range <
100, Gap
1000,
5000,
50000,
Method
Obj.
Time
Obj.
Gap
Time
Obj.
Gap
Time
Obj.
Gap
Time
Greedy
154.35
55.64 %
0.06s
1548.87
61.20 %
1.02
7715.41
58.73 %
5.52
73700.7
52.16 % 276.79
Piaite
OR-Tools
100.76
1.60 %
49.98
1056.95
9.99 %
300.00
5311.167
9.27 %
8001.01
PyVRP
99.17
180 03
960.86
180.53s
4860.81
192.88
MFVRP-G
107.78
8.68 %
5.09
1056.68
9.97 %
1
5250. 19
7,99 %
32.69
49692.9
2.59 % 502.47s
MPVRP-F
105.72
6.61
173.2
1030.66
7.26 %
1
5076.18
4.43 %
199.82
48438.2
788.39
Greedy
79.43
55.99 %
0.06
795.35
49.26
0.78%
3958.64
49.49 49 %
4.62
44404.7
49.83
278.56s
Citics
OR-Tools
50.92
60.00
532.91
300.00s
2647.775
8000.01
PyVRP
58.63
15.14 %.
180.02
576.70
8.22 %
181.022 02
2879.56
8.75 %
201. 001.64s
MFVRP-G
58.09
14.08 %
6.6
551.25
3.44 %
14.39
2721.67
2.79 %
34.45
30743.2
3.73%
523. 12
MFVRP-F
56.90
11.74 %
173.03
544.26
2.13 %
180.66s
2687.12
1.49 %
223.08
29635.9
775.41
Uniform
Greedy
217.76
73.09 %
0.06
2206.73
87.12%
11032.74
89.65
110313.7
72.30
275.73
OR-Tools
s
4.35 %
1.74 *
PyVRP
125.81
a
1179.32
180.638
5817.59
194.11s
MPVRP-G
164.99
31.14% %
4.92
1406.12
19.23 %
9.73
6648.92
14.29 %
31.77
64394.3
0.58%
494.12
MFVRP-F
164.71
30.92 %.
159.38
1406.39
19.26 %
172.63s
6633.06
14.02%% %
193.26
640024.5
727.07
11

---

Published in Transactions on Machine Learning Research (09/2025)
K pretrained
K ==3
pretrained
R =
50
1.0
Mean distances
Frac. completed
10.0
Episadic
0.5
35
(8)
5.0
(0
(c)
0.5
1.5
Global timesteps
=10
Global timesteps
x 100
Global timesteps
x10*
Figure 4: Training curves for MFVRP-F (single trial). Comparison of returns, travelled distances, episode lengths and percentage of completed episodes for MFVRP-F on particular VRP instance, for K 3, M 500 and K = 5, M = 1000.
Quantitative comparison of speed. In Table ! and Table 2 quantitatively compare the results of our approach against OR-Tools and PyVRP as strong practical basclines.
We observe that both the general MFVRP-G and our fine-tuned MFVRP-F (including training time) are faster than OR-Tools large scenarios, which was configured with maximum computation times to over 120 minutes for small and larger problem configurations respectively. Training was performed on GPU, but evaluation was performed without. For MFVRP-G G the time is the feedforward evaluation time on a standard CPU, whereas for MFVRP-F the times also include the training time on the GPU. Meanwhile, variation in training and postprocessing time taken, due to minor performance fluctuations. Both PyVRP and OR-Tools failed to produce any solution for M = 50000 within our time limit of more than 120 minutes. For the former, this is largely due to the pre-processing bottleneck of constructing the complete M x M distance matrix, a step with quadratic complexity that becomes intractable at this scale. Therefore, their results are omitled from the tables for this instance size.
have slight
Overall, we conclude that in terms of speed and scalability, the MF approach can be advantageous for very large scales. Morcover, would like to point out that most of the increase in time incrcasing M for MFVRP solutions is due to inelficient Python postprocessing code where objects (also leftover objects) are assigned to vehicles. This increase in time can be made significantly more efficient. We point out that MFVRP therefore scales to near-arbitrarily many vehicles if required, with speeds nearly matching simple heuristics.
Table 2: Comparison and evaluation of VRP methods for
5 as in Table
100,
1000, Gap
5000,
50000,
Method
Obj.
Gap
Time
Obj.
Time
Obj.
Gap
Time
Obj.
Gap
Time
Greedy
182.28
78.62 %
0.06s
1849.05
84.11
%
1.02s
9208.56
83.27 %
5,64
86675.4
68.63 % 258.47
Flaite
OR-Tools
113.00
10.73 %
57.12s
1174.35
16.93 %
300.00s
5978.828
18.99 %
8001.01
PyVRP
102.05
180.03
1001.32
180.49
5021.67
191.90s
MFVRP-G
130.91
28.28 %
s
1222.37
21.72%
14.99
6029.63 62
20.00 %
4
55017.1
7.03 %
507.06
MPVRP-F
128.68
26.10% %
215.68s
1172.54
16.75 %
217.8
5766.29
14.76 %
241.85
51401.0
859.22
Greedy
105.87
68.69 %
0.08
1064.14
74.58
0.76x
5333.94
75.25 %
4.32
51858.1
61.84
258.02
Citics
OR-Tools
64.70
3.09 %
60.00
670.29
9.97 %
300.00s
3326.19
9.29 %/
8000.01
PyVRP
62.76
180.02
609.53
180.66s
3043.34
198.39
MFVRP-G
79.61
26.84 %
1
729.45
19.67 %
3581.63
17.69 %
34455.7
7.53 5.53%
013.36
MFVRP-F
78.92
25.75 %
202.17g
731.32
19.98 % 207.97s
3563.57
17.09 %
228.8
32042.1
798.19
Uniform
Greedy
217.76
%
0.06
2206.73 73
11032.74
5.58
110313.7
72.28
262.77
OR-Tools
4.36 %
5919.67
1.74 *
PyVRP
125.81
180.02
1179.24
180.73
6818.09
194.29
MPVRP-G
171.04
35.95 %
9.64
1458.49
23.68 68
14.74
6836.91
17.51 %
43.35
66644.9
4.08 %
488.32
MFVRP-F
171.91 36.64 %.
190.95
1453.92
23.30
174.968
6759.07
16.17 %
192.39
64022.3
806. 69
12

---

Published in Transactions on Machine Learning Research (09/2025)
Quantitative comparison of objectives. As for the quality of objectives given by the total distance travelled by all vehicles, we find that MFVRP-F is usually better than MFVRP-G as result of fine-tuning on the particular VRP instance of interest. In a separate test, we verify that MFVRP-FD gives results in-between MFVRP-F and MFVRP-G (106.72 for M = 100, K = 3).
In comparison to baselines, we find that MEVRP usually outperforms simple heuristics but is behind OR-Tools and PyVRP in smaller-sized problem instances. A key question is why MFVRP, even with fine-tuning, is outperformed by solvers like PyVRP on smaller instances. The reason lies in the nature of our approximation. MFVRP optimizes discretized, mean-field version of the problem, which is accurate proxy only when the number of agents N is very large. For smaller N, 1. the stochasticity of the finite system causes the empirical distributions to deviate significantly from the smooth mean-field dynamics, an error that persists throughout the episode. Furthermore, 2. the clustering introduces a discretization error that is more impactful on shorter total routes found in smaller problems. In contrast, solvers like PyVRP use heuristics like HGS that perform sophisticated local scarch diroctly on the exact, discrete problem graph, which is highly effective at these scales. While fine-tuning MFVRP helps, it cannot fully bridge this fundamental gap between optimizing an approximate model versus searching the exact problem. We also empirically show the significance of the MF error for small-to-medium instances in Appendix C.1
Moreover, we attribute significant suboptimality to the limited efficiency of the RI. solution. In particular, we note that the RL solutions shown in Figure 3 are unstable, i.e the solution begins to deteriorate at a certain point and does not stay in a local optimum. Further work invested into reward shaping, hyperparameter tuning and neural network architecture may improve results further. This is supported by the limited RL performance for higher K seen in Appendix
As the size of problems increases however, the gap to the best method grows increasingly small. We also find that MFVRP can outperform OR- Tools and PyVRP under the right circumstances (M = 5000, "finite" and "cities" respectively). Moreover, the method scales automatically to arbitrary numbers of vehicles and objects, whereas OR-Tools and PyVRP take very long to produce results at very large scales. Moreover, we find that for M = 1000 and M 5000 in the finite dataset, our approach achieves an increase in performance over OR-Tools. This shows that a mean-field- bised methodology to optimization problems can in fact outperform more standard methods in the case of (a) accurate clustering ("finite" dataset), and (b) high numbers of vehicles.
Comparison between datasets. Comparing between different scenarios and parameters, we find an increasingly good approximation of the MFVRP solution as the number of vehicles and objects becomes large, M + 0o. In general, the gap between MFVRP and baseline performance becomes increasingly small or disappears as M increases.
Additionally, we can see that the suboptimality of MFVRP is strongly associated with the clusteredness of the dataset expected. In the "finite" dataset, we find significantly better comparative performance due to the finite space of locations |X'| = K, whereas in "citics" the sources and dostinations are scattered around the city centroids. Finally, in "uniform" we essentially have the worst-case for clustering-based approximations, with accordingly worse gaps in performance. To further improve the gap stemming from discretization however, we have to increase K, which in turn increases the hardness of the associated RL problem, since the action space of dimension K², Scaling up RL towards very high-dimensional continuous action spaces is difficult and left as future work, as our initial experiments with low-rank approximations of T, and higher K > in Appendix C.1 show (neither experiment is successful in achieving satisfactory performance).
5 Discussion and Conclusion
In this work, we have proposed a scalable RL methodology based on MFC for solving large-scale CVRP with pickup and delivery. The proposed methods were not only theoretically motivaled, but also empirically evaluated and compared against existing baselines as a proof of concept. While the general case with many clusters is yet difficult due the unique challenge of high-dimensional actions, the solution of particular cases remains useful. In particular, existing standard methods such as Tools may take too long to find solution for many vehicles and locations (see Table 2h, while our method provides a fast solution. While
13

---

Published in Transactions on Machine Learning Research (09/2025)
solving high-dimensional continuous RL such as the MFVRP remains difficult, still obtain RL complexities independent of the number of clients (or linear by sampling VRP solution and routes for each agent from the limiting solution, which is the minimal asymptotic complexity). Overall, we have investigated the applicability of mean-field methods to discrete optimization scttings and found that it is at the very least feasible.
At the same time, we have also seen the limitations in applying mean-field methods standard discrete optimization settings (e.g., Section 2.5 and experiments). In futture work, one could consider how to apply MFC-based solutions for general not-piikuup-nnd-delvery VRP and other hard combinatorial optimization problems. One could also scale up to more clusters, which is challenging due to the -i-dimensional action space. Promising directions for this include curriculum learning, energy-based actor-critic methods (Haarnoja et al. 2018), or using structured representations of the transport map Tı, such as low-rank factorizations. Further, it remains to be studied whether one can apply appropriate inductive biases via graph neural networks to generalize to any number of clusters. Finally, one may consider taking inspiration from related classical complexity reduction such as the fast multipole method (Rokhlin. 1985), or avoiding discretization altogether by suitable kernel-based parametrizations.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Acknowledgements
This research has been partially funded by the German Federal Ministry of Education and Research (BMBF) through grant 01IS23067 Software Campus 3.0 Technische Universität Darmstadt part of the Software Campus project 'RAAMFRP', and by the LOEWE initiative (Hesse, Germany) within the emergenCITY center. The authors acknowledge Lichtenberg high performance computer of the TU Darmstadt for providing computational facilities for the calculations for this research.
References
Andrea Angiuli, Jean- Pierre Fouque, and Mathieu Laurière. Unified reinforcement Q-learning for mean field game and control problems. Math. Control Signals Syst., 34(2):217-277 2022.
Andrea Angiuli, Jean-Pierre Fouque, Ruimeng Hu, and Alan Raydan. Deep reinforcement learning for infinite horizon mean field problems in contimuous spaces. vrXiu:2309.10553 2023.
Sundararajan Armapuram, Kamlesh Mathur, and Daniel Solow. Vehicle routing and scheduling with full truckloads. Transportation. Science, 3702)110--182, 2003.
Alain Bensoussan, Jens Frehse, Phillip Yam, et al. Mean field games and mean field type control theory. volume 101. Springer, 2013.
DD Bochtis and Claus G Sørensen. The vehicle routing problem in field logisties: Part I. Biosystems engineering, 104(4):447-457 2009.
DD Bochtis and Claus G Sørensen. The vehicle routing problem in field logistics: Part II. Biosystems engineering, 18810018888 2010.
Aigerim Bogyrbayeva, Meraryslan Meraliyev, Taukekhan Mustakhov, and Bissenbay Dauletbayev. Machine learning to solve vehicle routing problems: A survey. IEEE Trensactions on Intelligent Transportation Systems, 2024.
Andreas Bortfeldt and Junmin Yi. The split delivery vehicle routing problem with threo-dimensional loading constraints. European, Journal of Operational Research, 282(2):545-55) 2020.
14

---

Published in Transactions on Machine Learning Research (09/2025)
René Carmona, François Delarue, et al. Probabilistic theory of meon field games with opplications I-II. Springer, 2018.
René Carmona, Mathieu Laurière, and Zongjun Tan. Linear-quadratic mean-field reinforcement learning: convergence of policy gradient methods. arXio:1910.0429: 2019.
René Carmona, Mathieu Laurière, and Zongjun Tan. Model-free mean-field reinforcement learning: mean-field MDP and mean-field Q-eeanning Ann. Appl. Probub., 33(6B))53334 5381, 2023.
Jean-François Cordeau and Gilbert Laporte. The dial-a-ride problem: models and algorithms. Annals of Operations Research, 153:29-46, 2007.
Kai Cui, Anam Tahir, Mark Sinzger, and Heinz Koeppl. Discrete-time mean field control with environment states. In Proc. CDC, pp. 2239-52466 2021.
Kai Cui, Sascha Hauck, Christian Fabian, and Heinz Koeppl. Learning decentralized partially observable mean field control for artificial collective behavior. In Proc. ICLR, 2024.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andreoli. BQ-NCO: Bisimulation quotienting for efficient neural combinatorial optimization. In Proc. NeurIPS, volume 36, pp. 2023.
Massimo Fornasier and Francesco Solombrino. dean-field optimal control. ESAIM: Control, Optimisation and Calculus of Voriations, 20(4):1123-1152, 2014.
Zhang-Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize a small pre-trained model to arbitrarily large TSP instances. In Proceedings of the AAAI conference on artificial intelligence, volume 35, pp. 7474 7482, 2021.
Xin Guo, Anran Hu, and Junzi Zhang. Theoretical guarantees fictitious discount algorithms for episodic reinforcement learning and global convergence of policy gradient methods. In Proc. AAAI, volume 36, pp. 6774 6782, 2022.
Tuomas Haarnoja, Aurick Zhou, Picter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proc. ICML, pp. 1861-1870, 2018.
Sin C Ho, Wai Yuen Szeto, Yong-Hong Kuo, Janny MY Leung, Matthew Petering, and Terence WH Tou. A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 111:395-423 421, 2018.
Qingchun Hou, Jingwei Yang, Yiqiang Su, Xiaoqing Wang, and Yuming Deng. Generalize learned heuristics to solve large-scale vehicle routing problems in real-time. In Proc. ICLR, 2023.
Kuang Huang, Xu Chen, Xuan Di, and Qiang Du. Dynamic driving and routing games for autonomous vchicles on networks: A mcan field game approach. Transportation Research Part C: Emerying Technologies, 128:103189, 2021.
Yuan Jiang, Zhiguang Cao, Yaoxin Wu, Wen Song, and Jie Zhang. creemble-based deep reinforcement learning for vehicle routing problems under distribution shift. In Proc. NewrIPS, 2023.
Leonard Kaulman and Peter J. Rousseeuw. Partitioning Around Medoids (Program PAM), pp. 68 125. John Wiley & Sons, Inc., 2008. ISBN 9780470316501.
Daisuke Kikuta, Hiroki Ikeuchi, Kengo Tajiri, Yuta Toyama, Masaki Nakamura, and Yuusuke Nakano. Electric vehicle routing for emergency power supply with deep reinforcement learning. In Proc. AAMAS, pp. 2336 2338, 2024.
Grigorios D Konstantakopoulos, Sotiris Gayialis, and Evripidis P Kochagias. Vchicle routing problem and related algorithms for logistics distribution: literature review and classification. Operational Research, (3):2033 2062, 2022.
15

---

Published in Transactions on Machine Learning Research (09/2025)
Yeong-Dae Kwon, Jinho Choo, Iijoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Proc. NewrIPS, volume 34, pp. 1138-51499, 2021.
Jean-Michel Lasry and Pierre-Louis Lions. Mean field games. Jupanese J. Math, 2:229 260, 2007.
Kun Lei, Peng Guo, Yi Wang, Xiao Wu, and Wenchao Zhao. Solve routing problems with residual edge-graph attention neural network. Neurocomputing, 508:79-90 98, 2022.
Bingjie Li, Guohua Wu, Yongming He, Mingfeng Fan, and Witold Pedryez. An overview and experimental study of learning-basee based optimization algorithms for the vehicle routing problem. IEEE/CAA Journal of Automatica Sinica, 97)):1115 1138, 2022.
Jingwen Li, Liang Xin, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Heterogencons attentions for solving pickup and delivery problem via deep reinforcement learning. IEEE Transaclions on Intelligent Transportation Systems, 23(3):25 23(3)22306 2315, 2021a.
Sirui Li, Zhongxia Yan, and Cathy Wu. Learning to delegate for large-scale vehicle routing. In Proc. NewrIPS, volume 34, pp. 26198-26222 2021b.
Yeqian Lin, Wenquan Li, Feng Qiu, and He Xu. Research on optimization of vehicle routing problem for ride-sharing taxi. Procidia-Social and Behavioral Sciences, 43:494 502, 2012.
Qidong Liu, Chaoyue Liu, Shaoyao Niu, Cheng Long, Jie Zhang, and Mingliang Xu. 2D-Ptr: 2D array pointer network for solving the heterogeneous capacitated vehicle routing problem. In Proc. AAMAS, pp- 1238 1246, 2024.
Chris Lu, Jakub Kuba, Alistair Letcher, Luke Metz, Christian Schroeder de Witt, and Jakob Foerster. Discovered policy optimisation. In Proc. NewrIPS, volume 35, pp. 16455-16468, 2022.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Prec. NearIPS, volume 36, pp. 8845 8864, 2023.
Fu Luo, Xi Lin, Yaoxin Wu, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Qingfu Zhang. Boosting neural combinatorial optimization for large-scale vehicle routing problems. Proc. ICLR, 2025. URL
Yimeng Min, Yiwei Bai, and Carla P Gomes. Unsupervised learning for solving the travelling salesman problem. In Proc. NewrIPS, volume 36, 2024.
Santhanakrishnan Narayanan, Emmanouil Chaniotakis, and Constantinos Antoniou. Shared autonomous vehicle services: A comprehensive review. Transportation Research Part C: Emerging Technologies, 111: 255-293, 2020.
Laurent Perron and Vincent Furnon. optimization/
OR-Tools, 2023. URL http:://eereloprs.ggoole...
Jonathan Pirnay and Dominik G. Grimm. Seff-improvement for neural combinatorial optimization: Sample without replacement, but improvement. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinatorial optimization problems. In Proc. NewrIPS, volume 35, pp. 25531 25546, 2022.
Vladimir Rokhlin. Rapid solution of integral equations of classical potential theory. Journal of computational physics, 6022)1187-207 1985.
Naci Saldi, Tamer Basar, and Maxim Raginsky. Markov-Nash equilibria in mean-field games with discounted cost. SIAM J. Control Optim., 56(6):4256-422) 4287, 2018.
Filippo Santambrogio. Models and applications of optimal transport oconomics, traffic and urban planning. Xiv preprint
2010.
16

---

Published in Transactions on Machine Learning Research (09/2025)
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arxi 17700000774777 2017.
David Silver, Guy Lever, Nicolas Heess, Thomas Degris, Daan Wierstra, and Martin Riedmiller. Deterministic policy gradient algorithms. In Proc. ICML, pp. 387-395, 2014.
Jiwoo Son, Zhikai Zhao, Federico Berto, Chuanbo Hua, Changhyun Kwon, and Jinkyoo Park. Neural combinatorial optimization for real-world routing. arXiv preprint arXiv:2503.16159, 2025.
Zhiqing Sun and Yiming Yang. Difusco: Graph-based diffusion solvers for combinatorial optimization. In Proc. NewrlPS, volume 36, pp. 3706 3731, 2023.
Aad W Van der Vaart. Asymptotic Statistics, volume 3. Cambridge University Press, 2000.
Yong Wang, Qin Li, Xiangyang Guan, Jianxin Fan, Maozeng Xu, and Haizhong Wang. Collaborative multi- depot pickup and delivery vehicle routing problem with split loads and time windows. Knowledge- Based Systems, 231:107412, 2021.
Niels A. Wouda, Leon Lan, and Wouter Kool. PyVRP: high-performance VRP solver package. INFORMS Journal on Computing, 36(4):943 955, 2024.
Yaoxin Wu, Mingfeng Fan, Zhiguang Cao, Ruobin Gao, Yaqing Hou, and Guillaume Sartoretti. Collaborative deep reinforcement learning for solving multi-objective vehicle routing problems. In Proc. AAMAS, pp. 1956-1965, 2024.
Yifan Xia, Xianliang Yang, Zichuan Liu, Zhihao Liu, Lei Song, and Jiang Bian. Position: Rethinking post-hoc scarch-based neural approaches for solving large-scale traveling salesman problems. In Proc. ICML, pp. 54178-54190, 2024.
Yubin Xiao, Di Wang, Boyang Li, Miugzhao Wang, Xuan Wu, Changliang Zhou, and You Zhou. Distilling autoregressive models to obtain heg-ppeforrmanc non-autoregressive solvers for vehicle routing problems with faster inference speed. In Proc. AAAI, volume 38, pp. 20274-20283, 2024.
Haifei Zhang, Hongwei Ge, Jinlong Yang, and Yubing Tong. Review of vehicle routing problems: Models, classification and solving algorithms. Archives of Computational Methods in Engineering, pp. 27, 2022.
Kenan Zhang and John Lygeros. Routing and charging game in ride-hailing service with electric vehicles. In Proc. CDC, pp. 3116-3121, 2023.
Zhi Zheng, Shunyu Yao, Zhenkun Wang, Tong Xialiang, Mingxuan Yuan, and Ke Tang. DPN: Decoupling partition and navigation for neural solvers of min-max vehicle routing problems. In Proc. ICML, pp. 61559-6141 61592, 2024.
Jianan Zhou, Zhiguang Cao, Yaoxin Wu, Wen Song, Yining Ma, Jie Zhang, and Xu Chi. MVMoE: Multi-task vehicle routing solver with ofxture-of-expeets. In Proc. 1CML, pp. 61804 61824, 2024.
Zefang Zong, Meng Zheng, Yong Li, and Depeng Jin. MAPDP: Cooperative multi-agent reinforcement learning to solve pickup and delivery problems. Proc. AAAI, volume 36, pp. 9980 9988, 2022.
17

---

Published in Transactions on Machine Learning Research (09/2025)
A
Dataset Details
In this study, we generate 3 different types of datasets, called uniform, finite and cities. For each type of dataset we vary the amount of objects to be delivered M {100, 1000, 5000, 50000), and for the finite and cities distribution
also vary the amount of clusters, K E {3.
The positions of the K clusters in finite are sampled uniformly from [-1,1]². Meanwhile, in cities we sample the positions from a list of rescaled longitudes and latitudes of the 80 most populated German cities. The rescaling performed by subtracting the mean longitude and latitude (51,10) and dividing by 5. The source and destination cluster assignments are sampled from a flat Dirichlet distribution. The exact position of the M largets and sources then sampled from Gaussian distribution around the positions of one of the corresponding K clusters, with standard deviation of 0 and 0.02 for finite and cities respectively, with samples clipped between -1 and 1. For the latter, this standard deviation of 0.02 corresponds to city radius (95% of samples inside) of 16 km.
For the uniform dataset we sample M sources and destinations uniformly from [-1, We generate 50 instances for each combination of M and k, resulting 200 VRP instances for uniform, and 400 VRP instances for cities and finite.
B Proofs
B.1
Mean- Faan- Convergence
Proof of Theorem 2.1 First, note that with deterministic á comes constant, (non-random) T. output over all Pe, Vt. Indeed, even constant MFC policies are sufficient due the deterministic evolution of pr, vr given the initial state, and are equivalent to any trained RL policy क for the limiting MFC problem with open-loop control sequence To, T1, .2..... We therefore use equivalent optimal, but constant MFC policy (.()))--) = δτ. Therefore, T; is no longer random and entirely deterministic.
The statement is shown inductively by convergence in expectation, E [[lua" - -ell O(1/VN) - 0 and E |||e"N = = OIIvVN) immediate by weak law of large numbers (LLN). Assuming the statement at time i, then at time + 1, as a short sketch, we obtain
Convergence in probability then follows. At time t 0, the statement is
E [llK [1t1llo]]
ΣE
E
Σ
(s)tt)
1 Σ (s)))
N
N IEN
xEx
+ E
(s) - Σ (s)T
N
=EX
ESN
and can apply induction assumption for the latter term, and a weak LLN argument for the former. The same holds for vy Vt.
More precisely, for the analysis, we lift the actions to a new action space X (Carmona et al, 2018 and note the equivalence in distribution the original MARL system by using ni.,. whenever vehicle is in state
x. Then, we may apply the discussed constant MFC policies by sampling wf,, Te(x,.) for all x e X' and using the corresponding component, instcad of uf ~ Te( -). The advantage in analysis that ut,, is i.d.d for all i, x. Then, v/Ni (s,d) d) is given by subtracting from vi (s, d) the random variables 11 =d for each of E W vehicles, up to at most N Ru many.
The proof proceeds the above system where the actions are i.i.d., and the results follow for the original system by equivalence in distribution of both systems for the two following lemmas.
The overall result is then obtained two steps, which are shown in App. B.2 and B.3
18

---

Published in Transactions on Machine Learning Research (09/2025)
Lemma B.1 (Propagation of Chaos I). Consider finite X, tmax oc and determánistic ft For each S tmax
08 N + 00,
E Illu - pelloo - OL1/VN) + 0.
Lemma B.2 (Propagation of Chaos IT). Consider finite X, mmax < oo and deterministic a. For each S bmax;
as N + -0,
E [l
rellso] O(1/VN) +0
From the above lemmas, the proof of Theorem
follows: The desired statement shown inductively 2.1
by convergence in expectation, E |||,,* pellso| O(1/VN) + 0 and E |2 1/ v/llo0 O(1/VN) 0 by
Lemmas B. and B.2. Convergence in probability then follows by Van der Vaart 2000
Theorem 2.7) and
deterministic Me,
B.2 Propagation of Chaos
Proof of Lemma B.1 For the analysis, we lift the actions to new action space x2 (Carmona et al. 2018 and note the equivalence in distribution to the original MARL system, as discussed in B.1 We prove the statement via induction over t. For I == O, the statement follows from a law of large numbers argument (see induction step below, first term). Thus, remains to show the induction step using the induction assumption (IA). Assume that the equation holds at time l. Then, at time L+ have
E [1lit1 Mc41lloo] = E max mnaxluita(es (())
xEet
<
IE
Σ
M (xt) Met1(z))
Σ E ((c+ (x)1
Loe
SEX
1
Σ ZEX
E
Σ
(s)())(())))
Σ Em((s)Ta(s5aO)
N
Σ E
1/1 Σ
1
Σ
0z (x)
1 +EΣ+ 6nf (s) SEXiSN
N
N
ZEX
MEA SEAiSN
+
ΣΣ
8 (x)())
Σ (1(
N
SEN
EE
< Σ E
Σ
Sef (s)
ΣΣ SEXISN
8 (s)T((())
N
N
ZEX
NEXiSN
iSN
+ E
N
82 (s)(TE(())
Σ
(s)
SEXiSN
SEX
1 Σ
Σ
E
Σ<
x
(s)
Σ
E
x
N
ZEX
NEA
iSN
+
Σ
T((8,2)
[m((8)-
Σ
on (8)
BE
27 1/2
E
N2
Σ
(1( -
vx(x))
,
27
N
+
Σ
T((,,))
(r(s)
N
ZEX
iSN
20(1/VN)
19

---

Published in Transactions on Machine Learning Research (09/2025)
1/2
u1(()) 2 2 xx ))
Σ
N2 E
uf(x)
+ OL(/VN)
ZEX
O(1/V\),
VN
which concludes the proof.
B.3 Propagation of Chaos
Proof of Lemma B.2 For the analysis, we lift the actions to new action space x2 (Carmona et al. 2018 and note the equivalence in distribution the original MARL system, as discussed in [. As before, we prove the Lemma via induction over and note that the induction start & = holds by law of large numbers argument (alternatively, see induction step below). Now, the induction step is provided by the following argument, where we assume that the statement holds for t:
[1 - 10-16 =E
max Mit (s, d) (s-1(s,)) s.dEA
E
Σ x,dex
(s, -Ve-1(s,d)
Σ e,dEx
E (5, (s,
Σ E
max V (
1
Σ
dag (s)
max (sss)T((s,dd//
(5)
RN
s,d.
I
=<v
For the next argument, fix some arbitrary tuple (s,d) E X²2 For the moment, focus
E
M (s,
Σ (s)( (v)(s, ((s))((s)))))
RN
s
1 d() R pe(s)TT(ss
1 N
Σ (s O(I/VN)) ISN
where the first summand converges to zero by the induction assumption and the second sunmand converges to zero by an argument in the proof of Theorem B.1 The above result implics convergence of equation to zero because for each arbitrary but fixed tuple (s,d) X and any N N we have
|0a Ix) max(0, m) s IN - IT]
To see that the inequality is true, make case distinction. If both Iy and II are non neg-negative, the statement trivially holds. If both In and II are negative, the left side of the inequality is and thereby the inequality is obviously fulfilled since there is absolute value the right side. Finally, in the third case, assume that In is non-negative and II is negative (or vice versa). In the third case, the left side equals Iy while the right side equals IN - 11 > Iy since 1I is negative, This completes the proof of Theorem B.2
B.4 Approximate Optimality with High Probability
Proof of Corollary 2.2 The proof idea is to compare the objectives (sums of expected rewards) of the respective policies and systems, and thereby establish the following sequence of inequalities for objectives, for any holding at least with probability 1 1-8,
(2) MARL (1) MFC A 2
(3) >
MFC - A A2
MARI -A A2
20

---

Published in Transactions on Machine Learning Research (09/2025)
with A = O SVN and 2 = :0=00
(VN) where MARL denotes the objective of the sampled MARL solution, MARL" is the optimal MARL objective, MFC" is the MFC solution's objective from which the MARL solution is sampled, and MFC is the optimal MFC objective with starting conditions matching the empirical sampled VRP instance 10 I.
Term 1. Consider an optimal MFC solution where the corresponding objective value is denoted by MFC* in the above inequality sequence. By Theorem 2.1 the probability any positive fraction of objects Frem Es.d Vi tmax (s.d) d) 0 remaining (more than in the MFVRP) after termination time mmax of the MEVRP MDP being larger than some
P (Frem 2 =)== IP
Σ Umax (5,
Σ
Vlmas (s,d)
ZE
S IE
taaa (8,
Σ s,d
Viman (8,
1
8
by Markov inequality. From Theorem 2.1
E El N Mellool I C.VVN and Bilby - vs villool S D./VN. Let
Cmax max + Dz). Then the expected difference bounded:
Ciax
E
Σ s,d
Funas (s,
Σ s.d
Uemar (0, d)
Lr
|
VN
Letting the probability of remaining objects be at most & and solving for e, we have
4T,, Cmax X12
JvN
as an optimal MFC solution transports all objects in the limit, Esdd Vimaa (s (s.d)=0)
Similarly, by Theorem 2.1 the MARL trajectories rewards close to the MFC rewards up to time fmax with high probability,
mmx Cmax
P
Σ fSttmix
2E
2
S E
Σ
EVN N
I Emnx
Again, letting the right-hand side be at most & we get
4tmax Cmax
JvN
Let the former event be A (%rom 2 E), and the latter = 1={(Ec Eistama - Yi 2 e). Overall,
therefore P(A^ B) 2 1 - 4. Moreover, A ^ B jointly implies that a sampled solution's 's return is approximately given by the optimal MFC solution's return up to a difference
Cmax 8/N
41max Cmax
A =
-2 diaim
SVN
since each remaining object takes at most 2 diam((') to transport, and thus establishes the first inequality (1).
Term 3. To prove the third incquality (3), note that the return of any optimal MARL solution can also be exactly obtained in MFC system with modified initial distributions, by using vg n starting values
21

---

Published in Transactions on Machine Learning Research (09/2025)
instead of Po: Po- Letting d) E 2ntuiaaa obtains exactly the optimal MARL objective in the 2, 1,(1)
modified MFC system denoted as MFC" in the above inequality sequence. Therefore, the optimal MARL
objective bounded by the optimal modified MFC objective which corresponds to inequality (3).
Term 2. Finally, it remains to establish inoquality (2). We point out that the optimal MFC objective is Lipschitz continuous in its starting conditions, since Eqs. 2 are Lipschitz continuous. Let L be
the corresponding Lipschitz constant. Then
(L - polloo + 11:/ - vollo)) =
1
X 1 8
s E ( - nollso + 1110 - ]ooloo)]
LJ
and letting the probability not exceed probability 5. we get e between optimal modified MFC objective (with changed starting conditions) and the optimal MFC objective
4
OVN This implies that we have a bound
X
D
8VN
which yields incquality (2)-
Therefore, putting the results logether, the probability that the sampled MARL solution is (Ai + A2)-optimal in the MARL system also is at least 1-d.
B.5 Approximate Optimality under Fine Discretization
Proof of Theorem 3.1
The proof structure consists establishing the following five inequalities of objectives
as in Corollary 2.2
MARL > 8-MARL E
-2 2 8-MARL" A - A2 2 MARL 2 - -A- - A2.
MFC 2
First, obtain the center inequality sequence
8-MARL e' MFC -'' - 2 -F A2 2 &-MARL' -1
by the same argument as in the proof of Corollary 2.2 where 5-MARL refers to the discretized VRP problem.
Therefore, remains to establish the first and last inequality of the initial inequality sequence. These two incqualities intuitively build on the obscrvation that the discretized 6-MARL system close to the initial, continuous MARL system. Formally, we know that each of the M objects 'cause' most two vehicle moves: one be picked up and one be delivered to the destination. In the worst case, all N vehicles have additionally fly back to their respective depots, which upper bounds the total number of travels by 2M + N.
By the triangle inequality, max, diam((k) from the respective travel in the continuous system. Consequently, the overall sum of deviations, and therefore the deviation of objective in the systems, is upper bounded by s' = 2 (2M + N) max; dCam(Ck). This argument holds uniformly for all solutions and hence establishes
then know that each travel in the discretized system deviates at most
MARL 2 6-MARL- 9' and 5-MARL* > MARL* -
and thereby concludes the proof.
C Additional Experiments
In this section, we perform additional experiments on low-rank approximations to reduce the complexity of the RL problem, well as run for higher K.
22

---

Published in Transactions on Machine Learning Research (09/2025)
C.1 Low-Rank Approximation
In Fig- can see the results for low-rank approximation of Tr, where essentially reduce the dimensionality of action space from Y² to K using rank-1 approximation. Essentially, each column of T; is the same, because Tę is row stochastic and therefore rows are normalized. As can be seen from the figure, the rank-1 approximation is insufficiently expressive and greatly reduces the achieved objectives and distances travelled in comparison to the full-rank version.
C.2 Tests on higher
In Fig. 5 we can see the results for higher K. can be seen that the RL algorithms do not converge to good solutions. We used the exact same settings and implementation as for = and K = This demonstrates the scalability challenge posed by the K dimdimnnsiln action space. High-dimensional contimtous-action RL still remains very challenging, and this constitutes limitation of our work.
C.3 Fractions leftover objects
As can be seen in Fig. 7 the number of leftover objects at the end of executing the limiting MF actions the corresponding finite VRPs are significant for smaller N, but quickly tend to zero for sufficiently large N. This implies that the heuristic for handling any leftover objects may play an important role for suboptimal performance of MFVRP in smaller instances, but its choice is not important for sufficiently large VRP instances.
C.4 Expected error between empirical and limiting MF
that the expected Lı error between the limiting MF and the empirical MF starts at zero at decision epoch zero, since all agents start at the depot and the MF of objects is initialized from the finite problem. After executing a few sampled actions in decision epochs however, we find that the MFs of the limiting system and the sampled MFVRP system will diverge, less so the larger the VRP instance is. It can also be seen that the deviations still remain of significant. order (more than a few percent) unless the number of agents is significant (e.g., 1000). We can hence see that MFVRP obtains potentially significant suboptimality from its approximation error, unless the VRP instances are of sufficient size.
In Fig.
K=3
K=5
Mean distances
Frac. completed
35
12
Episodic
30
10
(a)
(b)
0.5
(c)
25
8
0.5
1.0
1.5
0.5
1.0
1.5
0.5
1.0
1.5
Global timesteps t
1e10
Global timesteps
1e10
Global timesteps
1e10
Figure 5: Training curves for MFVRP-G as in Fig. the dimensionality of action space from K2 to K.
but using rank-1 approximation for Tr, i.e. reducing
K=
Episodic return
Mean distances
14
Frac. completed
0.3
26
24
(a)
10
(c)
2
Global timesteps
1e9
Global timesteps
1e9
Global timesteps
1e9
Figure 6: Training curves for MFVRP-G as in Fig. but for higher K.
23

---

Published in Transactions on Machine Learning Research (09/2025)
0.25
k=3
0.20
0.15
0.30
101
10
10a
agents (log)
km5
0.3
Lettover traction
0.2
0.1
10a
10
Num agents N (log)
Figure 7: Expected fraction of leftover objects over the size the sampled VRP problem, together with 95% confidence interval over a total of trials.
N-200
us Sgtntts
N-50
N-1000
0.3
0.6
N=200
LINMF Rintee
N=30
N=1000
0.7
0.0
0.0
10
12
10
Time
Figure 8: Expected Lı error between limiting and empirical MF, with 95% confidence over 50 trials. (Left: MF of agents; Right: MF of objects; last value extended to longest trial if lengths mismatch)
24


Reviews:
[{"review_id": "N1Zoem6AGU", "reviewer": "Reviewer_vDEa", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper seeks to tackle very large scale unit-capacity pickup-and-delivery routing by casting the many-vehicle system into a mean-field formulation. The idea is to track distributions of trucks and package source-destination pairs instead of tracking every truck and package, thus turning a multi-agent problem into a single-agent MDP whose action is a transport map over a clustered discretization of space. The proposed approach then applies RL on this mean-field MDP. The paper also provides asymptotic guarantees and a discretization error bound from clustering. Overall, I find this work interesting, and the results seem quite convincing, demonstrating that the proposed mean-field approach is much faster than OR-Tools/PyVRP at very large scales. I find the work interesting and promising, but I have several reservations (evaluation scope, baseline coverage, and some clarity issues) which I believe should be addressed before publication.", "claims_and_evidence_yn": "Yes", "claims_explanation": "Most of the claims seem correct with few exceptions as detailed in the other parts of my review.", "audience_yn": "Yes", "audience_explanation": "Overall, I find this paper's idea and results interesting and I believe after a revision (there are some inconsistencies and discrepancies) it can contribute to the scientific community in general and to TMLR's audience in particular.", "requested_changes": "I have several questions, concerns and suggestions as elaborated below.\n\nConcerns:\n\n1. First and foremost, the title mentions VRP, but the studied problem is not the classic VRP. I would suggest the authors to revise the title to correctly reflect this paper's scope and contributions. For example, something along the lines \" A Mean-Field RL for Large-Scale Unit-Capacity Pickup-and-Delivery Problems.\"\n\n2. In section 2.2 it is stated that the constant c_d > 2/M diam(X), but in the following section the authors state that they chose c to be 2 diam(X), is this a typo or an oversight ?\n\n3. In section 1.2, it is stated that several prior works allow sub-minute training times, which is also met in this paper. However, the reported results in section 4.1 state that fine-tuning takes around 3 minutes per instance and pre-training takes roughly 1 hour per K. This should be clarified and the language should be adjusted.\n\n4. The scope of the evaluation is limited to synthetic data generated by the authors. In the \"Related Works\" section, several PDP papers are cited. Incorporating the datasets employed/generated in those works (or public PDP datasets) into the current evaluation not only would provide external validity to this work but will also allow for direct apples-to-apples comparisons with prior works. Furthermore, this will also facilitate future works' comparison with the results reported in this paper.\n\n5. On a related note, the current set of benchmarks omits learning-based approaches from prior work. This weakens the empirical positioning of the contribution: it remains unclear how the proposed method compares to existing neural/learning-based VRP solvers reviewed in the Related Work section. Please either (i) include representative learning baselines, or (ii) provide a clear rationale for their exclusion, and discuss how those factors affect comparability. \n\nQuestions:\n\n1. T_t grows quadratically with K. Have the authors considered any methods to reduce action dimension (e.g., low rank factorization ) ?\n\n2. Have the authors considered post-processing steps other than delivering leftovers randomly ?\n\nSuggestions:\n\n1. The paper’s structure, especially the Introduction, can be made clearer. I recommend (i) stating the precise problem variant early (unit-capacity PDP, no time windows, tour-length cap), (ii) briefly explaining the link to CVRP used for baselines, and then (iii) introducing the mean-field perspective and contributions. This would anchor the reader before the methodological details and make the scope unambiguous.", "broader_impact_concerns": "N/A", "additional_comments": "Minor comments:\n\n1. For example, (Zhou et al., 2024) considers -> For example, (Zhou et al., 2024) consider. This grammatical error is throughout the paper, please correct all the instances. \n2. Proofs for theoretical results may be found in the Appendix- > can be found\n3. Examplary system with four states -> Exemplary \n4. As a finite problem of interest, one may consider vehicle routing problems with pickup and delivery -> this sentence reads super awkward to me and is not clear what the authors meant.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RCDAlfYG6Z", "reviewer": "Reviewer_5UMp", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel method for the (capacitated) Vehicular Routing Problem (VRP) by first showcasing the mean-field limiting solution and then discretizing it back down into the combinatorial domain. They showcase state-of-the-art performance compared to existing baselines.", "claims_and_evidence_yn": "Yes", "claims_explanation": "The work is well motivated by first looking at the distributional mean-field limit and then “projecting” onto a finite space. The work is generally clear and the figures are appropriate for showing the general idea.\n\nLooking at equation 2-3: Is this connected to an optimal transport (Wasserstein) flow? This somewhat looks like a continuity equation (2) and a transport map (3). There is probably some connection since your method ultimately estimates a pushforward (3) and a continuity term: ignoring positivity: $\\nu_{t+1}(s,d) - \\nu_t(s,d) = - \\mu_t(s) T_t(s,d)$. If we don’t have mass-flow we get $\\partial_t\\nu_t(s,d) = -\\mu_t(s) T_t(s,d)$, i.e. continuity with a sink $-\\mu_t(s)T_t(s,d)$. As such I think it would be appropriate to cite existing work on OT+VRP like Santambrogio (https://arxiv.org/abs/1009.3857) or Huang (https://arxiv.org/abs/2012.08388), both of which use essentially the dynamic Benamou-Brenier OT formulation.\n\nThis is more of a remark, but I don’t quite understand the utility of the theorems/corollaries (2.1, 2.2, 3.1): Usually propagation of chaos is used to establish a link between a finite nonparametric Mean-Field estimate (i.e. approximating p(x) via N bins) and the true distribution p(x). This means that N is a free parameter one can alter to improve the approximation: If I want a certain $\\varepsilon-\\delta$ bound I can set $N$ high enough. However, here the N corresponds to the number of vehicles/objects, so it is not a free parameter. If I’m given a specific realization of a VRP, then the $N$ is fixed, so in some sense the guarantee should  be the other way around (given $N$, you prove $\\varepsilon,\\delta$). From everything I know about MFC, the $N$ one might need for decent approximation is huge.\n\nA strength of this paper is the good delineation of the paper’s limitations: Capacities>1 is exponential, non-pickup-delivery VRPs are not really modellable.\nI think you should strengthen your explanation of MFVRP-F vs MFVRP-FD: I think the distinction is that in MFVRP-F you just update the distributions themselves, while in MFVRP-FD you sample the discrete actions and update the distributions with those, but this is not entirely clear.\nIn Algorithm 2, line 5: Should this reference Algorithm 1 rather than Algorithm 2?\nRegarding the results in table 1: Is this one policy (pre-)trained for all settings (uniform, cities, finite) or one policy per setting (i.e. one for uniform, one for cities, one for finite)?\nThis is somewhat important since if every setting needs one model, the pretraining time might dominate in the real world. In fact, an interesting benchmark to consider is what happens if one model was trained on e.g. uniform (and only uniform) and evaluated on e.g. cities. This would showcase on what level optimization performance hinges on pretraining performance.\n\nWhat happens if K is larger than 5? Does the method still work? Having just 3-5 clusters is really limiting in practice.\n\nWhy is c_miss and r_bonus needed? Shouldn’t the choice of c_d remove the local optima?\n\nOn page 8 “For learning a general solution under fixed K, we dynamically generate every possible scenario by sampling $\\nu_0$ and cluster centroids randomly according to flat Dirichlet and uniform distributions respectively”: should this be “any” scenario? I doubt that you can generate every scenario.", "audience_yn": "Yes", "audience_explanation": "In general the application of mean-field limit approaches for combinatorial problems is interesting for large scale optimization.", "requested_changes": "Test larger problems beyond K=5\n\nClarify the connection of this to existing classical OT-VRP approaches (see above).\n\nClarify the utility of theorems/corollaries (2.1, 2.2, 3.1).", "broader_impact_concerns": "No broader impact concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SXthIjhebt", "reviewer": "Reviewer_NtR6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work proposes to combine mean field control and reinforcement learning to handle large-scale vehicle routing problems.\n\n### Strengths:\n- The introduction of mean field control for vehicle routing problems (VRPs) is a novel and interesting approach, particularly for large-scale scenarios.\n\n### Weaknesses:\n - Performance Concerns: The proposed algorithm underperforms baseline methods (e.g., OR-Tools, PyVRP) on small and mid-sized VRPs. While it scales to 50,000-node problems, the solution quality remains unclear—outperforming a naive greedy heuristic is insufficient to demonstrate superiority. Alternative baselines like Hexaly should be considered for a more rigorous comparison.\n\n - Overly Simplified Assumptions: The assumption of single-capacity vehicles (\"carrying capacity of one object\") significantly weakens the model’s applicability, as it ignores a key feature of VRPs: multi-pickup/delivery scenarios.\n\n  - Questionable Practical Relevance: Mean field control relies on a large number of agents (vehicles), yet real-world VRPs typically involve limited fleets. The authors should justify this choice with a motivating example or application where such scalability is realistic and necessary.", "claims_and_evidence_yn": "No", "claims_explanation": "See the weakness part.", "audience_yn": "Yes", "audience_explanation": "Novel methods for VRPs are worth studying.", "requested_changes": "1. **Baseline Specification**  \n   - The authors use \"OR-Tools\" as a baseline without specifying which specific algorithm(s) were employed. Given OR-Tools' diverse algorithmic offerings, this omission affects reproducibility. \n\n2. **Benchmark Enhancement**  \n   - The evaluation would benefit from including standard **VRP with Pickup and Delivery (VRPPD)** benchmarks, particularly:\n     - https://neo.lcc.uma.es/vrp/vrp-instances/vehicle-routing-problem-with-pick-up-and-deliveries/\n   - These would better validate the method's handling of precedence constraints and mixed load scenarios.\n\n3. **Comparative Analysis**  \n   The baseline comparison should be expanded to include:\n   - **Commercial Solvers**:\n     - [Hexaly](https://www.hexaly.com/) (notable for its optimization speed)\n     - NVIDIA's [cuOpt](https://docs.nvidia.com/cuopt/) (for GPU-accelerated routing)\n   - **Learning-Based Methods**: All relevant RL/learning approaches cited in the paper", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)