Name
Title | ||
|---|---|---|
Acceleration strategies for the weight constrained shortest path problem with replenishment. |
Abstract | ||
|---|---|---|
The weight constrained shortest path problem with replenishment (WCSPP-R) generalizes the constrained shortest path problem (CSP) and has multiple applications in transportation, scheduling, and telecommunications. We present an exact algorithm based on a recursive depth-first search that combines and extends ideas proposed in state-of-the-art algorithms for the CSP and the WCSPP-R. The novelty lies in a set of acceleration strategies that significantly improves the algorithm's performance. We conducted experiments over large real-road networks with up to 6 million nodes and 15 million arcs, achieving speedups of up to 219 times against the state-of-the-art algorithm. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s11590-014-0742-x | Optimization Letters |
Keywords | Field | DocType |
Constrained shortest path problem,replenishment,large-scale networks | Canadian traveller problem,Mathematical optimization,Shortest path problem,Constrained Shortest Path First,Yen's algorithm,Shortest job next,Shortest Path Faster Algorithm,Mathematics,Euclidean shortest path,K shortest path routing | Journal |
Volume | Issue | ISSN |
8 | 8 | 1862-4472 |
Citations | PageRank | References |
3 | 0.42 | 9 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Manuel A. Bolívar | 1 | 6 | 1.17 |
| Leonardo Lozano | 2 | 59 | 4.52 |
| Andrés L. Medaglia | 3 | 28 | 2.76 |