An exact bidirectional pulse algorithm for the constrained shortest path

摘要

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.