Theorem 11.6, lower bound (routing part):
ProvedSupplyChainTheory.vrp_tsp_lelower-boundsoperations-researchtraveling-salesmanvehicle-routing
For a unit-demand VRP instance with metric distances, : the optimal TSP tour through the depot and all customers is no longer than the optimal VRP solution. Concatenating the routes of a VRP solution gives a closed walk through all nodes that visits the depot once per route; shortcutting the repeated depot visits, by the triangle inequality, yields a tour no longer than the solution. As this bound and the upper bound of Theorem 11.6 both approach .
Preamble
import Definitions.Def_SupplyChainTheory_vrp
Formal statement
namespace SupplyChainTheory
theorem vrp_tsp_le {n : ℕ} (c : Fin (n + 1) → Fin (n + 1) → ℝ) (hc : VRPMetric c)
(hn : 1 ≤ n) (C : ℕ) (hC : 1 ≤ C) : tspOpt 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 ('Moreover, by the triangle inequality, zT ≤ z∗')
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.