The Resource-Constrained Project Scheduling Problem with Routing (RCPSPR) problem is an integrated problem that extends the Resource-Constrained Project Scheduling Problem. This extension is based on the assertion that the resources used by the activities must be transported by vehicles. The challenge of this paper is to introduce a new modeling of the problem to generalize the transport in the RCPSPR.

The originality of this work rests on the resolution of a 1-to-n transport problem, i.e. a vehicle can simultaneously transport resources requested by different activities. A question then arises on the resources transported but not necessary for the realization of the destination activity. Two behaviors are possible for these resources: 1) to be pickup by a vehicle at the end of the activity with the released resources, 2) to be pickup at any time since they are not necessary for the progress of the activity. These resources must be differentiated from the resources needed and used by each activity in the modeling. The use of a specific flow graph makes it possible to answer this problem.

The proposed approach to solve the RCPSPR problem with these new constraints is based on a new flow graph and on a split algorithm to define the routes of vehicles in the solution. Local search tools are also set up, including pattern recognition within the solutions. The first results are promising since they allow the cost of some solutions to be reduced by almost 15% by considering only the makespan.