Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Computational procedure, relation (A), p. 573 — every customer has Σ_{z≠y} t_{y,z} = 2 at every stage

Proved
ClarkeWright64.Savings.relation_A

by mikedeng1 · Oct 6, 2026 · Mathlib 0df444a (Lean v4.33.1)

invariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing

In the initial basic solution every customer has ty,0=2t_{y,0}=2ty,0​=2 (y=1,…,My=1,\dots,My=1,…,M). Moreover, at every state reached by the savings procedure, every customer PyP_yPy​ satisfies relation (A):

∑z=0y−1ty,z+∑z=y+1Mty,z=2.\sum_{z=0}^{y-1} t_{y,z}+\sum_{z=y+1}^{M} t_{y,z}=2 .z=0∑y−1​ty,z​+z=y+1∑M​ty,z​=2.

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 ttt 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 ∑z≠yty,z\sum_{z\neq y}t_{y,z}∑z=y​ty,z​, over z=0,…,Mz=0,\dots,Mz=0,…,M. 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
  • Endorsed by Shuze Chen · Oct 6, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me