Reaching the Elementary Lower Bound in the Vehicle Routing Problem with Time Windows

In this article, we present a comparative study of several strategies that can be applied to achieve the so-called elementary lower bound in vehicle routing problems, that is, the bound obtained when all positive-valued variables in an optimal solution of the linear relaxation of the set-partitioning formulation correspond to vehicle routes without cycles. This bound can be achieved by solving the resource-constrained elementary shortest path probleman N P -hard problemas the pricing problem in a column generation algorithm, but several other strategies can be used to ultimately produce the same lower bound in less computational effort. State-of-the-art algorithms for vehicle routing problems rely on the quality of this lower bound to either bound the size of the search tree in a branch-and-price algorithm or the complexity of an enumeration procedure used to limit the number of variables in the set-partitioning model. We consider several strategies for imposing elementarity that involve ng-paths, strong degree constraints, and decremental state-space relaxation. We compare the performance of these strategies on some selected instances of the vehicle routing problem with time windows. (c) 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 65(1), 88-99. 2015