A Multiple-Starting-Path Approach to the Resource-Constrained kth Elementary Shortest Path Problem

作者：Tae Hyunchul; Kim Byung In^*

来源：Mathematical Problems in Engineering, 2015, 2015: 803135.

DOI：10.1155/2015/803135

The resource-constrained elementary shortest path problem (RCESPP) aims to determine the shortest elementary path from the origin to the sink that satisfies the resource constraints. The resource-constrained kth elementary shortest path problem(RCKESPP) is a generalization of the RCESPP that aims to determine the kth shortest path when a set of k-1 shortest paths is given. To the best of our knowledge, the RCKESPP has been solved most efficiently by using Lawler's algorithm. This paper proposes a new approach named multiple-starting-path (MSP) to the RCKESPP. The computational results indicate that the MSP approach outperforms Lawler's algorithm.

• 出版日期2015