MDCVRP: A Graph Matching Based Approach for the Multi-Depot Capacitated Vehicle Routing Problem

Abstract

The Multi-Depot Capacitated Vehicle Routing Problem (MDCVRP) asks for minimum-cost delivery tours from several capacitated depots to a set of customers. Like most vehicle-routing variants it is NP-hard, so practical solvers must trade solution quality against speed. This trade-off is sharpest in the dynamic settings that motivate this work, where routes must be revised as new orders arrive. We revisit it through the lens of graph matching. Adapting a matching-based construction first developed for the Traveling Tournament Problem, we present two algorithms, Cluster-First and Match-First, that reduce routing to a sequence of minimum-weight matchings. We prove that for tours of up to two targets the matching formulation solves the MDCVRP exactly in polynomial time for any number of depots. In the structured regimes, both algorithms are constant-factor approximations of this optimum, with a tight factor of two. This matching optimum coincides with the exact combinatorial-auction optimum, so the auction serves as a strong quality baseline. Because Cluster-First routes each depot independently, the approach also re-routes cheaply when new customers arrive. On instances of 1000 customers and 20 depots our methods match or beat the baseline in tour length while running two to three orders of magnitude faster, a scale at which exact and auction-based solvers become impractical.

The Problem

The MDCVRP combines capacitated vehicles with several geographically distributed depots. It is NP-hard, so exact methods are impractical beyond small instances and the literature is dominated by heuristics that trade optimality for speed. The usual recipe is cluster-first, route-next: group customers by depot, then route each cluster as a single-depot problem. Learning-based methods reach high quality on small instances but scale poorly and are expensive to train, which is a poor fit for the large, dynamically changing instances that arise in practice.

Input

Vehicles with capacities, each stationed at a depot; customers at known locations, each with the weight of the goods they ordered; travel costs given by a weighted graph.

Output

A set of tours, each leaving and returning to a depot, visiting every customer exactly once, minimising the sum of tour costs.

Why it is hard

NP-hard like most VRP variants, and harder still when routes must be revised as new orders arrive, since a solver that has to restart from scratch is unusable online.

Method

Rather than building routes sequentially, we reduce routing to minimum-weight matching on the complete graph whose vertices are the targets and whose edge weights are inter-target distances, computed with Edmonds' Blossom algorithm. Each matched pair becomes one tour that leaves a depot, visits both targets and returns; each unpaired target gets a singleton round trip. The construction adapts a matching-based bound originally proposed for the Traveling Tournament Problem.

Two algorithms

CF

Cluster-First

Assign each target to its nearest depot, then match within each cluster and route the pairs from that depot. Cheap, and it re-solves only the affected cluster when a customer arrives.

MF

Match-First

Match once over all targets with no reference to the depots, then route each group from the depot nearest its centroid. Global matching finds pairings clustering cannot.

M&M

Match-and-Merge

For unbounded tour sizes, collapse each pair to a midpoint node and match again, merging two pairs into a four-target tour when capacity allows, iterating until no merge fits.

Three scenarios

Scenario 1

Demands at most half the capacity, tours of at most two targets, so every pair is feasible and matching runs on the full complete graph.

Scenario 2

Demands at most half the capacity, tour size unbounded, so tours are built by Match-and-Merge, giving groups of up to four targets.

Scenario 3

Demands up to the full capacity, tours of at most two targets, so infeasible pairs are cut from the graph and Match-First additionally drops pairs that save nothing.

As a strong point of comparison we also formulate the MDCVRP as a combinatorial auction, where depots bid on bundles of targets and a winner-determination step picks a feasible lowest-cost assignment. We evaluate two implementations of it, an Integer Linear Program (CA-ILP) and a Maximum Independent Set formulation (CA-MIS). In each scenario the auction is restricted to bundles no larger than the biggest tour the matching methods can form, so the comparison is like-for-like.

Theoretical Analysis

Tour size two is a tractability boundary

For tours of up to two targets, the MDCVRP is solvable exactly in O(n²K + n³) time for any number of depots: score each pair from its best depot and take a maximum-saving matching. The exact ILP auction computes this same optimum, which is why it is a strong baseline rather than a weak one.

Tight 2-approximations

Cluster-First costs at most twice the nearest-depot lower bound, with the factor of two tight because a pair whose targets are nearest to different depots gets split. Match-First is unbounded without a safeguard; restricting the matching to positive-saving pairs restores the same guarantee.

Running time

Match-First costs O(n³ + nK), rising to O(n³ + n²K) in Scenario 3, where the savings filter scores every candidate pair against every depot. Cluster-First avoids that precomputation entirely, at O(nK + Σₚ nₚ³), far below n³ once targets spread across depots.

Larger tours

For the four-target tours of Scenario 2 every merge only lowers cost, and Cluster-First is a 4-approximation, a factor tight for nearest-depot clustering. Extending the guarantees past tour size four is left as future work.

