  In this research we introduce Local Area (LA) routes for improving the
efficiency and tightness of column generation (CG) methods for solving vehicle
routing problems (VRP). LA-routes rely on pre-computing the lowest cost
elementary sub-route (called an LA-arc) for each tuple consisting of the
following: (1) a (first) customer where the LA-arc begins, (2) a distant
customer (from the first) where the LA-arc ends, and (3) a set of intermediate
customers near the first customer. 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. A Decremental State Space Relaxation method is applied over
LA-routes to construct the lowest reduced cost elementary route during the
pricing step of CG. LA-route based solvers can be used to efficiently tighten
the standard set cover VRP using a variant of subset row inequalities, which do
not alter the structure of pricing. We incorporate LA-arcs into a novel CG
stabilization scheme. Specifically each column generated during pricing is
mapped to an ordered list of customers consistent with that column. An LA-arc
is consistent with an ordering if the first/last customer in the arc come
before/after all other customers in the LA-arc in the associated ordering
respectively. Each such ordering is then mapped to a multi-graph where nodes
correspond to (customer/demand) and edges correspond to LA-arcs consistent with
that ordering. Hence any path from source to sink on the multi-graph is a
feasible elementary route. The ordering for a column places customers spatially
nearby in nearby positions on the ordering so that routes can be generated so
as to permit spatially nearby customers to be visited without traveling far
away first. We solve the restricted master problem over these graphs, which has
special structure allowing for fast solution.
