  In this research we consider the problem of accelerating the convergence of
column generation (CG) for the weighted set cover formulation of the
capacitated vehicle routing problem with time windows (CVRPTW). We adapt two
new techniques, Local Area (LA) routes and Graph Master (GM) to these problems.
LA-routes rely on pre-computing all lowest cost elementary sub-routes, called
LA-arcs, where all customers but the final customer are localized in space.
LA-routes are constructed by concatenating LA-arcs where the final customer in
a given LA-arc is the first customer in the subsequent LA-arc. To construct the
lowest reduced cost elementary route during the pricing step of CG we apply a
Decremental State Space Relaxation/time window discretization method over time,
remaining demand, and customers visited; where the edges in the associated
pricing graph are LA-arcs. To accelerate the convergence of CG we use an
enhanced GM approach. We map each route generated during pricing to a strict
total ordering of all customers, that respects the ordering of customers in the
route; and somewhat preserves spatial locality. Each such strict total ordering
is then mapped to a multi-graph where each node is associated with a tuple of
customer, capacity remaining, and time remaining. Nodes are connected by
feasible LA-arcs when the first/last customers in the LA-arc are less/greater
than each intermediate customer (and each other) with respect to the total
order. The multi-graph of a given route can express that route and other
"related" routes; and every path from source to sink describes a feasible
elementary route. Solving optimization over the restricted master problem over
all multi-graphs is done efficiently by constructing the relevant nodes/edges
on demand.
