A Primal Adjacency-Based Algorithm for the Shortest Path Problem with Resource Constraints
针对资源约束最短路径问题，提出一种基于路径邻接划分的精确原始算法，在无环网络上通过迭代搜索解空间，实验表明在车辆与人员调度中优于动态规划方法。
The shortest path problem with resource constraints (SPPRC) is often used as a subproblem within a column-generation approach for routing and scheduling problems. It aims to find a least-cost path between the source and the destination nodes in a network while satisfying the resource consumption limitations on every node. The SPPRC is usually solved using dynamic programming. Such approaches are effective in practice, but they can be inefficient when the network is large and especially when the number of resources is high. To cope with this major drawback, we propose a new exact primal algorithm to solve the SPPRC defined on acyclic networks. The proposed algorithm explores the solution space iteratively using a path adjacency–based partition. Numerical experiments for vehicle and crew scheduling problem instances demonstrate that the new approach outperforms both the standard dynamic programming and the multidirectional dynamic programming methods.