Approximate solution of the shortest path problem with resource constraints and applications to vehicle routing problems

Vehicle routing problem (VRP) is a fundamental combinatorial optimization and integer programming problem with several important applications. The VRP is usually solved by using branch-and-bound techniques requiring solving a shortest path problem with resource constraints (SPPRC) and the determination of a lower bound, which can be computed by using column generation. The SPPRC entails finding the minimum cost elementary path in a valuated graph that is subject to constraints on resource consumption. The proposed exact solutions to this hard NP-hard problem require an excessive computation time which increases with the number of resources. In this paper, we propose a new approximate resolution of the SPPRC for acyclic and cyclic graphs. Our method is based on a Lagrangian relaxation of a subset of the constraints and using dominance only on a subset of the resources. This reduces the search space and allows users to efficiently compute solutions used to improve the column generation procedure. Extensive evaluation and comparison to the classical exact method show that the proposed algorithm achieves a good compromise between efficiency and quality of the SPPRC and the VRP solutions. Thus, our method can be used for practical large-scale VRP applications.