Theorem 4 — no deterministic CVRP reformulation over first-order generic ambiguity sets

There is an instance of the distributionally robust CVRP whose ambiguity set has the form of the first-order generic moment ambiguity set, that is, a number $n$ of customers, a number $m$ of vehicles of capacity $Q>0$, a risk level $\epsilon\in(0,1)$, a support box $[\underline{\boldsymbol q},\overline{\boldsymbol q}]$ with $\underline{\boldsymbol q}\ge\mathbf 0$, a mean $\boldsymbol\mu$ in the interior of the box, customer subsets $S_1,\dots,S_p$ and bounds $\boldsymbol\nu>\mathbf 0$, with the following property: for every deterministic CVRP instance with the same customers and vehicles, i.e. every capacity $Q'\ge0$ and every demand vector $\boldsymbol q'\in\mathbb R^n_+$,

This contrasts with marginalized moment ambiguity sets, over which the distributionally robust CVRP is equivalent to a deterministic CVRP with altered demands: once the ambiguity set couples the demands of different customers, the feasible route sets need not be those of any deterministic instance.

Formalization Note Route sets are R : Fin m → List (Fin n); feasibility in $\mathrm{RVRP}(\mathcal P)$ requires $\mathbb P[\sum_{i\in\mathbf R_k}\tilde q_i\le Q]\ge1-\epsilon$ for every distribution in the ambiguity set and every vehicle. The paper takes $Q\in\mathbb R_+$; the statement asks for $Q>0$, which only restricts the witness.