Theorem 6 — no deterministic CVRP has the same feasible route sets

There is an instance of the distributionally robust capacitated vehicle routing problem with the covariance ambiguity set (16) — a number $n$ of customers, $m$ vehicles of capacity $Q\ge0$, a risk level $\epsilon\in(0,1)$, a box $[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$, a mean $\boldsymbol\mu$ in its interior and a covariance bound $\Sigma\succ0$ — such that for every deterministic instance on the same customers and fleet, with capacity $Q'\ge0$ and demands $\boldsymbol q\ge\mathbf 0$,

In words, the chance constraints over a covariance ambiguity set cannot, in general, be replaced by deterministic capacity constraints with suitably chosen demands and capacity. This is why the paper works with the demand estimator $d_{\mathcal P}$ instead of a deterministic surrogate.

Formalization Note Route sets, RVRP($\mathcal P$)-feasibility and deterministic feasibility are the definitions IsRouteSet, RVRPFeasible and DetFeasible. "The same set of feasible route sets" is equality of the two sets of route sets Fin m → List (Fin n). The instance is required to satisfy all side conditions of (16).