§1, p. 2 — every CVRP route is a q-route without 2-cycles
ProvedRobustBCPCVRP.Formulation.route_isQRoutecolumn-generationinteger-programmingp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1vehicle-routing
In a CVRP instance with graph , demands and capacity , let be a CVRP route: a walk in , , visiting pairwise distinct clients with total demand at most . Then is a q-route without 2-cycles:
This containment is what makes the column formulation a relaxation of the CVRP: every vehicle route of a feasible solution is available as a column.
Formalization Note The paper says the containment is strict. Strictness depends on the instance (for instance, it fails when is smaller than twice every client demand, since then no q-route can repeat a client), so only the containment is stated.
Preamble
import Mathlib import Definitions.Def_LysgaardCVRP_Shrink_cut import Definitions.Def_LysgaardCVRP_Shrink_roundedCapacityBound import Definitions.Def_RobustBCPCVRP_Formulation_Setting import Definitions.Def_RobustBCPCVRP_Formulation_Polytopes open LysgaardCVRP.Shrink
Formal statement
namespace RobustBCPCVRP.Formulation
theorem route_isQRoute {n : ℕ} (E : Finset (Sym2 (Fin (n + 1))))
(d : Fin (n + 1) → ℕ) (C : ℕ) (r : List (Fin (n + 1))) (hr : IsRoute E d C r) :
IsQRoute E d C r := by sorry
end RobustBCPCVRP.Formulation
Source
Fukasawa, Longo, Lysgaard, Poggi de Aragão, Reis, Uchoa & Werneck, Robust branch-and-cut-and-price for the capacitated vehicle routing problem, Math. Program. (DOI 10.1007/s10107-005-0644-x); accepted manuscript, p. 2, §1, definition of q-routes; p. 4, §2, q-routes without 2-cycles
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.