Results

All methods are implemented in C++ and run on randomly generated Euclidean instances: a base collection of 100 datasets with 100 targets and 10 depots, and a scalability collection of 50 datasets with 1000 targets and 20 depots. Every dataset fixes the number of depots and targets and varies only target locations and demands.

Quality at scale

2–4%

shorter tours than the CA-MIS auction on the 1000-target instances

Speed at scale

2–3 orders

of magnitude faster than the auction, which the ILP cannot solve at all

Choosing a baseline

A speed claim is only as convincing as the baseline it is measured against, so we first fix that baseline. Three standard solvers are compared on the base instances, all following the cluster-first, route-next pattern and differing only in how each single-depot subproblem is routed: a nearest-neighbour heuristic, a two-stage solver built on Google OR-Tools, and our combinatorial auction. The auction gives the shortest tours at both representative capacities.

Boxplots of combined tour distances for nearest neighbour, combinatorial auction and two-stage at capacity 100 — **Figure 1a.** Tour lengths over the 100 base instances at vehicle capacity 100.

Boxplots of combined tour distances for nearest neighbour, combinatorial auction and two-stage at capacity 150 — **Figure 1b.** The same comparison at vehicle capacity 150.

Sweeping the vehicle capacity confirms that the ranking is not an artefact of one setting. The auction leads across almost the whole range, and only in the regime where capacities dwarf target demands does a baseline draw level, which is expected given that we deliberately restrict the auction to small bundles. We therefore carry the auction forward as the single point of comparison.

Average tour length against vehicle capacity for the combinatorial auction and the baseline heuristics — **Figure 2.** Average tour length as vehicle capacity varies, over the same base instances.

RQ1: Graph matching versus the auction

On the base instances the two matching methods are compared against both auction implementations across the three scenarios. The exact ILP auction attains the shortest tours, with the matching methods a few percent behind; against the MIS auction they are level or ahead in Scenarios 1 and 3. The runtime picture, on a log scale, is not close: in Scenario 3 the paper reports a mean tour of 5305 for CA-ILP at 479 ms per instance, against 5411 for Match-First at 4.8 ms and 5626 for Cluster-First at 3.3 ms, so the matching methods stay within 2 to 6% of the best tour at roughly two orders of magnitude less time.

Tour distance distributions for Cluster-First, Match-First, CA-ILP and CA-MIS across three scenarios — **Figure 3.** Tour distance over the 100 base instances, by method and scenario.

Runtime distributions on a log scale for Cluster-First, Match-First, CA-ILP and CA-MIS across three scenarios — **Figure 4.** Computation time over the same instances, on a logarithmic scale.

RQ2: Effect of capacity

Varying the vehicle capacity leaves the ordering untouched. Both matching methods stay flat and far below both auction implementations at every capacity and in every scenario, so the speed advantage is a property of the method rather than of one operating point.

Computation time against vehicle capacity for the four methods across three scenarios — **Figure 5.** Computation time as vehicle capacity varies, on the base instances.

RQ3: Scalability

At 1000 targets and 20 depots the ILP auction no longer completes, and Scenario 2 is out of reach for the auction formulation entirely, since the number of candidate bundles explodes. Against CA-MIS the matching methods are no longer behind on quality: they match or slightly beat it in both scenarios shown. The time gap, meanwhile, widens to two or three orders of magnitude, with Cluster-First averaging tens of milliseconds per instance against tens of seconds for the auction.

Tour distance distributions at scale for Cluster-First, Match-First and CA-MIS in Scenarios 1 and 3 — **Figure 6.** Tour distance over the scalability instances, 1000 targets and 20 depots.

Runtime distributions at scale for Cluster-First, Match-First and CA-MIS in Scenarios 1 and 3 — **Figure 7.** Computation time over the same instances, on a logarithmic scale.

The quality gap closes at scale

On the base instances the exact auction wins on tour length by a few percent. At 1000 targets the matching methods match or slightly beat the auction that still runs.

Orders of magnitude faster

The runtime plots are logarithmic, and the gap grows with instance size until the ILP auction stops finishing altogether.

Robust across capacities

Sweeping the vehicle capacity leaves the ordering intact, so the speed-up is not an artefact of one capacity setting.

Cheap to re-route

Because Cluster-First assigns each target to its nearest depot and matches only within clusters, a newly arrived customer re-solves one cluster instead of the whole instance, which is the dynamic setting that motivates the work.

Citation

@misc{chandwani2026mdcvrp,
  title         = {A Graph Matching Based Approach for the Multi-Depot Capacitated Vehicle Routing Problem},
  author        = {Chandwani, Jayant and M R, Pranav and Jat, Anand and Ostwal, Anshu and Chatterjee, Diptendu and Narasimhamurthy, Anand},
  year          = {2026},
  eprint        = {2607.27727},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2607.27727}
}

MDCVRP MDCVRP