RCPSPR Example

Example of an RCPSPR Solution from a Flow

This web page provide a full description of an RCPSPR solution with detailed steps to illustrate the article:

Philippe Lacomme, Aziz Moukrim, Alain Quilliot, Marina Vinot. A New Shortest Path Algorithm to Solve the Resource-Constrained Project Scheduling Problem with Routing from a Flow Solution. Engineering Applications of Artificial Intelligence, Volume 66, Issue C, Pages 75-86.

The example instance:

The example presented in this page introduces the resolution steps to solve the RCPSPR from a RCPSP solution with a flow network. The example introduced below is composed of 3 activities and two dummy activities modeling the depot. The duration of the activities is given in Table 1 and the distance matrix is introduced in Table 2. For the routing part, two vehicles are available, the vehicle 1 with a capacity equal to 3 and the vehicle 2 with a capacity equal to 2. Both vehicles are assumed to have a traveling speed of 1.

Table 1:Information on the activities
Activity	Duration	Resource requirement	Successors
0	0	/	1, 2, 3, 4
1	2	3	4
2	10	2	3, 4
3	5	2	4
4	0	/	/

Table 2:Matrix distance between the activities
/	0	1	2	3	4
0	0	2	2	3	0
1	2	0	2	3	2
2	2	2	0	5	2
3	3	3	5	0	3
4	0	2	2	3	0

Let us assume that a specific algorithm solves the RCPSP defining a flow-network solution in Fig. 1.

Fig 1: Activity-on-node (AON)-flow network example

Let us define the graph T_φ(U,V,E,F) on this solution, with U={0,0,1,1,2,3}, V={1,2,2,3,4,4}, |E|=6, |F|=20 introduced in Fig. 2.

Fig 2: Graph T_φ(U,V,E,F)

For the first step, the graph is initialized with a label L_# leading to two labels stored on node 1⁺ and 2⁺ corresponding to activity 0. In the second step, all the labels on node 2⁺ are propagated on node 2^-. In this step two labels are created. In the third step, the labels on node 2^- are propagated on nodes 1⁺,2⁺,3⁺,4⁺ with a feasibility check leading to 10 labels.

At the end of the algorithm, when all labels have been propagated, a set of non-dominated solutions are obtained and the solutions minimizing the makespan are stated to be optimal since they minimize the objective function. An optimal solution (solution minimizing the makepsan) is introduced in Fig. 3 with the trip of vehicle 1 in black and the trip of vehicle 2 in red.

Fig 3: Solution of the RCPSPR with the detailed trips of the two vehicles

The solution in Fig. 3 is obtained at the end of the shortest path algorithm. The steps and the labels leading to this solution are detailed in Fig.4.

Fig 4: The shortest path in the graph T_φ(U,V,E,F) leading to solution in Fig. 3

The Gantt of Figure 5 represents the solution in Fig. 3 where both scheduling and routing are represented.

Fig 5: Gantt solution with both scheduling and transport planning