An Exact Algorithm for the Elementary Shortest Path Problem with Resource Constraints

The elementary shortest path problem with resource constraints (ESPPRC) is an NP‐hard problem that often arises in the context of column generation for vehicle routing problems. We propose an exact solution method that relies on implicit enumeration with a novel bounding scheme that dramatically narrows the search space. We embedded our algorithm within a column generation to solve the linear relaxation (root node) of the vehicle routing problem with time windows (VRPTW) and found that the proposed algorithm performs well when compared against state‐of‐the‐art algorithms for the ESPPRC on the well‐known Solomon’s test bed for the VRPTW.