Data-Driven Dynamic Programming for Constrained Shortest Paths

Authors:
Preprint
Publisher website
Google Scholar
Abstract
The most successful approaches for solving the Elementary Resource Constrained ShortestPath Problem (ERCSPP) to optimality are based on Dynamic Programming (DP) combinedwith an iterative relaxation strategy. Decremental State Space Relaxation (DSSR) and ng-path relaxation have long been established in the literature as relaxation techniques.In DP algorithms, an effective policy for selecting the next state to extend among the openones is crucial for performance. In a first exploratory work, we showed that machine learningcan be used to identify promising states in DP, Basso and Salani (2026). In particular, if aclassifier is trained to identify dominated states in a given DSSR iteration, it can then beused to estimate the quality of the states generated in the subsequent iteration.Building on this idea, in this work we show that it is possible to efficiently embed such amodel into a state-of-the-art DP algorithm for the ERCSPP and use its predictions to definea data-driven state exploration policy. Although the approach is data-driven, it remainsexact and does not require pre-existing training data. The algorithm has been integratedinto the Pathwyse library and tested on a dataset of multi-resource instances. Comparedwith a node-based extension policy, the proposed approach consistently reduces the numberof explored DP states and, for sufficiently difficult instances, also improves runtime.

This publication has 41 references indexed in Scilit: