Please use this identifier to cite or link to this item:
https://hdl.handle.net/10316/3958
Title: | An improved solution algorithm for the constrained shortest path problem | Authors: | Santos, Luís Coutinho-Rodrigues, João Current, John R. |
Keywords: | Network routing; Constrained shortest path problem; Exact algorithms | Issue Date: | 2007 | Citation: | Transportation Research Part B: Methodological. 41:7 (2007) 756-771 | Abstract: | The shortest path problem is one of the classic network problems. The objective of this problem is to identify the least cost path through a network from a pre-determined starting node to a pre-determined terminus node. It has many practical applications and can be solved optimally via efficient algorithms. Numerous modifications of the problem exist. In general, these are more difficult to solve. One of these modified versions includes an additional constraint that establishes an upper limit on the sum of some other arc cost (e.g., travel time) for the path. In this paper, a new optimal algorithm for this constrained shortest path problem is introduced. Extensive computational tests are presented which compare the algorithm to the two most commonly used algorithms to solve it. The results indicate that the new algorithm can solve optimally very large problem instances and is generally superior to the previous ones in terms of solution time and computer memory requirements. This is particularly true for the problem instances that are most difficult to solve. That is, those on large networks and/or where the additional constraint is most constraining. | URI: | https://hdl.handle.net/10316/3958 | DOI: | 10.1016/j.trb.2006.12.001 | Rights: | openAccess |
Appears in Collections: | FCTUC Eng.Civil - Artigos em Revistas Internacionais |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
filedfa98392e75f428794de2eb2e8247e64.pdf | 213.08 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
78
checked on Oct 7, 2024
WEB OF SCIENCETM
Citations
67
checked on Oct 2, 2024
Page view(s)
284
checked on Oct 8, 2024
Download(s)
526
checked on Oct 8, 2024
Google ScholarTM
Check
Altmetric
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.