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

作者：Sedeno Noda Antonio^*; Alonso Rodriguez Sergio

来源：Applied Mathematics and Computation, 2015, 265: 602-618.

DOI：10.1016/j.amc.2015.05.109

• Constrained shortest paths
• Shortest path algorithms
• Ranking best solutions

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.

• 出版日期2015-8-15