Name
Abstract | ||
|---|---|---|
A constrained shortest path is a minimum-cost sequence of arcs on a directed network that satisfies knapsack-type constraints on the resource consumption over the arcs. We propose an exact method based on a recursive depth-first search procedure known as the pulse algorithm (PA). One of the key contributions of the proposal lies in a bidirectional search strategy leveraged on parallelism. In addition, we developed a pulse-based heuristic that quickly finds near-optimal solutions and shows great potential for column generation (CG) schemes. We present computational experiments over large real-road networks with up to 6 million nodes and 15 million arcs. We illustrate the use of the bidirectional PA in a CG scheme to solve a multi-activity shift scheduling problem, where the pricing problem is modeled as a constrained-shortest path with multiple resource constraints. |
Year | DOI | Venue |
|---|---|---|
2020 | 10.1002/net.21960 | NETWORKS |
Keywords | DocType | Volume |
bidirectional search,constrained shortest path,large-scale networks | Journal | 76.0 |
Issue | ISSN | Citations |
SP2.0 | 0028-3045 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Nicolás Cabrera | 1 | 0 | 0.34 |
| Andrés L. Medaglia | 2 | 634 | 27.00 |
| Leonardo Lozano | 3 | 0 | 1.69 |
| Daniel Duque | 4 | 21 | 2.01 |