Formulation, p. 569 — if C_n ≥ Σ_j q_j the problem becomes the traveling salesman problem
ProvedClarkeWright64.Savings.tsp_caseSuppose the distances are shortest-route distances: is symmetric, nonnegative, zero on the diagonal and satisfies the triangle inequality. Suppose the largest capacity covers all the loads,
and at least one truck of capacity is available. Then the least total mileage of a feasible allocation of the loads to trucks equals the length of a shortest traveling salesman tour through the depot and all the customers.
Formalization Note The printed sum has upper limit , which is a misprint: counts truck classes, and the sum is over the customers. The availability of a truck of capacity is implied by the paper's "trucks ... are available" and is stated explicitly. The metric hypotheses come from p. 568, "the shortest route between every two points in the system is given".
import Mathlib import Definitions.Def_SupplyChainTheory_vrp import Definitions.Def_ClarkeWright64_Savings_Instance import Definitions.Def_ClarkeWright64_Savings_Procedure
namespace ClarkeWright64.Savings
/-- Clarke & Wright (1964), Formulation, p. 569: if the distances are shortest-route distances
(a metric) and the largest capacity `C_n` is at least the total load of all customers, with at
least one such truck available, the optimum of the problem equals the length of an optimal
traveling salesman tour through the depot and all customers. -/
theorem tsp_case {M n : ℕ} (I : Instance M n) (hd : SupplyChainTheory.VRPMetric I.d)
(hcap : ∑ j ∈ Finset.univ.erase (0 : Fin (M + 1)), I.q j ≤ I.C (Fin.last n))
(htruck : 1 ≤ I.x (Fin.last n)) :
optMileage I = SupplyChainTheory.tspOpt I.d := by sorry
end ClarkeWright64.Savings
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.