A new shortest path algorithm to solve the resource-constrained project scheduling problem with routing from a flow solution

In this study, the definition of a RCPSPR (Resource-Constrained Project Scheduling Problem with Routing) solution from a flow solution of the RCPSP is investigated. This new problem consists in defining a solution of RCPSPR that considers both routing and scheduling and that complies with a RCPSP flow, i.e., a solution where the loaded vehicle moves are achieved between activity i and j with a non-null flow. A shortest path algorithm is proposed to solve this problem with a labeling dynamic approach where a label provides all of the information about a solution, including the objective function, the system state and the remaining resources that allow the use of a dominance rule. The system state, described by the label, encompasses both the activities and the vehicle fleet information, including vehicle position and availability dates. Numerical experiments are limited to a comparative study with a proposed linear formulation since no previous publications exist on this problem. A time performance analysis of the proposed algorithm is carried out, proving the efficiency of the algorithm and clearing the way for integration into global iterative optimization schemes that will solve the RCPSPR to optimality.