Theorem 11.6, lower bound (radial part):
ProvedSupplyChainTheory.vrp_radial_boundlower-boundsoperations-researchvehicle-routing
For a unit-demand VRP instance on customers with capacity and metric distances, , where is the average distance from the depot to the customers. Each route serving the customer set has length at least by the triangle inequality, hence at least , and summing over the routes gives the bound. The radial term dominates for large (Theorem 11.7).
Preamble
import Definitions.Def_SupplyChainTheory_vrp
Formal statement
namespace SupplyChainTheory
theorem vrp_radial_bound {n : ℕ} (c : Fin (n + 1) → Fin (n + 1) → ℝ) (hc : VRPMetric c)
(hn : 1 ≤ n) (C : ℕ) (hC : 1 ≤ C) :
2 * ((n : ℝ) / C) * avgDepotDist c ≤ vrpOpt c C := by sorry
end SupplyChainTheory
Source
Lawrence V. Snyder and Zuo-Jun Max Shen, Fundamentals of Supply Chain Theory, 2nd ed., Wiley 2019, DOI 10.1002/9781119584445, p. 495, Sect. 11.4.1, the proof of Theorem 11.6 ('We prove the lower bound first')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.