Eq. (11.59), the iterated optimal tour partition bound: for every customer tour some partition into consecutive routes costs at most ,
ProvedSupplyChainTheory.iotp_boundheuristicsoperations-researchupper-boundsvehicle-routing
For a unit-demand VRP instance with metric distances, customers, capacity , , and any tour through the depot and all customers, there is a feasible VRP solution of total length at most
This is the iterated optimal tour partition heuristic: cut the customer sequence of into consecutive blocks of at most customers starting at each of the customers in turn, connect each block to the depot, and keep the best of the solutions. Over the solutions each customer is first and last on exactly routes and each tour edge is omitted exactly times, so the average solution costs and the best is no worse. Applied to the optimal tour it gives the upper bound of Theorem 11.6.
Preamble
import Definitions.Def_SupplyChainTheory_vrp
Formal statement
namespace SupplyChainTheory
theorem iotp_bound {n : ℕ} (c : Fin (n + 1) → Fin (n + 1) → ℝ) (hc : VRPMetric c)
(hn : 1 ≤ n) (C : ℕ) (hC : 1 ≤ C) (L : List (Fin (n + 1))) (hL : IsCustomerTour L) :
∃ R, IsVRPSolution C R ∧ solutionCost c R
≤ 2 * ⌈(n : ℝ) / C⌉₊ * avgDepotDist c + (1 - (⌈(n : ℝ) / C⌉₊ : ℝ) / n) * routeCost c L := 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, pp. 495-496, Sect. 11.4.1, the proof of Theorem 11.6, the optimal tour partition and iterated optimal tour partition heuristics, Eq. (11.58)-(11.59)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.