An enhanced K-SP algorithm with pruning strategies to solve the constrained shortest path problem

• A new exact algorithm for the constrained shortest path problem is presented.
• Extensive experiments comparing the behavior of the new scheme and the recent best method from the literature are provided.
• The proposed approach solves the constrained shortest path problem in USA road networks containing millions of nodes and arcs.

We propose an exact method to solve the constrained shortest path (CSP) problem. The new approach takes advantage of the binary partition strategy of a recent K shortest paths (K-SP) algorithm that allows posing numerous additional path constraints in the model without extra difficulty. We adapt and incorporate several pruning strategies from the literature on the CSP problem in this scheme and obtain a robust and scalable algorithm. The method is compared with the current best algorithm to solve the CSP problem and produces significant speedups in a wide range of network configurations. An example is given where the CSP problem is solved in road networks containing a million nodes and arcs.