Computational procedure, condition (III), p. 573 — the Table II test holds exactly when the runs can be allocated to trucks
ProvedClarkeWright64.Savings.tableII_iff_fleetFeasiblefleethall-conditionp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing
Suppose the capacities are ordered, , and the smallest trucks are unlimited, . Then for every finite multiset of run loads the following are equivalent:
- the loads pass the Table II test: for each ,
- the runs can be allocated to the trucks: each run receives a truck of a class whose capacity is at least its load, and no class receives more than runs.
This is what justifies condition (III): checking the columns of Table II decides whether the amended routes are "consistent with truck availabilities and capacities".
Formalization Note Both standing assumptions of p. 569 are needed: without the untested column "Up to " would bind, and without the order of the the columns are not nested.
Preamble
import Mathlib import Definitions.Def_SupplyChainTheory_vrp import Definitions.Def_ClarkeWright64_Savings_Instance
Formal statement
namespace ClarkeWright64.Savings
/-- Clarke & Wright (1964), Computational procedure, condition (III), p. 573: when
`C₁ < ⋯ < C_n` and `x₁ = ∞`, a multiset of run loads passes the Table II test exactly when the
runs can be allocated to the available trucks without exceeding any truck's capacity. -/
theorem tableII_iff_fleetFeasible {M n : ℕ} (I : Instance M n) (hC : StrictMono I.C)
(hx : I.x 0 = ⊤) (loads : Multiset ℝ) :
I.TableIIOK loads ↔ I.FleetFeasible loads := by sorry
end ClarkeWright64.Savings
Source
Clarke & Wright, Scheduling of vehicles from a central depot to a number of delivery points, Oper. Res. 12 (1964), p. 573, Computational procedure, condition (III) and Table II; p. 569 (ordering of C_i, x_1 infinite)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.