Improved Dynamic Programming for the Shortes Path Problem with Resource Constraints in DAG

摘要

In this work, we present the design and implementation of an efficient yet flexible solution framework for the shortest path problem with resource constraints, which is a critical subproblem in a bunch of optimization problems in the airline industry. We especially focus on directed acyclic graph since graphs in our application are acyclic by definition. Several improving strategies have been devised to improve the performance of the classical labeling algorithm based on dynamic programming. We apply the skyline algorithms to speed up the computation of pareto-optimal labels. We improve data locality and computational efficiency of label dominance with a specialized memory management strategy. Bi-directional dynamic programming techniques are also applied to further improve the performance. Numerical experiments on internal benchmark problems show that our implementation is in general an order of magnitude faster than that of the Boost Graph Library.