In this paper 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 problem - an NP-hard problem - as 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 involves 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.