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.
Funding Information
  • Office of Naval Research Global (N00014‐19‐1‐2329)
  • Universidad de los Andes (Office of Research / 2019‐2020)

This publication has 32 references indexed in Scilit: