Sec. 3 and Figure 1, pp. 345–346 — the example has 11 feasible routes, 22 second-model paths and 12 2-cycle-free paths
ProvedVRPTWColGen92.Bound.fig1_solution_spacesexamplep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1time-windowsvehicle-routing
In the four-node example of Figure 1 (capacity , for every choice of the costs), the three solution spaces of Sec. 3 are exactly as follows.
- The feasible routes are the eleven routes , , , , , , , , , , .
- The paths of the second model are those eleven routes and the eleven paths , , , , , , , , , , : twenty-two in all.
- The paths of the third model (no 2-cycle) are the eleven routes and : twelve in all.
The example shows that the inclusions between the three solution spaces can be strict.
Formalization Note. The page's list for the second model prints twice; enumeration under the mission's conventions gives as the eleventh nonelementary path, and the statement lists that path. The counts need the capacity constraint "load " (with , the path of load would drop out).
Preamble
import Mathlib import Definitions.Def_VRPTWColGen92_Bound_Network import Definitions.Def_VRPTWColGen92_Bound_Fig1
Formal statement
namespace VRPTWColGen92.Bound
theorem fig1_solution_spaces (c : Fin 4 → Fin 4 → ℝ) :
{p | IsRoute (fig1 c) p} =
({[1], [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [1, 2, 3], [2, 1, 3], [2, 3, 1]} :
Set (List (Fin 4))) ∧
{p | IsPath (fig1 c) p} =
({[1], [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [1, 2, 3], [2, 1, 3], [2, 3, 1],
[1, 2, 1], [1, 3, 1], [2, 1, 2], [3, 1, 3], [1, 2, 1, 2], [1, 2, 1, 3], [1, 2, 3, 1],
[1, 3, 1, 3], [2, 1, 2, 1], [2, 1, 3, 1], [3, 1, 3, 1]} : Set (List (Fin 4))) ∧
{p | IsPath3 (fig1 c) p} =
({[1], [2], [3], [1, 2], [1, 3], [2, 1], [2, 3], [3, 1], [1, 2, 3], [2, 1, 3], [2, 3, 1],
[1, 2, 3, 1]} : Set (List (Fin 4))) := 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 and Figure 1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.