The Pulse Algorithm: A Modular Framework for Hard Shortest Path Variants

Solving practical applications arising on transportation and logistics often involves the solution of underlying large-scale network problems with shortest path structures. Initially, we proposed the pulse algorithm as an exact method for solving shortest paths with side constraints. Later on, we identified other shortest path variants where the same principle behind the pulse algorithm applied. In this talk, we present the pulse algorithm as a framework based on the idea of performing an implicit enumeration of the entire solution space supported by pruning strategies that efficiently discard a vast number of suboptimal solutions. The framework relies on general components that can be easily extended to different routing problems and problem-specific components that can be used as modules. We show our experience on several shortest path variants such as the constrained shortest path, the biobjective shortest path, the elementary shortest path with resource constraints, the orienteering problem with time windows, and the weight-constrained shortest path with replenishment.