1 · The input
Depot, coordinates, demands
The number in each point is that customer’s demand. Total demand is 30, so at least three vehicles are required. Any pair of points is a legal drive.
← → · F fullscreen
Overview
BP-MDS
Million-scale approximate CVRP in minutes —
parallel divide-and-conquer.
Angular buckets around the depot. MST and randomized DFS on each core. Five million customers in eight minutes.
Chekkala Sandeep Reddy
IIT Madras
Primary contact
Lakshya Rani P
IIT Madras
Somesh Singh
Siemens EDA, France
Rajesh Pandian Muniasamy
Qualcomm, Bangalore
Rupesh Nasre
IIT Madras
on Parallel Processing 2026 · Singapore
The problem
CVRP, in one picture.
Identical vehicles leave a depot, serve every customer once, and return. Each vehicle holds at most Q. A drive costs the straight-line distance, and the objective is the total length.
2 · Rejected
Visited everyone, broke capacity
Gray routes are fine (loads 7 and 10). The red route carries 6 + 4 + 3 = 13. One overfilled vehicle makes the whole solution illegal.
3 · Feasible
Same customers, loads fit
Move the demand-3 customer onto the left route. Each route now sums to 10, starts at the depot, and returns. Among such routings, CVRP wants the shortest.
Closed at the depotEvery route starts and ends at the depot. Vehicles are identical, and the fleet is large enough to serve everyone.
Load at most QDemands on a route sum to at most Q. Each demand is positive and itself at most Q. The depot has demand 0.
Each customer onceEvery customer lies on exactly one route. A demand is served whole: it is never split across vehicles.
Shortest total lengthEdge cost is Euclidean distance. The sum over routes is NP-hard to minimize, so city scale needs approximation.
Motivation
What makes million-scale a different problem.
A local warehouse is a few thousand customers. Planning across cities is millions. The best city routes radiate from the depot, and a full distance matrix is far larger than the machine.
Routes already form a flower.
Best-known routes for Brussels put the depot at the center and each route on a petal. A cone of width α follows one petal. Cones share the depot, so each cone is a smaller CVRP that can run on its own cores.
How far current methods reach.
~10²–10³
Exact methods, savings, sweep
Strong on warehouse-sized benchmarks. Impractical once the instance leaves that range.
a few 10³
HGS-CVRP
Near-best gaps on a few thousand customers. Built for quality, and too heavy past that.
~5×10⁴
ParMDS
Same MST and randomized DFS idea. Runs out of memory near fifty thousand customers.
5×10⁶
BP-MDS — this paper
Five million customers in eight minutes on 40 threads.
The matrix is the bottleneck.
n = 5×10⁶ · edges ≈ n²/2 ≈ 1.25×10¹³
~100 TBif every edge weight is stored as 8 bytes
192 GBmemory on the machine used for the experiments
BP-MDS keeps an MST inside each cone: n − 1 edges. Prim computes a Euclidean weight only for the edge it is testing. A custom min-heap and on-demand allocation make that tree cheap across cores.
What stays from ParMDS is the route engine: MST, randomized DFS, then 2-opt. What changes is the split, the implicit graph, and the parallel schedule.
310 capacity-only Euclidean instances
| Set | # | What it stresses |
|---|---|---|
| CVRPLIB | 130 | Known best solutions: X (100), Golden 9–20, AGS cities, CMT5, E, F, P, tai. Gap against BKS. |
| FILO2 | 20 | Real Italian regions, about 20 thousand to 1 million customers. The city-scale check. |
| Synthetic XML | 160 | Uchoa generator, from 10 customers up to 5×10⁶. The scaling check. |
How it solves
Five million in eight minutes.
-
01
Partition⌈360°/α⌉ cones. The depot sits in every cone.
-
02
ConquerMST and ρ randomized DFS, one cone per set of cores.
-
03
Stitch2-opt inside the cone, then union the routes.
5×106customers, 8 minutes
2370×vs HGS, 40 threads
100×vs HGS, 1 thread
20–60×vs ParMDS
1.27%gap, 20 FILO2 cities
8.51%gap, wherever a BKS exists
310 instances · Xeon Gold 6248 · 40 threads · 192 GB