Theoretical aspects, pp. 571–572 — linking cell (y:z) saves exactly d_{0,y} + d_{0,z} − d_{y,z}
ProvedClarkeWright64.Savings.link_savingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing
Let the distances be symmetric, . Let be a state that the savings procedure reaches from the initial basic solution, and let be an admissible cell of (conditions (I)–(III)). If is the state obtained by linking and , then
Since and are both linked to the depot, linking them severs only their links to ; this is why the cell value of the half matrix is the distance saved by the link.
Formalization Note Symmetry of is the paper's half matrix (p. 573); it is needed because a run may be reversed to bring to its end.
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: linking an admissible cell `(y:z)`
of a state reached by the procedure lowers the total mileage by exactly the saving
`d_{0,y} + d_{0,z} − d_{y,z}`, for symmetric distances. -/
theorem link_saving {M n : ℕ} (I : Instance M n) (hsymm : ∀ i j, I.d i j = I.d j i)
(s : State M) (hs : Reachable I s) (y z : Fin (M + 1)) (hyz : Admissible I s y z) :
I.mileage (link s y z) = I.mileage s - I.saving y z := 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; p. 573 (cell values)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.