Computational procedure, the example, pp. 575–576 — every run on Table I ends with total distance 290
ProvedClarkeWright64.Savings.example_290examplep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1savings-algorithmvehicle-routing
On the twelve-customer instance of Table I with the fleet of p. 573 (unlimited 4000-gallon trucks, three of 5000 gallons, four of 6000 gallons), every run of the savings procedure, whichever way the ties are broken, stops in a state whose runs serve the customer sets
with total distance units.
The paper reports the routes , , , . The order of customers within a run depends on the tie-breaks, so only the partition and the total are stated.
Preamble
import Mathlib import Definitions.Def_SupplyChainTheory_vrp import Definitions.Def_ClarkeWright64_Savings_Instance import Definitions.Def_ClarkeWright64_Savings_Procedure import Definitions.Def_ClarkeWright64_Savings_TableI
Formal statement
namespace ClarkeWright64.Savings
/-- Clarke & Wright (1964), the numerical example, pp. 575–576: on the data of Table I with
the fleet of p. 573, every run of the procedure (every tie-break) stops with the customers
partitioned into the runs `{1,2,3,4}`, `{5}`, `{6,8,9}`, `{7,10,11,12}` and a total
distance of 290 units. -/
theorem example_290 (s : State 12) (hs : Reachable tableI s) (hterm : Terminal tableI s) :
tableI.mileage s = 290 ∧
(↑(s.map List.toFinset) : Multiset (Finset (Fin 13))) =
{{1, 2, 3, 4}, {5}, {6, 8, 9}, {7, 10, 11, 12}} := 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. 575–576, Computational procedure (Tables V, VI and the routes)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.