Computational procedure, relation (A), p. 573 — every customer has Σ_{z≠y} t_{y,z} = 2 at every stage
ProvedClarkeWright64.Savings.relation_Ainvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing
In the initial basic solution every customer has (). Moreover, at every state reached by the savings procedure, every customer satisfies relation (A):
Relation (A) says that each customer is joined to exactly two neighbours on its truck's route, the depot counting once for each side of a run it closes; it is what makes the matrix a valid description of a set of routes throughout the procedure.
Formalization Note The two sums of the printed display lack a "+" between them; the statement uses the sum, written , over . The relation is stated for every reachable state, not for arbitrary lists of runs, for which it is false.
Preamble
import Mathlib import Definitions.Def_SupplyChainTheory_vrp import Definitions.Def_ClarkeWright64_Savings_Instance import Definitions.Def_ClarkeWright64_Savings_Procedure
Formal statement
namespace ClarkeWright64.Savings
/-- Clarke & Wright (1964), Computational procedure, relation (A), p. 573: the initial basic
solution has `t_{y,0} = 2` for every customer, and at every state the procedure reaches, every
customer `P_y` has `∑_{z ≠ y} t_{y,z} = 2` (the sum includes `z = 0`). -/
theorem relation_A {M n : ℕ} (I : Instance M n) :
(∀ y : Fin (M + 1), y ≠ 0 → t (init M) y 0 = 2) ∧
∀ s : State M, Reachable I s →
∀ y : Fin (M + 1), y ≠ 0 → ∑ z ∈ Finset.univ.erase y, t s y z = 2 := 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, relation (A)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.