Sec. 3, p. 346 — every feasible route is a 2-cycle-free path, and every 2-cycle-free path is a path of the second model
ProvedVRPTWColGen92.Bound.route_isPath3p2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1state-space-relaxationtime-windowsvehicle-routing
The three dynamic programming models of Sec. 3 have nested solution spaces. Let be a customer list in a VRPTW instance. Then
- if is a feasible route (first model), it is a path of the third model (a resource-feasible path without 2-cycles);
- if is a path of the third model, it is a path of the second model.
These inclusions are what make the column generation LP over 2-cycle-free paths a relaxation of the set partitioning model: every VRPTW solution uses only columns the subproblem can generate.
Formalization Note. A 2-cycle is a pattern of three consecutive customers; the depot is not part of the customer list.
Preamble
import Mathlib import Definitions.Def_VRPTWColGen92_Bound_Network
Formal statement
namespace VRPTWColGen92.Bound
theorem route_isPath3 {n : ℕ} (I : Instance n) (p : List (Fin (n + 1))) :
(IsRoute I p → IsPath3 I p) ∧ (IsPath3 I p → IsPath I p) := by sorry
end VRPTWColGen92.Bound
Source
Desrochers, Desrosiers & Solomon, A new optimization algorithm for the vehicle routing problem with time windows, Oper. Res. 40 (1992), pp. 345–346, Sec. 3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.