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.Keywords
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:
- Exact Solution of the Evasive Flow Capturing ProblemOperations Research, 2018
- Solving the Orienteering Problem with Time Windows via the Pulse FrameworkComputers & Operations Research, 2015
- Acceleration strategies for the weight constrained shortest path problem with replenishmentOptimization Letters, 2014
- A New Approach for Air Cargo Network PlanningTransportation Science, 2009
- The network design problem with relaysEuropean Journal of Operational Research, 2007
- Column Generation2005
- Improved preprocessing, labeling and scaling algorithms for the Weight‐Constrained Shortest Path ProblemNetworks, 2003
- Solving Real-World Linear Programs: A Decade and More of ProgressOperations Research, 2002
- Algorithms for the Weight Constrained Shortest Path ProblemInternational Transactions in Operational Research, 2001
- Performance of various computers using standard linear equations softwareACM SIGARCH Computer Architecture News, 1992