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

作者：

Highlights：

• 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.

摘要

•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.

论文关键词：Constrained shortest paths,Shortest path algorithms,Ranking best solutions

论文评审过程：Received 22 August 2014, Revised 20 May 2015, Accepted 24 May 2015, Available online 12 June 2015, Version of Record 12 June 2015.

论文官网地址：https://doi.org/10.1016/j.amc.2015.05.109