Heuristics based on partitioning the space of solutions to the least path problem with resource constraint in multiphase algorithms

The Shortest Path with Resource Constraints Problem (SPPRC) consists of determining, in a cost-oriented graph with multiple resource consumptions associated with the arcs, a minimum cost path between a source and a destination whose cumulative consumption respects pre-established limits for each resource along the route. Despite its simple formulation, SPPRC is NP-difficult and occupies a central role in column generation schemes applied to vehicle routing problems, crew scheduling and several other applications in logistics and transportation, in which it emerges as a pricing sub-problem. The efficiency with which it is resolved determines, to a large extent, the overall performance of these exact schemes.

Classical approaches to SPPRC are based on dynamic labeling programming, in which labels representing partial paths are propagated across the vertices of the graph and discarded by means of dominance rules, often combined with elementary relaxations, pruning by reverse dynamic programming, and bidirectional searching. Despite the advances, the number of manipulated labels grows rapidly in larger instances, which motivates the search for more scalable algorithms.

Recently, Himmich, El Hallaoui, and Soumis (2024) proposed a multiphase dynamic programming algorithm that partitions the solution space, progressively exploring subsets of paths with common structural characteristics