A Multiple-Starting-Path Approach to the Resource-Constrained kth Elementary Shortest Path Problem. (22nd March 2015)

• Record Type: Journal Article
• Authors: Tae, Hyunchul; Kim, Byung-In
• Other Names: Ngoduy Dong Academic Editor.
• Is Part Of: Mathematical problems in engineering. Volume 2015(2015)
• Publication Date: 2015-03-22
• Subjects: Engineering mathematics -- Periodicals; 510.2462
• DOI: 10.1155/2015/803135
• Languages: English
• ISSNs: 1024-123X

Abstract

Abstract : 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 k th elementary shortest path problem (RCKESPP) is a generalization of the RCESPP that aims to determine the k th 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.