An exact bidirectional pulse algorithm for the constrained shortest path
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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jun 21, 2020
- Source ID
- 10.1002/net.21960
Entities
People
- Andrés L. Medaglia
- Daniel Duque
- Leonardo Lozano
- Nicolás Cabrera
Organizations
- Northwestern University
- Office of Naval Research Global
- University of Cincinnati
- University of the Andes