Theoretical aspects, pp. 571–572 — links between customers are never severed; interior points are never reconsidered
ProvedClarkeWright64.Savings.interior_points_finalinvariantp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing
Let be a state reached by the savings procedure and let follow by one step. Then:
- every link between two customers survives: if in for customers , then in ;
- no customer's link count to the depot increases: ;
- a customer with in (one linked to two other customers) lies in no admissible cell of or of any state reached from , so it is never considered again for linking.
This is the procedure's form of the paper's remark that the only links ever severed are those to .
Formalization Note The paper argues this for its general scheme through "shadow costs"; only the conclusion is formalized, for the procedure of pp. 573–575.
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), Theoretical aspects, pp. 571–572: in a step of the procedure from a
reachable state, (a) every link between two customers survives, (b) no `t_{y,0}` increases, and
(c) a customer with `t_{y,0} = 0` (linked to two customers) lies in no admissible cell of any
later state, so it is never considered again for linking. -/
theorem interior_points_final {M n : ℕ} (I : Instance M n) (s s' : State M)
(hs : Reachable I s) (hstep : Step I s s') :
(∀ y z : Fin (M + 1), y ≠ 0 → z ≠ 0 → t s y z = 1 → t s' y z = 1) ∧
(∀ y : Fin (M + 1), y ≠ 0 → t s' y 0 ≤ t s y 0) ∧
(∀ y : Fin (M + 1), y ≠ 0 → t s y 0 = 0 →
∀ s'' : State M, Relation.ReflTransGen (Step I) s s'' →
∀ z : Fin (M + 1), ¬ Admissible I s'' y z ∧ ¬ Admissible I s'' z y) := 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), pp. 571–572, Theoretical aspects
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.