Private Price Signals for Collaborative Vehicle Routing Among Competing Carriers

Competing delivery companies waste many kilometres driving half-empty trucks. If they could swap delivery orders, studies on real freight data report large savings. A multi-agent auction across 1,000 Dutch carriers cut travel costs by up to 77% (Large-scale collaborative vehicle routing). Pairwise "give-and-take" swaps among five Singapore logistics providers raised joint profit by up to 14.32% (Individually Rational Collaborative Vehicle Routing through Give-And-Take Exchanges). Both methods, however, make carriers reveal commercially sensitive material in plaintext. The auction exposes bundles, bids and reservation prices. The give-and-take method sends whole re-optimized routes to a central integer program. That second paper names a decentralized design that "could remove the need for a central marketplace, enhancing data privacy" as open future work.

This note proposes a different approach. Carriers coordinate only through prices posted on a shared pool of orders, and the coordinator never sees an individual carrier's response. In each round, each carrier plans its own routes on its true private data and decides which pooled orders it would take at current prices. The coordinator then learns only a noisy total of how many carriers want each order, computed by secure summation, which reveals the sum but not the individual inputs. Prices rise for orders nobody wants and fall for orders that are over-claimed. The central bet is about where the privacy noise goes. Prior work perturbed locations or physical inputs, and that broke routing. Here the noise is placed in the price space, so it cannot make any route infeasible.

Core Claim

The claim is that noise belongs in the coordination signal, not in the routing problem. Privacy-preserving vehicle assignment for mobility-on-demand systems added planar Laplace noise to vehicle locations before a central matching step. This raised mean passenger wait from 181 s to 234 s. The authors could recover only by sending several physical vehicles per request. Routing is fragile to input noise because capacities and time windows are hard constraints. In our scheme every carrier solves its own routing subproblem exactly on its own data, so every route a carrier commits to is feasible by construction. Noise only blurs the aggregate demand count that drives price updates, and a slightly wrong price costs efficiency, not feasibility.

The second claim is testable. Decentralized Nonconvex Optimization with Guaranteed Privacy and Accuracy showed that privacy noise in continuous nonconvex problems acts as a random push that escapes saddle points. Discrete best-response price dynamics have a known failure of their own: integrality causes prices to cycle, with two carriers alternately claiming and dropping the same order. We hypothesize that moderate noise on aggregate counts dampens this cycling, much as randomized best responses do in games. If so, a privacy budget in some range costs little or nothing in welfare. This is a hypothesis, and SVRPBench gives reason for doubt: it shows uncertainty degrading routing badly, with learned solvers losing over 20%. The experiments are designed to reject it if it is wrong.

Mechanism

Let $R$ be the pool of orders that carriers have agreed to make tradable. Each order $r$ is released by its owner, who pays a transfer $p_r$ to whoever serves it. In round $t$, carrier $k$ holds its private orders, fleet and costs. It solves a prize-collecting vehicle routing problem with time windows:

$$y_k^t = \arg\max_{y \in \{0,1\}^{|R|}} \Big[ \sum_{r} p_r^t\, y_r - C_k(y) - \tfrac{\rho}{2}\lVert y - y_k^{t-1}\rVert^2 \Big]$$

Here $y_r$ indicates that carrier $k$ claims order $r$. $C_k(y)$ is carrier $k$'s minimum routing cost to serve its own orders plus the claimed ones, computed by any local solver it likes. The last term is a proximal penalty with weight $\rho$ that discourages flip-flopping, borrowed from the augmented terms in ADMM (the alternating direction method of multipliers, a standard way of splitting an optimization across parties). Carriers submit masked shares of $y_k^t$, each adding a share of Gaussian noise. The coordinator then recovers only $s_r^t = \sum_k y_{kr}^t + \xi_r^t$ and updates prices by $p_r^{t+1} = p_r^t - \eta(s_r^t - 1)$ with step size $\eta$.

This is Dantzig–Wolfe-style price coordination applied to discrete routing. Carriers price their own routes and the master sees only coverage. It mirrors how A Distributed Operational Method for Convex Hull Pricing Based on the Alternating Direction Method of Multipliers with Dantzig–Wolfe and Benders Decomposition keeps generator cost data local while coordinating through shadow prices, reaching optimality gaps within 0.1% of the exact convex-hull pricing benchmark in many cases. That work coordinates continuous energy quantities. We coordinate binary order claims, where no convergence guarantee transfers, so a final step is needed.

After $T$ rounds, conflicts are resolved by passing a token around a ring of carriers. The ring design is borrowed from the Hamiltonian-cycle token passing of Privacy-Preserving Incremental ADMM for Decentralized Consensus Optimization. The token carries the set of still-unassigned orders, and each carrier in turn takes the orders it still wants at final prices. Any order left unassigned returns to its owner. Each carrier keeps its isolated plan as a fallback and accepts the outcome only if its profit, including transfers, is at least that of the fallback. This enforces individual rationality locally rather than through a central constraint as in give-and-take.

