An exact bidirectional pulse algorithm for the constrained shortest path. Issue 2 (21st June 2020)

• Record Type: Journal Article
• Authors: Cabrera, Nicolás; Medaglia, Andrés L.; Lozano, Leonardo; Duque, Daniel
• Is Part Of: Networks. Volume 76:Issue 2(2020)
• Page Start: 128
• Page End: 146
• Publication Date: 2020-06-21
• Subjects: bidirectional search -- constrained shortest path -- large‐scale networks; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21960
• Languages: English
• ISSNs: 0028-3045

Abstract

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.