The privacy guarantee has two layers. Secure aggregation alone gives an under-determination guarantee in the spirit of PI-ADMM: with three or more carriers, a single count does not reveal who claimed what. Calibrated noise adds formal differential privacy, meaning a guarantee that the released data changes little whether or not any one claim is present. The protected unit is one carrier's claim on one order per round, with composition across rounds. We will also report the much weaker guarantee at whole-carrier granularity, rather than hide it.

Research Program

The work has three parts. The first builds the protocol with carrier subproblems solved by an off-the-shelf prize-collecting VRPTW heuristic. The second analyzes what leaks. We characterize which carrier quantities an observer of the full price trajectory can infer even without individual claims, starting with marginal costs and depot regions; prices are public, so they leak something regardless. We also bound the welfare loss from the duality gap and from noise. The third evaluates the protocol against plaintext coordination and centralized solving. The deliverable is a measured trade-off between welfare and privacy budget, set against an empirical inference attack, not just a nominal epsilon.

Baselines

The naive reference point is isolation: each carrier routes only its own orders, and every other method is scored as percentage improvement over it.

The strongest small-scale competitor is Give-And-Take (Individually Rational Collaborative Vehicle Routing through Give-And-Take Exchanges). It reports up to 14.32% profit improvement on 200 orders from five Singapore providers, against 4.36% for the Order Package Heuristic, converging in about 270 s. It is the strongest competitor because it achieves the best reported welfare under the same individual-rationality requirement we impose, at the cost of full disclosure to a central solver. We will rerun it on the modified Li & Lim instances with offset depots that it uses. We will use the Singapore data only if it is obtainable, since we cannot confirm its availability. Both methods get the same local routing heuristic and the same wall-clock budget. Beating it means matching its welfare within a few points at a privacy budget where our attack below fails.

At large scale, the competitor is the multi-agent reverse-auction system (Large-scale collaborative vehicle routing), which reports travel-cost reductions of up to 77% with 1,000 carriers on more than 12,000 Dutch orders. We will run it on the Gansterer & Hartl (2016) instances it also uses and match it there. Its central combinatorial auction baseline will also be run where it remains tractable.

Two ablations isolate the contribution. Running our protocol without secure aggregation or noise, so that plaintext individual claims are visible, measures the pure cost of privacy. Varying the noise level while holding the number of rounds fixed tests the cycling-damping hypothesis. An input-perturbation baseline will also be run: geo-indistinguishable order locations fed to a central solver, following Privacy-preserving vehicle assignment for mobility-on-demand systems, at matched epsilon.

Why not just…?

Why not just run the central solver inside secure multiparty computation? This is the real threat. It gives centralized-quality solutions with cryptographic secrecy. The cost is that routing local search inside multiparty computation is orders of magnitude slower than in plaintext, and even plaintext central combinatorial auctions became intractable at large scale in Large-scale collaborative vehicle routing. We found no reported result on Lacuna for multiparty-computation collaborative routing. We will implement a secure version of the final selection step of Give-And-Take on the 40-order, six-provider stress test it reports and measure where its runtime crosses ours. If it stays competitive at Li & Lim scale, our contribution narrows to the large-carrier regime, and we will say so.

Why not just add location noise and use a strong central solver? The Tsao et al. numbers show a 30% wait-time penalty from location noise even in simple one-to-one matching. Multi-stop routing with time windows is more fragile than one-to-one matching. Our matched-epsilon comparison tests this directly. If location noise loses less welfare than price-space noise at the same epsilon, the core claim is wrong.

Why not just use plain Lagrangian price coordination, which already hides routes? Prices alone do hide routes, but plaintext individual claims across many rounds let a coordinator trace each carrier's acceptance threshold per order, which is its marginal cost. Our attack experiment quantifies this leak for the no-aggregation ablation. If the attack fails even there, the secure-aggregation and noise layers are unnecessary and the simpler method wins.

Proposed Experiments

The welfare experiments use modified Li & Lim instances with three to ten carriers and the Gansterer & Hartl and Dutch-platform settings with up to 1,000 carriers. Metrics are percentage welfare or travel-cost improvement over isolation, the fraction of carriers better off than isolated, rounds and wall-clock time to reach that point, and the number of orders returned unserved after the ring step.

Privacy is measured in two ways: the formal epsilon, and an attack in which the coordinator fits each carrier's marginal cost per order and depot region from all observed traffic. The attack score is reconstruction error against ground truth, compared across the plaintext, aggregated-only and noisy variants.

Two decisive checks determine whether the proposal holds. In the first, the price-space noisy protocol must beat location-noise at matched epsilon on welfare, with zero infeasible routes. If not, the central thesis fails. In the second, a plot of welfare against noise level at fixed rounds either shows a non-monotone region where small noise reduces price cycling and improves welfare over the noise-free ablation, or it does not. That outcome confirms or refutes the transfer of the Wang & Basar "double win" from continuous to discrete coordination.