Joris Vidé

Cindy Romain

Christine Feillet-Coudray

Béatrice Bonafos

Jean-Paul Cristol

Gilles Fouret

Jean-Max Rouanet

Sylvie Gaillet

Assessment of potential toxicological aspects of dietary exposure to silicon-rich spirulina in rats

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.


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

Keywords:

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 𝑖 and 𝑗 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. 2 3 4 Transport operation (load) Transport operation (unload)

Introduction

Although supply chain decision problems are interrelated, they are often solved sequentially. However, to achieve a highly effective overall system that complies with customers' expectations, coordination among the different stages in the supply chain is necessary. Consequently, the integration of scheduling and routing problems has received increasing attention in the last decade [START_REF] Moons | Integrated production scheduling and vehicle routing decisions at the operational decision level: A review and discussion[END_REF]. Several papers focusing on integrated problems were recently published, including but not limited to [START_REF] Zhang | An integrated strategy for a production planning and warehouse layout problem: Modeling and solution approaches[END_REF] who deal with the real-world production warehousing case, or [START_REF] Saglam | Integrated multiproduct batch production and truck shipment scheduling under different shipping policies[END_REF] who focus on batching decisions and different shipping scenarios. In supply chain management, in addition to the integration of production planning and distribution decisions, an effective management of the resources is essential to preserve the competitiveness of companies. This paper focuses on a new integrated problem based on the resourceconstrained project scheduling problem with routing constraints.

Resource-constrained project scheduling problem

The Resource-Constrained Project Scheduling Problem (RCPSP) consists of a set of activities, 𝑉 = {0, . . . , 𝑛 + 1 }, with durations, 𝑝 = (𝑝 0 , . . . , 𝑝 𝑛+1 ), where 𝑛 is the number of nondummy activities plus two dummy activities denoted 0 and 𝑛 + 1, which define the "project start" and the "project end", respectively. The set of non-dummy activities is identified 1 Corresponding author. e-mail addresses: placomme@isima.fr (P. Lacomme), aziz.moukrim@utc.fr (A. Moukrim), alain.quilliot@isima.fr (A. Quilliot), marina.vinot@isima.fr (M. Vinot) by 𝐴 = {1, … , 𝑛} and some activities are related by precedence constraints. The precedence constraints can be induced by the definition of predecessors in the problem definition (one activity 𝑗 cannot start before all its predecessors have been achieved) and by definition of constraints due to the resource exchanges. A solution of the RCPSP is fully defined by the activity start times 𝑆 𝑖 and by a resource supply that complies with the activity requirements. The number of project resources is denoted as 𝑞 and the set of resource capacities is 𝑅 = {𝑅 1 , . . . , 𝑅 𝑞 }, where 𝑅 𝑘 ∈ ℕ . The activity resource requirement 𝑏 𝑖𝑘 ∈ ℕ means that activity 𝑖 requires 𝑏 𝑖𝑘 ≤ 𝐵 𝑘 resource units of resource 𝑘 during its execution.

RCPSPR definition

The RCPSPR (Resource-Constrained Project Scheduling Problem with Routing) is an extension of the RCPSP where resources are transported from one activity to another using a vehicle. The problem consists of solving both the activity scheduling problem and the vehicle routing problem. This paper focuses on the case of one resource, 𝑞 = |𝑅| = 1, and assumes, without loss of generality, that 𝑏 𝑖𝑘 = 𝑏 𝑖 . The schedule length 𝐶 𝑚𝑎𝑥 (i. e., the project makespan) is defined by the end of the last transport operation from one activity to the dummy activity 𝑛 + 1.

The routing part consists of scheduling trips with a set of vehicles 𝑇 = {1, . . . , 𝑣 } sorted in descending order of capacity 𝑐 𝑢 , 𝑢 ∈ {1, … , 𝑣}. A loaded transportation time 𝑡 𝑖𝑗 𝑢𝑥 is defined from activity 𝑖 to 𝑗 with a vehicle 𝑢 loaded with 𝑥 units of resources. An unloaded transportation time 𝑒 𝑖𝑗 𝑢 is also defined from activity 𝑖 to 𝑗 with an empty vehicle 𝑢. An activity 𝑗 is defined by a starting time 𝑆 𝑗 with a completion time 𝐶 𝑗 = 𝑆 𝑗 + 𝑝 𝑗 and resource supplies that meet the requirement 𝑏 𝑗 . An activity can only start when a total amount 𝑏 𝑗 of resources is transferred from activity i to activity 𝑗.

The resources transferred from activity 𝑖 to 𝑗 are modeled by a transport operation 𝑇 (𝑖,𝑗,𝑢,𝑥) = (𝑃 (𝑖,𝑗,𝑢,𝑥) , 𝐷 (𝑖,𝑗,𝑢,𝑥) ), which is fully defined by a pickup operation 𝑃 (𝑖,𝑗,𝑢,𝑥) and a delivery operation 𝐷 (𝑖,𝑗,𝑢,𝑦) . These two operations are defined by:  an arrival time and a departure time of the vehicle, 𝐴 (𝑖,𝑗,𝑢,𝑥) and 𝐵 (𝑖,𝑗,𝑢,𝑥) , respectively;  a quantity of resource (pickup or deliver) 𝑥;  a vehicle assigned to the transport operation 𝑢.

The problem consists in a proper coordination of scheduling and routing operations to minimize the makespan 𝐶 𝑚𝑎𝑥 (Fig. 1). A routing solution is defined as a set of trips, and each trip is an ordered sequence of loaded transport operations. The earliest starting time of an activity is the latest arrival time of the last vehicle assigned to the transportation of resources required by the activity.

In Fig. 1, an extended Gantt diagram displays a solution with the earliest starting times and the durations of three activities, plus the trips of two vehicles with 𝑐 1 = 3 and 𝑐 2 = 2. For example, in Fig. 1, activity 1 has an earliest starting time equal to the arrival time 𝐴 (0,1,1,3) = 2. For activity 3, the earliest starting time is equal to the maximum value between the arrival time of vehicle 2 with two units of resource, 𝐴 (1,3,2,2) = 7 and the earliest completion time of activity 2, 𝐶 2 = 16, due to a precedence constraint. Let us note that the earliest starting time of activity 2, is the latest arrival time of the vehicles (vehicle 1), meaning that two delivery operation are required to define the starting time of activity 2.

P D B (2,4,1,2) A (2,4,1,2) T (2,4,1,2) B (3,4,1,2) P A (3,4,1,2) D T (3,4,1,2)
Vehicle waiting time

T (0,2,2,1) A (0,2,2,1) D B (1,3,2,2) P B (1,2,1,1) A (1,3,2,2) D T (1,3,2,2)
Vehicle 1 Vehicle 2

Figure 1. Coordination between routing and scheduling

In this example, vehicle 2 transports one resource from activity 0 to 2 (𝑇 (0,2,2,1) ) and then makes an unloaded move to activity 1 in order to load and transport two resources to activity 3 (𝑇 (1,3,2,2) ). Once the resources are delivered at time 7, vehicle 2 goes back to the depot and arrives at time 10. Figure 2 shows that two deliveries are performed on activity 2, the first delivery operation permits to transport one unit of resource from activity 0 with the vehicle 2 and the second delivery operation permits to transport one unit from activity 1 thanks to vehicle 1. The delivery operation are defined by both a location (activity) and a quantity of resource. The resource delivered at one activity are assumed to be in an input buffer on the activity. Such situation occurs for activity 2, where one unit of resource waits from time 2 to time 6 in the input buffer of activity 2. At time 6, activity 2 can start thanks to the transport operation 𝑇 (1,2,1,1) . This example is used throughout the paper in order to illustrate the proposed algorithm.

D P

P A (3,4,1,2) D 7 D A (1,3,2,2) D D Legend: Trip of vehicle 1 B (0,2,2,1) P Trip of vehicle 2 B (2,4,1,2) A (2,4,1,2) T (0,2,2,1) T (0,1,1,3) T (1,3,2,2) T (1,2,1,1) T (2,4,1,2) T (3,4,1,2) 1 S 1 C 1 S 2 S 3 =C 2 C 3 21 Vehicle 1 Vehicle 2
Figure 2. Impact of coordination on the ressource management

Related problems

Routing constraints are involved in numerous scheduling problems including, for example, the flexible job-shop scheduling problem with transport (Zhang et al., 2012b), the jobshop with transport [START_REF] Knust | Shop-Scheduling Problems with Transportation[END_REF][START_REF] Lacomme | Job-shop based framework for simultaneous scheduling of machines and automated guided vehicles[END_REF][START_REF] Afsar | Resolution of a Job-Shop problem with transportation constraints: a master/slave approach[END_REF], the Flexible Manufacturing Systems (FMS) [START_REF] Caumond | An MILP for scheduling problems in a FMS with one vehicle[END_REF], the HSP (Hoist Scheduling Problem) [START_REF] Honglin | A new method of cyclic hoist scheduling for multi-recipe and multi-stage material handling processes[END_REF][START_REF] Adnen | An efficient new heuristic for the hoist scheduling problem[END_REF][START_REF] Chtourou | A hybrid algorithm for the cyclic hoist scheduling problem with two transportation resources[END_REF], and the RCPSP with transport [START_REF] Quilliot | Resource Constrained Project Scheduling with Transportation Delays[END_REF]. Numerous scheduling approaches take advantage of the disjunctive graph introduced by [START_REF] Roy | Les problèmes d'ordonnancement avec contraintes disjonctives[END_REF], which has been extended to tackle transport constraints (see [START_REF] Lacomme | A disjunctive graph for the job-shop with several robots[END_REF] and Zhang et al. (2012a)), where vertex models transport operations and disjunctive arcs are added between operations that require the same resource (vehicle). The coordination between transport and scheduling can be achieved in two possible ways depending on the objective. The first one consists of the explicit modeling of transport from one location to another, and the second one consists in modeling only transport delay (minimal time-lags between machines). Maximal time-lags between activities can model a time window between activities and are used in pickup and delivery resolution approaches for trip evaluation [START_REF] Cordeau | A tabu search heuristic for the static multi-vehicle dial-a ride problem[END_REF][START_REF] Firat | Analysis of the dial-a-ride problem of Hunsaker and Savelsbergh[END_REF].

Transport modeling depends on the vehicle capacity, and a trip is considered to be an ordered sequence of pickup/delivery operations including loaded/unloaded transport operations.

Depending on the problem, the transportation time can be job/vehicle load-dependent and can be denoted 𝑡 𝑖𝑗 𝑥 for a transport from activity 𝑖 to 𝑗 with 𝑥 resources. Similarly, 𝑡 𝑖𝑗 0 (normally denoted 𝑒 𝑖𝑗 = 𝑡 𝑖𝑗 0 ) denotes the duration of an unloaded transport operation. If the transportation times are vehicle-dependent, they can be noted 𝑡 𝑖𝑗 𝑢𝑥 where 𝑢 is the vehicle.

Proposition

RCPSPR modeling

Several formulations were introduced for the RCPSP, including [START_REF] Alvarez-Valdés | The project scheduling prolyhedron: Dimension, facets and lifting theorems[END_REF], [START_REF] Pritsker | Multi-project scheduling with limited resources: a zero-one programming approach[END_REF], Pritsker and Watters (1968) and Dauzère-Pérès and Lasserre, (1995), and more recently, the flow formulation of [START_REF] Artigues | Insertion for static and dynamic RCPSP[END_REF] that defines a solution of the RCPSP using an activityon-node (AON)-flow network defining a so called 𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) (Fig. 3). In this graph, there is a vertex in 𝑉 for each activity. In addition, the set 𝐸 of resource arcs represents the number of units of the resource directly transferred between two activities.

The arc in Fig. 3 between node 0 and 𝑖 1 models a resource transfer of 𝜑 0,𝑖 1 units of the resource between activity 0 and 𝑖 1 . Every arc 𝑒 ∈ 𝐸 connects a vertex in 𝑈 to a vertex in 𝑉 to model a loaded transport operation, |𝐸| = 𝑛 𝜑, and every arc 𝑓 ∈ 𝐹 connects a vertex from 𝑉 to a vertex 𝑈 to model an unloaded transport operation (dotted arcs in Fig. 5). The required arcs (arcs modeling loaded transport operations) are defined by a couple (𝜑 𝑖𝑗 , 𝑡 𝑖𝑗 ) where 𝜑 𝑖𝑗 is the number of resources to transport from 𝑖 to 𝑗 and where 𝑡 𝑖𝑗 is the transportation time. The valuation of a non-required arc (an arc modeling an unloaded transport operation) is defined by (0, 𝑡 𝑗𝑣 ). For convenience, two global dummy nodes are introduced, the first one referred to as # to represent the starting time of the first transport operation, and the second one * , the finishing time of the last transport operation. A solution of the RCPSPR is composed of a set of trips assigned to vehicles, knowing that a trip is composed of an ordered set of required arcs and a deadheading path from the destination node of one required arc to the origin node of the next required arc in the trip:  First, from this point of view, the problem to solve falls into the family of arc routing problems, including, for example, the Chinese Postman Problem (CPP) first introduced by the mathematician [START_REF] Kwan | Graphic programming using odd or even points[END_REF], the Rural Postman Problem (RPP) [START_REF] Orloff | A fundamental problem in vehicle routing[END_REF], and the Capacitated Arc Routing Problem (CARP), that was introduced by [START_REF] Golden | Capacitated arc routing problems[END_REF]. Contrary to the CARP, where the vehicle load increases during the trip, the pickup/delivery characteristics lead to a specific arc routing problem with no trip infeasibility due to vehicle capacity.  Second, the problem can be solved using a resolution approach based on a labeling algorithm with an efficient label processing procedure and a specific label definition that makes it possible to obtain a solution of a resourceconstrained shortest path problem.

ϕ i2,ip+2 0 i 1 i p+1 i 2 i p+2 i p i p+n i p+. ... n+1 ϕ 0,i1 ϕ 0,ip ϕ 0,i2 ϕ i1,ip+1
0 i 1 i 1 i p+2 i p+2 i p+. i 2 i p+2 Pickup Delivery i p+2 ... ... n+1 0 i 2 (ϕ , t ) (0 , t ) i 1 i p+1 i 1 i p+1 i p+1 i 2 i p i p+n i p+2 n+1 (ϕ ,t )
An optimal solution of the RCPSPR defined by the flow can be obtained by execution into 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹) of a shortest path algorithm with resource constraints between the global dummy nodes # and * . The shortest path is defined by an ordered sequence of transport operations with alternation between loaded transport and unloaded transport operations.

RCPSPR solution defined from a flow

A flow solution defines an acyclic graph 𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) where the flow arcs can make it possible to define the transport operations with the quantity of resource. The flow is assumed to comply with the definition of [START_REF] Artigues | Insertion for static and dynamic RCPSP[END_REF], and the input/output flow of an activity is assumed to be equal to its required capacity with flow conservation. A flow 𝜑 𝑖𝑗 between activity 𝑖 and activity 𝑗 can exceed the vehicle capacity and can require several transport operations due to the vehicle capacity constraints (𝑐 𝑣 ).

The new algorithm dedicated to the resource-constrained shortest path problem is defined on a non-ordered set of transport operations and provides an optimal set of trips to build both a routing solution and a scheduling solution that consists of:  computing the earliest starting times 𝑆 𝑖 of the activities;  defining the assignment of vehicles to transport operations;  ordering the transport operations for each vehicle to define a trip with the departure time and arrival time of the vehicle for each transport operation.

The transport operations are divided into two categories with:  Loaded transport operation 𝑇 𝑖,𝑗, * ,𝜑 𝑖𝑗 from activity 𝑖 to 𝑗, modeled by an arc from 𝑖 to 𝑗 where the valuation is composed of the flow 𝜑 𝑖𝑗 (that must be transported from activity 𝑖 and activity 𝑗) and the transportation time 𝑡 𝑖𝑗 .  Unloaded transport operation, modeled by an arc (dotted arcs in Fig. 5) valuated with 0 for the flow and 𝑡 𝑖𝑗 for the transportation time.

A New Shortest Path Algorithm and its application to arc routing

The resource-constrained shortest path problem considered in this paper makes it possible to define an optimal solution of the RCPSPR in the graph 𝑇 𝜑 (𝑈, 𝑉, 𝐸, 𝐹). Each solution (Fig. 6) is composed of a set of trips (modeled by a path in 𝑇 𝜑 (𝑈, 𝑉, 𝐸, 𝐹)

from node # to node * ) passing through every arc with a nonnull flow. The solution is optimal if it minimizes the arrival time of all the vehicles on the node * with respect to all the constraints. Figure 6 shows two trips assigned to two vehicles. The trip of vehicle 1 is composed of six transport operations, whereas the trip of vehicle 2 consists of three transport operations. These two trips are interrelated due to some activities in both trips, e.g. activity 𝑖 𝑝+2 . The two delivery nodes 𝑖 𝑝+2 must be scheduled before the two pickup nodes 𝑖 𝑝+2, and the departure times of the two loaded transport operations from the two pickup nodes 𝑖 𝑝+2 are greater or equal to the completion time of the activity 𝑖 𝑝+2 . Each partial solution (also denoted for convenience as a solution) is modeled by a path represented by a label 𝐿(𝑓, 𝑆, 𝑅) i.e., a data structure that provides all of the information about the solution such as the objective function, the system state and the remaining resources that allow the use of a dominance rule. A partial solution is defined by a label where all the flows between operations have not yet been transported by vehicles, meaning that all activities are not yet scheduled. Conversely, a final solution is a label where all flows have been transported, i.e., a label where all activities have been scheduled.

0 i 1 i 1 i p+2 i p+2 i p+.
For each node 𝑖 of the graph 𝑇 𝜑 (𝑈, 𝑉, 𝐸, 𝐹), 𝑌 𝑖 is the ordered set of unprocessed labels, i.e., paths that have not been extended along all arcs (𝑖, 𝑗) leading to feasible paths. The set 𝑃 𝑖 contains labels that are required to be kept, i.e., 𝑃 𝑖 defines a set of nondominated labels on node 𝑖. The labels are sorted into nondecreasing order of the total loaded transportation time 𝑡 𝑖𝑗 from activity 𝑖 to 𝑗 not yet serviced according to the required flow, and 𝑍 𝑖 is the restriction of 𝑌 𝑖 to the 𝑁 𝐿 first labels.

For each node 𝑖, the distance 𝐷[𝑖] is the longest path in terms of the number of arcs from 𝑖 to the dummy node * . In other words, 𝐷[𝑖] is a distance between a partial solution and a solution of the problem and is representative of the computational effort required to obtain a final solution. The distances are preprocessed and are directly used in the following algorithm.

The use of a dominance rule is optional in the sense that the algorithm otherwise enumerates all feasible paths starting at node #, but dominance is crucial in the design of one efficient resource-constrained shortest path algorithm to identify paths that do not need to be extended.

The outline of the resource-constrained shortest path algorithm for solving the RCPSPR is presented in Algorithm 1. The problem consists of computing a minimum-cost feasible path ending at the global dummy nodes * where a set of nondominated labels (each label modeling a partial solution) is stored. The algorithm starts with one initialization step (lines 12-15) where a label 𝐿 0 is stored on the global dummy node # (that models the depot node of vehicles). Lines 16-34 define the outer loop where labels are propagated along feasible-path constraints.

The algorithm terminates when no further unprocessed label on the node exists, i.e., when all labels giving the non-dominated paths from vertex # to * have been created, which is defined by an empty queue Λ. The algorithm selects a final solution 𝑆𝑜𝑙 (line 35) that minimizes the objective function 𝑓. The procedure 𝐼𝑁𝑆𝐸𝑅𝑇_𝐿𝐴𝐵𝐸𝐿(𝐿 𝑤 , 𝑍 𝑛𝑜𝑑𝑒_𝑗 ) (line 24) carries out the insertion of the label 𝐿 𝑤 in the ordered set of unprocessed labels 𝑍 𝑛𝑜𝑑𝑒_𝑗 that take the maximum number of unprocessed labels authorized on each node 𝑁 𝐿 into account. Then, with the function 𝐴𝑃𝑃𝐿𝑌_𝐷𝑂𝑀𝐼𝑁𝐴𝑁𝐶𝐸(𝐿 𝑤 , 𝑍 𝑛𝑜𝑑𝑒_𝑗 ) (line 25), all labels on 𝑍 𝑛𝑜𝑑𝑒_𝑗 that are dominated by 𝐿 𝑤 are removed from 𝑍 𝑛𝑜𝑑𝑒_𝑗 .

The 𝐶𝐻𝐸𝐶𝐾_𝑆𝑂𝐿(𝐿 𝑤 , 𝑈𝐵 ) (line 27) function updates the upper bound of the problem for each new solution (defining a path through every arc with a non-null flow) on the final node. Finally, the best solution at the end of the algorithm is given by the function 𝐵𝐸𝑆𝑇_𝑆𝑂𝐿 (𝑇 𝜑 ) (line 35) from the best final label in 𝑇 𝜑 .

The resource-constrained shortest path algorithm must encompass the management of both the availability of vehicles and that of activities, and includes the following features:  a label definition to encompass the system state;  creation of the initial label;  a propagation rule to create a new label;  a label feasibility check;  a dominance rule to save only non-dominated labels on the node.  a label propagation selection rule required to choose the next path (next label) to be extended.

Let us define a function that makes it possible to assign a number in [1. . 𝑛 𝜑 ] to each arc.

β: 𝑒 ∈ 𝐸 → [1. . 𝑛 𝜑 ] , β(𝑒 ∈ 𝐸 ) = 𝑖 ∀𝑒 1 ∈ 𝐸, ∀𝑒 2 ∈ 𝐸, 𝑒 1 ≠ 𝑒 2 , β(𝑒 1 ) ≠ β(𝑒 2 ).
Another notation is also used to identify the pickup node and the delivery node of each numbered arc 𝑖 𝜖 [1. . 𝑛 𝜑 ]. Let us denote 𝑖 + as the position number of the pickup node in graph 𝐺 and 𝑖 -as the position of the delivery node of arc 𝑖. Let us define λ as the activity number where a pickup operation (resp. delivery operation) is achieved from position 𝑖 + (resp. 𝑖 -) such that 𝜆(𝑖 -) or 𝜆(𝑖 + ) gives the activity where the operations are achieved.

Label definition

A label 𝐿 = (𝑓, 𝑆, 𝑅) represents a partial or final solution and 𝐿 𝑖 𝑗 denotes the 𝑖 𝑡ℎ label on node 𝑗 = 𝑗 -or 𝑗 = 𝑗 + , which is composed of three parts:  The objective function value of the solution, i. e., the maximal completion time of the vehicles.  The system state 𝑆 that encompasses the vehicle fleet and the activities. The system state can be described by: -a 3𝑣-uplet 𝑉

Creation of the initial label

An initial label 𝐿 is stored on node # and propagated to all nodes 𝑗 = 𝑗 + , where 𝜆(𝑗 + ) = 0. To comply with the following definition, all the values are initialized: The new label 𝐿 𝑞 𝑗 for node number 𝑗 = 𝑖 -is defined from the label 𝐿 𝑝 𝑖 𝑖 = 𝑖 + using the vehicle 𝑢 with the following updates: If 𝑏 𝑞𝑗 𝑅,𝜆(𝑗) = 0, the propagation rule also updates all the starting times of the successors of activity 𝜆(𝑖), i.e., ∀𝑠 ∈ 𝑠𝑢𝑐𝑐(𝜆(𝑖)), 𝑆 𝑞𝑗 𝑠 = 𝑚𝑎𝑥(𝑆 𝑝𝑖 𝑠 ; 𝑆 𝑞𝑗 𝜆(𝑗) + 𝑝 𝜆(𝑗) ). This update ensures that precedence constraints hold. For the label 𝐿 𝑝 𝑖 , all assignments to vehicles are investigated, leading to 𝑣 labels. These labels are included or not depending on the set of non-dominated labels previously stored on the node 𝑗 in 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹).

∀𝑢 ∈ 𝑇, 𝑃 1𝑗 𝑢 = 0 ∀𝑢 ∈ 𝑇, 𝐴 1𝑗 𝑢 = 0 ∀𝑢 ∈ 𝑇, 𝐵 1𝑗 𝑢 = 0 ∀𝑘 ∈ 𝑉 * , 𝑆 1𝑗 𝑘 = -∞
𝑃 𝑞𝑗 𝑢 =
Propagation rule for a label on a delivery node (arc modeling an unloaded transport operation)

A propagation function defined by 𝑓: L  T → R that makes the generation of a new label 𝐿 𝑞 𝑗 - from one label 𝐿 𝑝 𝑖 + and an unloaded transport operation defined by (0, 𝑡 𝑚𝑘 )/𝑚 = 𝜆(𝑗 -) and 𝑘 = 𝜆(𝑖 + ) possible.

The new label 𝐿 𝑞 𝑗 with 𝑗 = 𝑖 + is defined from the label 𝐿 𝑝 𝑖 , where 𝑖 = 𝑗 -using vehicle 𝑢 with the following updates:

𝑃 𝑞𝑗 𝑢 = 𝜆(𝑗) 𝐴 𝑞𝑗 𝑢 = 𝐵 𝑝𝑖 𝑢 + 𝑒 𝜆(𝑖),𝜆(𝑗)
𝐵 𝑞𝑗 𝑢 = 𝑚𝑎𝑥 (𝐴 𝑞𝑗 𝑢 ; 𝑆 𝑝𝑖 𝜆(𝑗) + 𝑝 𝜆(𝑗) )

𝑓 𝑞𝑗 = 𝑚𝑎𝑥 (𝑓 𝑝𝑖 ; 𝐴 𝑞𝑗 𝑢 )

Label feasibility check

The first and the second conditions detailed below only hold for label 𝐿 𝑞 𝑖stored at delivery node 𝑖 = 𝑖 -propagated to a pickup node 𝑗 = 𝑗 + . Both conditions are linked to the resource state. The first condition takes advantage of the flow. If the flow 𝜑 𝑞𝑖 𝑅,𝑗 = 0, i.e., all resources between 𝜆(𝑗 + ) and 𝜆(𝑗 -) were transported, then an unloaded transport operation to activity 𝜆(𝑗 + ) must be forbidden. The second condition holds since an unloaded transport operation can only be achieved to an activity 𝜆(𝑗 + ) previously scheduled, i.e., for which all the resources were delivered 𝑏 𝑞𝑖 𝑅,𝜆(𝑗) = 0. If 𝑏 𝑞𝑖 𝑅,𝜆(𝑗) ≠ 0, no unloaded transportation operation to 𝜆(𝑗 + ) must be scheduled.

Dominance rule

Whenever one or several new labels are created (by the propagation rule), they are compared for dominance with the non-dominated labels that are stored at the destination node. On the other hand, each label 𝐿 𝑘 𝑖 |𝐿 𝑘 𝑖 ≪ 𝐿 𝑝 𝑖 can be removed from node 𝑖. The dominance rule limits the number of labels stored at each node to a subset of labels while maintaining algorithm optimality. An additional time-saving approach consists in limiting the maximal number 𝑁 𝐿 of labels stored on each node. Such restrictions, in addition to the dominance rule, can strongly reduce the CPU time but can yield to a sub-optimal final solution.

Label propagation selection rule

The algorithm relies on a queue referred to as Λ that supports the following operations:  Push (Λ, i): adds the node number 𝑖 to the queue and guaranties that each node number 𝑖 cannot be added to the queue more than once;  Pop (Λ): removes the node with the minimal 𝐷[𝑖] and the largest number of labels.

By adopting the Λ order for the node selection (line 17), the algorithm favors propagation of labels that are more prone to create a solution within an efficient time delay.

Example

In this section an example is introduced in order to build a graph 𝑇 𝜑 = (𝑈, 𝑉, 𝐸, 𝐹) to illustrate some steps of the algorithm. The example introduced below is composed of three activities and two dummy activities modeling the depot where four resources are available. 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, vehicle 1 with a capacity of 3 and vehicle 2 with a capacity of 2. Both vehicles are assumed to have a traveling speed of 1.

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 flow problem defining a flow-network solution 𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) (Fig. 7) and let us define the graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹) on this solution, where 𝑈 = {0,0,1,1,2,3}, 𝑉 = {1,2,2,3,4,4}, |𝐸| = 6, and |𝐹| = 20, introduced in Fig. 8. For the first step (Fig. 8), the graph is initialized with a label 𝐿 # leading to two labels stored on node 1 + and 2 + , corresponding to activity 0 as 𝜆(1 + ) = 0 and 𝜆(2 + ) = 0. The two labels 𝐿 1 1 +

and 𝐿 1 2 + are both equal to:

System state : S Resource state : R

f P ij , P ij 1 2 A ij , A ij 1 2 B ij , B ij 1 2 S ij , S ij , S ij , S ij 1 2 3 4
(0|0,0,0,0,0,0|0,-∞,-∞,-∞,-∞|1,3,1,2,2,2|0,3,2,2,4)

ϕ ij , ϕ ij , ϕ ij , ϕ ij , ϕ ij , ϕ ij R,1 R,2 R,3 R,4 R,5 R,6 b ij , b ij , b ij , b ij , b ij R,0 R,1 R,2 R,3 R,4
with respect to the label definition, 𝑖 = 1 and 𝑗 = {1 + , 2 + }. The queue is equal to

Λ = [1 + , 2 + ]. 0 2 (1,2) 1 + 1 - L 1 + 1 1 2 (1,2) 3 - 1 3 (2,3) 4 + 4 - 2 4 5 + 5 - 4 3 (2,3) 6 + 6 - 0 1 (3,2) 2 + 2 - 1 2 + L (2,2) (0,2) (0,0) (0,0) 3 + (0,2) # * # L Figure 8
. Initialization of the graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹).

In the second step, the node number 2 + is removed from the queue and all the labels on node 2 + are propagated on node 2 -. In this step, two labels are created (Fig. 9):

 𝐿 1 2 -= (2|1,0,2,0,2,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4)  𝐿 2 2 -= (2|0,1,0,2,0,2|0,2, -∞, -∞, 4|1,1,1,2,2,2|0,1,2,2,4) 0 1 (3,2) L 2 + 1 2 + 2 - L 2 - 1 L 2 - 2 Figure 9.
Step 2: Propagation of the label on arc number 2 in 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹).

The creation of label 𝐿 1 2can be designed to take label 𝐿 1 2 + , the arc (0,1) with the information (3,2) and the assignment of vehicle 1 into account.

Label 𝐿 1 2is created considering the propagation rule (loaded transport operation):

𝑃 1,2 - 1 = 𝜆(2 -) = 1 𝐴 1,2 - 1 = 𝐵 1,2 + 1 + 𝑡 0,1 = 0 + 2 = 2 𝐵 1,2 - 1 = 𝐴 1,2 - 1 = 2 𝑆 1,2 - 1 = 𝑚𝑎 𝑥(𝑆 1,2 + 1 ; 𝐴 1,2 - 1 ) = 𝑚𝑎 𝑥(-∞; 2) = 2
𝜑 1,2 -𝑅,2 = 𝜑 1,2 + 𝑅,2 -𝑚 𝑖𝑛( 𝜑 1,2 + 𝑅,2 ; 𝑐 1 ) = 3 -𝑚𝑖𝑛(2; 3) = 0 𝑏 1,2 -𝑅,1 = 𝑏 1,2 + 𝑅,1 -𝑚 𝑖𝑛( 𝜑 1,2 + 𝑅,2 ; 𝑐 1 ) = 3 -𝑚𝑖𝑛(2; 3) = 0 and because 𝑏 1,2 -𝑅,1 = 0, the earliest starting time of all successors of activity 1 should be updated:

𝑆 1,2 - * = 𝑆 1,2 - 1 + 𝑝 1 = 2 + 2 = 4
The two labels created are not comparable due to the position of the vehicles. They are therefore both stored on node 2 -. The queue is updated and is equal to

Λ = [1 + , 2 -].
In the third step, the node number 2 -is removed from the queue and the labels on node 2 -are propagated on nodes 1 + , 2 + , 3 + , 4 + with a feasibility check. This label propagation concerns unloaded transport operations in the dashed arcs in Fig. 8.

Ten labels are created:  Four on node 1 + :

𝐿 1 1 + = (4|0,0,4,0,4,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4)

𝐿 2 1 + = (2|1,0,2,0,2,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4)

𝐿 3 1 + = (2|0,1,0,2,0,2|0,2, -∞, -∞, 4|1,1,1,2,2,2|0,1,2,2,4) 𝐿 4 1 + = (4|0,0,0,4,0,4|0,2, -∞, -∞, 4|1,1,1,2,2,2|0,1,2,2,4)
 Two on node 2 + :

𝐿 1 2 + = (2|0,1,0,2,0,2|0,2, -∞, -∞, -∞|1,1,1,2,2,2|0,1,2,2,4) 𝐿 2 2 + = (4|0,0,0,4,0,4|0,2, -∞, -∞, -∞|1,1,1,2,2,2|0,1,2,2,4)
 Two on node 3 -:

𝐿 1 3 + = (4|1,0,2,0,4,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4) 𝐿 2 3 + = (4|1,1,2,2,2,4|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4)
 Two on node 4 -:

𝐿 1 4 + = 𝐿 1 3 + and 𝐿 2 4 + = 𝐿 2 3 +

Table 3

Details of all the labels of the optimal solution in Fig. 10.

Node List of labels # 𝐿 . # = (0|0,0,0,0,0,0|0, -∞, -∞, -∞, -∞|1,3,1,2,2,2|0,3,2,2,4) 1 + 𝐿 . 1 + = (2|1,0,2,0,2,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4) 1 -
𝐿 . 1 -= (2|1,2,2,2,2,2|0,2,2, -∞, 4|0,0,1,2,2,2|0,0,1,2,4) 2 + 𝐿 . 2 + = (0|0,0,0,0,0,0|0, -∞, -∞, -∞, -∞|1,3,1,2,2,2|0,3,2,2,4) 2 - 𝐿 . 2 -= (2|1,0,2,0,2,0|0,2, -∞, -∞, 4|1,0,1,2,2,2|0,0,2,2,4) 3 + 𝐿 .

3 + = (4|1,3,2,7,4,7|0,2,2,7,11|0,0,1,0,2,2|0,0,1,0,4) 3 - 𝐿 .

3 -= (6|2,3,6,7,6,7|0,2,6,16,16|0,0,0,0,2,2|0,0,0,0,4) 4 + 𝐿 . 4 + = (4|1,1,2,4,2,4|0,2,2, -∞, 4|0,0,1,2,2,2|0,0,1,2,4) 4 - 𝐿 . 4 -= (6|1,3,2,7,2,7|0,2,2,7,11|0,0,1,0,2,2|0,0,1,0,4) (16|2,3,16,7,16,7|0,2,6,16,16|0,0,0,0,2,2|0,0,0,0,4) 5 - 𝐿 . 5 -= (18| * ,3,18,7,18,7|0,2,6,16,18|0,0,0,0,0,2|0,0,0,0,2) (21|3,3,20,7,21,7|0,2,6,16,18|0,0,0,0,0,2|0,0,0,0,2) 6 - 𝐿 . 6 -= (24| * ,3,24,7,24,7|0,2,6,16,24|0,0,0,0,0,0|0,0,0,0,0) * 𝐿 . * = (24| * , * ,24,10,24,10|0,2,6,16,24|0,0,0,0,0,0|0,0,0,0,0)

5 + 𝐿 . 5 + =
6 + 𝐿 . 6 + =
At the end of the algorithm, i.e., when all labels have been propagated (the queue Λ is then empty), a set of non-dominated solutions are obtained. The final solutions that minimize the makespan are optimal since they minimize the objective function (first parameter in the labels). An optimal solution (solution minimizing the makespan) is introduced in Fig. 10 considering the trip of vehicle 1 in Fig. 10.a and the trip of vehicle 2 in Fig. 10.b. All the labels are fully described in Table 3. In Fig. 1 and2, an extended Gantt diagram displays this optimal solution.

Discussion

The algorithm proposed to solve the RCPSPR from a flow solution takes advantage of a resource-constrained shortest path algorithm. This algorithm is dedicated to the resolution of an arc routing problem with specific features based on the fact that the scheduling and the routing are interrelated with shared resource management. In the problem of interest here, the transport operations are first linked by precedence constraints due to the flow definition and, second, model the required arcs with a quantity that can eventually exceed the vehicle capacity. To the best of our knowledge, there is no specific method in the arc routing community that simultaneously tackles these constraints and that could provide time-saving implementation. This algorithm first attempts to optimally transform a RCPSP flow solution into a RCPSPR solution and is the first step towards defining an efficient framework based on the indirect modeling of solutions using the flow. This is a theoretical contribution with a practical application.

(0,0)

0 2 1 + 1 - 1 2 (1,2) 3 - 1 3 4 + 4 - 2 4 5 + 5 - 4 3 (2,3) 6 + 6 - 0 1 (3,2) 2 + 2 - (2,2) * # (0,0) 3 + (0,3) (0,2,2) L 2 + . L 2 - . L 6 + . L 6 - . L * . L 5 - . L 5 + . L 3 - . L 3 + . a. Trip of vehicle 1 0 2 (1,2) 1 + 1 - 1 2 3 - 1 3 (2,3) 4 + 4 - 2 4 5 + 5 - 4 3 6 + 6 - 0 1 2 + 2 - * # 3 + (0,2) (0,3) L 4 - . L 4 + . L * . L 1 - . L 1 + .
b. Trip of vehicle 2 Figure 10. Representation of the two trips of an optimal solution on the graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹).

Numerical experiments

The aim of these experiments is to provide feedback on the efficiency of the algorithm to compute an optimal RCPSPR solution from one RCPSP solution. The efficiency is analyzed considering the CPU time required in practice and the total number of labels generated during the process.

All experiments were carried out on a single thread C program, using Visual Studio and a Windows 7 operating system on a Dell Optiflex9020 with an Intel Core i7-4770 CPU 3.4 GHz and 16 Gb of RAM, meaning approximately 2671 Mflops (see [START_REF] Dongarra | Performance of various computers using standard linear equations software[END_REF]. The CPLEX experiments were carried out on the same computer. In order to ensure fair future comparative studies, all results and one example are available at the following web page: http://fc.isima.fr/~vinot/Research/RCPSPR_Flow.html

New set of instances

To the best of our knowledge, no instance dealing with this problem is available. Consequently, numerical experiments are based on a new set of small-scale instances composed of 18 instances with six activities (plus the dummy nodes). In these instances, the location of the activities can be divided into two configurations: the first one with a uniform distribution of the activities and the second one with two clusters.

Tables 4 and5 introduce the number of activities to be scheduled, but this number does not include information on the number of transport operations. The number of transport operations depends on the flow modeling a RCPSP solution and on the vehicle capacities. Column 𝐿𝐵(𝑛) is the lower bound of the total number of operations to be scheduled, considering both 𝑛 and the minimal number of arcs with a non-null flow, i. e., 𝑛 + 1, obtained with an ordered sequence of activities. The resource requirement and availability, the capacity of the vehicles and the ratio are given in Table 4. The ratio is defined as the ratio between the average duration of an activity and the average duration of a transport operation per vehicle, which is representative of the relative importance of the scheduling vs. the routing. A ratio greater than one means that the scheduling processing time represents a greater amount of time than the routing, and a ratio lower than one implies the reverse.

A new set of medium-scale instances composed of nine instances with 30 activities (plus the dummy nodes) is also introduced. In these instances, the location of the activities is divided into three configurations: the first one with a uniform distribution of the activities and the depot located at the center of the location, the second one with two clusters and the depot located at the center of the location, and the third one with two clusters and the depot location in a cluster (Table 5).

Due to the combinatorial nature of the RCPSP, obtaining optimal solutions using exact methods for problems with over 60 or so activities becomes intractable and, hence, impractical [START_REF] Valls | Justification and RCPSP: A technique that pays[END_REF]. Moreover, the RCPSPR is an extension of the RCPSP with the management of a fleet of vehicles where the decision variables encompass both RPCSP variables and a set of variables for the routing problem. In this new set of medium instances, more than 60 operations have to be scheduled (𝐿𝐵(𝑛) = 61). The optimal resolution of this set of instances is challenging due, first, to the large number of operations to be scheduled, including both the activities and the transport operations and, second, to the coordination between the activities and the transport operations, including the assignment of vehicles to the transport operations.

All the details of the instances are available at the web page.

Performance of the shortest path algorithm

The effectiveness of the shortest path algorithm can be evaluated on small-scale instances by considering a restriction of 𝑌 𝑖 to 500 labels per node, with 𝑟 = 10 replications per instance. One replication models one randomly generated flow (with one replication considering the flow leading to the optimal RCPSP solution). The shortest path algorithm is compared to an optimal resolution with IBM ILOG CPLEX 12.6 and a linear formulation of the problem [START_REF] Lacomme | Formalisation linéaire d'un problème de RCPSP avec transport de ressources[END_REF].

For each instance, ℎ 𝐶 (𝑥, r) defines the average solution cost with CPLEX, and 𝑡 𝐶 (𝑥, 𝑟) the average computational time required to find the optimal solution with CPLEX. Similarly, ℎ 𝑆𝑃 (𝑥, r) denotes the average best-found solution cost using the shortest path algorithm (restriction of 𝑌 𝑖 can lead to a suboptimal solution), and 𝑡 𝑆𝑃 (𝑥, 𝑟) the average resource-constrained shortest path algorithm time to the best-found solution. The notation 𝑔(𝑥, 𝑛) denotes the gap between ℎ 𝑆𝑃 (𝑥, 𝑟) and ℎ 𝐶 (𝑥, 𝑟) for the instance 𝑥, and 𝑔(𝑥, 𝑟) is an estimation of the average gap considering 𝑛 replications. The number of optimal solutions found by the shortest path algorithm for the instance 𝑥 with 𝑛 replications is denoted 𝑛 𝑆𝑃 (𝑥, 𝑛). Let us denote 𝑔(. , 𝑟) as the estimation of the average gap considering the 18 instances, 𝑡 * (. , 𝑟) (resp. 𝑡 𝑆𝑃 (. , 𝑟), and 𝑡 𝐶 (. , 𝑟)) the estimation of the average computational time (resp. of CPLEX and of the shortest path), 𝑛 𝑆𝑃 (. , 𝑟) the average number of optimal solutions found over the 18 instances, and 𝑛 𝑆𝑃 (. , . ) = ∑ 𝑛 𝑆𝑃 (𝑥, 𝑟), 𝑥=18 𝑥=1

i.e., the total number of optimal solutions found during the 10 replications and the 18 instances.

The average resource-constrained shortest path computational time 𝑡 𝑆𝑃 (. , 𝑟) in Table 6 is approximately 8.2 seconds, approximately two times lower that the CPLEX computational time 𝑡 𝐶 (. , 𝑟), which is approximately 17.8 seconds (Table 6). The average number of optimal solutions found by the resourceconstrained shortest path algorithm is greater than 9.9, which means that the percent of optimal solutions found is close to 100%. It can be observed that the resource-constrained shortest path algorithm finds the optimal solution for 176 flows out of 180 (𝑛 𝑆𝑃 (. , . )), with an average gap of 0.04%.

Table 6

Average shortest path efficiency with a restriction of 𝑌 𝑖 to 500 labels per node (𝑟 = 10 flows per instance) for small-scale instances. 7 gives the set of flows randomly generated for instance LMQV_U1 (that include the optimal RCPSP flow) and provides the optimal RCPSP solution (column 2) for each flow and the optimal RCPSPR solutions provided by CPLEX and by the shortest path algorithm. The set of 10 flows introduced in Table 7 encompasses the flow of the optimal RCPSP solution. Note that the best (optimal) solution of the RCPSP has a cost equal to 19, whereas the worst one in Table 7 has a cost equal to 24. Nevertheless, the best solution found for the RCPSPR has a cost equal to 87 and was obtained with a solution of the RCPSP with a cost equal to 20 (flow number 3 in Table 7). Such results lead us to consider that high-quality solutions of the RCPSP do not lead to high-quality RCPSPR solutions, which is not really surprising since there is no reason that a quality solution for one sub-problem favors the computation of a quality solution for the whole problem. Indeed, several solutions of the RCPSP with the same makespan (for example, 23) could lead to very different solutions of the RCPSPR with a cost ranging from 86 to 105. Such behavior suggests that it would be difficult to devise a rule that could provide quality RCPSPR solutions by considering the quality RCPSP solutions. For example, it should be noted that the instance LMQV_J30_U1 cannot be solved to optimality in 2 days of computational time using CPLEX.

For the couples instance/flow introduced in Table 8, a lower bound of the number of transport operations is provided in column 𝑛 𝜑 . For the instance LMQV_J30_CC1, we have 30 activities plus at least 60 transport operations, representing a total of 90 operations to be scheduled, assuming that each flow is transferred by one vehicle only with one transport. The minimal number of transport operations (with a value of 60) is induced by arcs with a non-null flow.

Performance of the label management rules

To evaluate the efficiency of the algorithm, no restriction of 𝑌 𝑖 , i.e., all labels that are required to be kept, is stored on nodes, and Table 9 provides the number of:  labels inserted on the node due to the 𝐼𝑁𝑆𝐸𝑅𝑇_𝐿𝐴𝐵𝐸𝐿() function;  labels pruned on the node with 𝐶𝐻𝐸𝐶𝐾_𝑈𝐵_𝐿𝐵() function;

 labels deleted on the node with 𝐴𝑃𝑃𝐿𝑌_𝐷𝑂𝑀𝐼𝑁𝐴𝑁𝐶𝐸() function.

All experiments were carried out on the 18 small-scale instances considering the 10 replications previously used, and the following notations are used in Table 9:  𝑇𝑁𝐿𝐺(𝑥, 𝑗) Total number of labels generated during the replication number 𝑗;  𝑇𝑁𝐿𝐺(𝑥, 𝑟) Average number of labels generated during the 𝑟 replications;  𝑇𝑁𝐿𝑃(𝑥, 𝑟) Average number of labels pruned per instance 𝑥 during the 𝑟 replications;  𝑃 𝑝 (𝑥, 𝑗)

Percent of labels pruned considering 𝑇𝑁𝐿𝐺(𝑥, 𝑗);  𝑃 𝑝 (𝑥, 𝑟)

Average percent of labels pruned with 𝑃 𝑝 (𝑥, 𝑟) = 𝐴𝑣𝑔 𝑗=1,𝑟 (𝑃 𝑝 (𝑥, 𝑗)) ;

 𝑇𝑁𝐿𝐷(𝑥, 𝑟) Total number of labels dominated;  𝑃 𝑑 (𝑥, 𝑗) Percent of labels discarded thanks to the domination rule considering 𝑇𝑁𝐿𝐺(𝑥, 𝑗);  𝑃 𝑑 (𝑥, 𝑟)

Average percent of labels discarded, with 𝑃 𝑝 (𝑥, 𝑟) = 𝐴𝑣𝑔 𝑗=1,𝑟 (𝑃 𝑝 (𝑥, 𝑗)) ;

 𝑃(. , . ) Average percent of 𝑃 𝑝 (𝑥, 𝑟) or 𝑃 𝑑 (𝑥, 𝑟) for all instances;  𝐴𝑣𝑔(. , . )

Average number of labels generated, pruned or dominated. The following remarks hold:

 25% of the labels generated are pruned (thanks to the function 𝐶𝐻𝐸𝐶𝐾_𝑈𝐵_𝐿𝐵(𝐿, 𝐿𝐵, 𝑈𝐵));

 43% of the labels generated are deleted (thanks to the dominance rule with 𝐷𝑂𝑀𝐼𝑁𝐴𝑇𝐸(𝑖, 𝑗) and 𝐴𝑃𝑃𝐿𝑌_𝐷𝑂𝑀𝐼𝑁𝐴𝑁𝐶𝐸(𝐿, 𝑍).

These results lead us to consider that the dominance rule we introduced is highly efficient and defines the cornerstone of the shortest path algorithm.

Remarks

The results first confirm the algorithm efficiency from a computational point of view and prove that the algorithm can be used in practice and could be integrated into an iterative metaheuristic-based search on an indirect representation of solutions [START_REF] Cheng | A tutorial survey of job-shop scheduling problems using genetic algorithms -I representation[END_REF] (Prins, 2002). The resourceconstrained shortest path algorithm can be used to determine an evaluation function that defines the optimal RCPSPR solution for one flow. From this point of view, the computational efficiency of the method is crucial. Intensive numerical experiments have shown that the algorithm can be adapted depending on the context, and should make it possible to find quality RCPSPR solutions within an acceptable computational time. An experiment based on 18 flows revealed that the computational time can be reduced to 15 seconds with 500 labels per node, and to 0.4 seconds with 50 labels per node, providing the optimal RCPSPR solution in 67% of the flows (the average deviation to the optimal solution is less than 0.9%). Because the evaluation function that makes it possible to associate a flow with a solution can be a part of a global optimization process, the capacity of the algorithm to ensure quasi-optimal evaluation in a very short computational time is a significant highlight of the algorithm.

Concluding remarks

A new resource-constrained shortest path algorithm is introduced to define a RCPSPR solution from one RCPSP flow solution. The RCPSPR is a new integrated problem dealing with scheduling and routing based on the RCPSP to which routing constraints with a heterogeneous fleet of vehicles with limited capacities have been added.

Our contribution concerns: (1) the label definition that encompasses both system state and resources; (2) the dominance rule;

(3) the propagation rule.

The algorithm ensures an efficient algorithmic solution to deal with a proper coordination between scheduling and routing problems since it points the way towards a definition of an iterative search process based on an indirect representation by an efficient computation of RCPSP solutions from a flow of the RCPSP. It should be noted that the resource-constrained shortest path algorithm we have introduced is a new way to solve arc routing problems by shortest path computation.

Figure 5 .

 5 Figure 5. Arc Routing Transportation Graph 𝑇 𝜑 (𝑈, 𝑉, 𝐸, 𝐹)

Figure 6 .

 6 Figure 6. A solution with two trips in the graph 𝑇 𝜑 (𝑈, 𝑉, 𝐸, 𝐹)

  Propagation rule for a label on a pickup node (arc modeling a loaded transport operation) A propagation function defined by 𝑓: L  T → R that makes the propagation of a new label 𝐿 𝑞 𝑖from one label 𝐿 𝑝 𝑖 + and a loaded transport operation defined by (𝜑 𝑚𝑘 , 𝑡 𝑚𝑘 ) /𝑚 = 𝜆(𝑖 + ) and 𝑘 = 𝜆(𝑖 -) possible.

Figure 7 .

 7 Figure 7. Example of an activity-on-node (AON)-flow network 𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸).

  In the graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹), the vertices are divided into two disjointed sets:  𝑈: the pickup node set (in white in Fig 5);  𝑉: the delivery node set (in gray in Fig 5).

	since activity 𝑗 has to be scheduled after activity 𝑖. The longest path from 0 to 𝑛 + 1 in graph 𝐷𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) makes it possible to	from 𝑖 to 𝑗.
	obtain the earliest starting time of all activities and a critical
	path. The dashed arc in Fig. 4 models a precedence constraint
	between the activities.
	𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) and 𝐷𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) make it possible to define a graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹), which explicitly models the activities and the
	transport operations of the RCPSPR. In our problem, the arc
	routing transportation graph 𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹) uses two types of
	arcs (Lacomme et al., 2005):
	 required arc (𝑖, 𝑗) ∈ 𝐸 corresponding to a positive flow
	transfer and consequently defining loaded transport
	operations. A required arc can be serviced by several trips
	depending on the total demand and on vehicle capacities.
	 non-required arcs (𝑖, 𝑗) ∈ 𝐹 corresponding to a null flow and
	that can be used for an unloaded transport operation. Non-
	required arcs make it possible to define deadheading paths
		ϕ ip+1,ip+2 ϕ ip+2,* Figure 3. Activity-on-node (AON)-flow network 𝐺 𝐴𝑂𝑁 i . 𝜑 ( 𝑉, 𝐸) p i2 0 i 1 i p+1 i 2 i p+2 i p i p+n i p+. ... n+1 0 0 0 p i1 p ip+1 p ip+2 i .
		Figure 4. Disjunctive graph 𝐷𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸)
		𝜑 ( 𝑉, 𝐸) (Fig. 4) is defined considering A disjunctive graph 𝐷𝐺 𝐴𝑂𝑁 the (AON)-flow network 𝐺 𝐴𝑂𝑁 𝜑 ( 𝑉, 𝐸) graph. For each node, 𝑖 ∈
		𝑉, all outgoing arcs (𝑖, 𝑗) ∈ 𝐸 are weighted by the duration 𝑝 𝑖 of
		activity 𝑖. If there is an edge (𝑖, 𝑗) ∈ 𝐸, then 𝐶 𝑖 = 𝑆 𝑖 + 𝑝 𝑖 ≤ 𝑆 𝑗 ,

  New shortest path procedure. The Boolean function 𝐷𝑂𝑀𝐼𝑁𝐴𝑇𝐸(𝑖, 𝑗) (line 23) return true if the label 𝑖 is not dominated by an unprocessed label on node 𝑗. The label feasibility is checked considering the remaining resources in the function 𝑃𝐴𝑇𝐻(𝐿 𝑖 , 𝑛𝑜𝑑𝑒_𝑗). The propagation rule to create a new label (detailed below) is achieved by the procedure 𝐶𝑅𝐸𝐴𝑇𝐸_𝐿𝐴𝐵𝐸𝐿(𝐿 𝑤 , 𝑣, 𝐿 𝑖 , 𝑛𝑜𝑑𝑒 𝑖 , 𝑛𝑜𝑑𝑒 𝑗 ) (line 22), which makes it possible to obtain a new label 𝐿 𝑤 from label 𝐿 𝑖 considering vehicle 𝑣.

		Procedure name: New Shortest Path Algorithm
	1. procedure Shortest_Path
	2. input parameters
	2.	𝑇 𝜑 ( 𝑈, 𝑉, 𝐸, 𝐹): Arc routing transportation graph
	3.	𝑈𝐵: Upper Bound of the problem
	4.	𝐿𝐵 𝑖 : Lower Bound to reach the final node from node 𝑖
	5. output parameters
	6.	𝑆𝑜𝑙: Solution
	7. global parameter
	8.	Λ: Queue
	9.	𝑛_𝑣𝑒ℎ𝑖𝑐𝑙𝑒: number of vehicles
	10.	𝑁 𝐿 : maximum number of unprocessed labels into 𝑍 𝑖 ∈ 𝑈∪𝑉
	11. begin
	12.	Definition of 𝐿 𝑜
	13.	for 𝑛𝑜𝑑𝑒_𝑖 ∈ 𝑈 ∪ 𝑉 do
	14.	if (𝜆(𝑛𝑜𝑑𝑒_𝑖) = 0) then 𝑍 node_i = {𝐿 𝑜 },𝑃𝑈𝑆𝐻(Λ, 𝑛𝑜𝑑𝑒_𝑖) else 𝑃 node_i = {∅} endif
	15.	endfor
	16.	while (Λ ! = ∅) do
	17.	𝑛𝑜𝑑𝑒_𝑖 ∶= 𝑃𝑂𝑃(Λ)
	18.	for 𝐿 𝑖 ∈ 𝑍 node_i do	//for each label unprocessed on node i
	19.	for 𝑛𝑜𝑑𝑒_𝑗 ∈ 𝑠𝑢𝑐𝑐(𝑛𝑜𝑑𝑒_𝑖)do
	20.	if 𝑃𝐴𝑇𝐻(𝐿 𝑖 , 𝑛𝑜𝑑𝑒_𝑗) 𝑖𝑠 𝑓𝑒𝑎𝑠𝑖𝑏𝑙𝑒 then	//resources and precedence constraints
	21.	for 𝑣: = 1 to 𝑛_𝑣𝑒ℎ𝑖𝑐𝑙𝑒 do
	22.	call 𝐶𝑅𝐸𝐴𝑇𝐸_𝐿𝐴𝐵𝐸𝐿(𝐿 𝑤 , 𝑣, 𝐿 𝑖 , 𝑛𝑜𝑑𝑒 𝑖 , 𝑛𝑜𝑑𝑒 𝑗 )
	23.	if (𝐷𝑂𝑀𝐼𝑁𝐴𝑇𝐸(𝐿 𝑤 , 𝑛𝑜𝑑𝑒_𝑗 )) and (𝐶𝐻𝐸𝐶𝐾_𝑈𝐵_𝐿𝐵(𝐿 𝑤 , 𝐿𝐵 𝑛𝑜𝑑𝑒_𝑗 , 𝑈𝐵)) then
	24.	call 𝐼𝑁𝑆𝐸𝑅𝑇_𝐿𝐴𝐵𝐸𝐿(𝐿 𝑤 , 𝑍 𝑛𝑜𝑑𝑒_𝑗 ), call 𝑃𝑈𝑆𝐻(Λ, 𝑛𝑜𝑑𝑒_𝑗),
	25.	call 𝐴𝑃𝑃𝐿𝑌_𝐷𝑂𝑀𝐼𝑁𝐴𝑁𝐶𝐸(𝐿 𝑤 , 𝑍 𝑛𝑜𝑑𝑒_𝑗 )
	26.	endif
	27.	if (𝜆(𝑛𝑜𝑑𝑒_𝑗) = * ) then call 𝐶𝐻𝐸𝐶𝐾_𝑆𝑂𝐿(𝐿 𝑤 , 𝑈𝐵 ) endif
	28.	endfor
	29.	endfif
	30.	endfor
	31.	𝑍 node_i = 𝑍 node_i \ 𝐿 𝑖
	32.	𝑃 node_i = 𝑃 node_i ∪ 𝐿 𝑖
	33.	endfor
	34.	endwhile
	35.	𝑆𝑜𝑙 ∶= 𝐵𝐸𝑆𝑇_𝑆𝑂𝐿 (𝑇 𝜑 ) //save the best solution
	36. end
	Algorithm 1.

𝐷𝑂𝑀𝐼𝑁𝐴𝑇𝐸(𝑖, 𝑗) = ∄𝑘 ∈ 𝑍 𝑗 , 𝑘 ≪ 𝑖 (1)

The algorithm also uses the function 𝐶𝐻𝐸𝐶𝐾_𝑈𝐵_𝐿𝐵(𝐿, 𝐿𝐵, 𝑈𝐵) (line 23), which returns true if the label 𝐿 cannot be pruned, and false if the objective function of the label 𝐿 plus the lower bound 𝐿𝐵 does not fit the upper bound 𝑈𝐵.

Table 1

 1 Information about 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 4

 4 Small-scale instance characteristics.

	Instances	n	LB(n)	Location	Resource requirement	Resource availability	Vehicle capacity	Ratio
	LMQV_U1	6	13	uniform	{4;10;3;3;8;4}	12	{12;12}	1.6
	LMQV_U2	6	13	uniform	{4;10;3;3;8;4}	12	{12;12}	1.1
	LMQV_U3	6	13	uniform	{4;10;3;3;8;4}	12	{12;12}	1.3
	LMQV_U4	6	13	uniform	{2;8;7;8;8;5}	14	{6;5}	0.5
	LMQV_U5	6	13	uniform	{2;8;7;8;8;5}	14	{6;5}	0.4
	LMQV_U6	6	13	uniform	{2;8;7;8;8;5}	14	{6;5}	0.4
	LMQV_U7	6	13	uniform	{5;3;8;2;3;1}	10	{4;2}	0.3
	LMQV_U8	6	13	uniform	{5;3;8;2;3;1}	10	{4;2}	0.3
	LMQV_U9	6	13	uniform	{5;3;8;2;3;1}	10	{4;2}	0.3
	LMQV_C1	6	13	clusters	{7;7;5;7;5;4}	7	{7;7}	3.0
	LMQV_C2	6	13	clusters	{7;7;5;7;5;4}	7	{7;7}	2.1
	LMQV_C3	6	13	clusters	{7;7;5;7;5;4}	7	{7;7}	3.0
	LMQV_C4	6	13	clusters	{7;1;2;6;2;6}	11	{6;5}	1.1
	LMQV_C5	6	13	clusters	{7;1;2;6;2;6}	11	{6;5}	1.0
	LMQV_C6	6	13	clusters	{7;1;2;6;2;6}	11	{6;5}	1.0
	LMQV_C7	6	13	clusters	{4;10;4;6;3;4}	12	{4;2}	0.8
	LMQV_C8	6	13	clusters	{4;10;4;6;3;4}	12	{4;2}	0.8
	LMQV_C9	6	13	clusters	{4;10;4;6;3;4}	12	{4;2}	0.8

Table 5

 5 Medium-scale instance characteristics.

	Instances	n	LB(n)	Location	Resource requirement	Resource availability	Vehicle capacity	Ratio
	LMQV_J30_U1	30	61	uniform	[1;10]	13	{13;13}	0.7
	LMQV_J30_U2	30	61	uniform	[1;10]	14	{8;6}	0.3
	LMQV_J30_U3	30	61	uniform	[1;10]	13	{13;9}	1.0
	LMQV_J30_C1	30	61	clusters	[1;10]	15	{15;15}	0.8
	LMQV_J30_C2	30	61	clusters	[1;10]	11	{7;5}	0.3
	LMQV_J30_C3	30	61	clusters	[1;10]	12	{12;9}	0.9
	LMQV_J30_CC1	30	61	clusters	[1;10]	13	{13;13}	0.6
	LMQV_J30_CC2	30	61	clusters	[1;10]	14	{8;6}	0.3
	LMQV_J30_CC3	30	61	clusters	[1;10]	13	{13;8}	1.1

Table 7

 7 RCPSP/RCPSPR solutions (instance LMQV_U1).

				RCPSPR Solution
			CPLEX optimal resolution	Shortest path optimal resolution
	Flow	RCPSP Solution	ℎ 𝐶 (𝑥, 1)	𝑡 𝐶 (𝑥, 1)	ℎ 𝑆𝑃 (𝑥, 1) ̅̅̅̅̅̅̅̅̅̅̅	𝑡 𝑆𝑃 (𝑥, 1)	ℎ 𝐶 (𝑥, 1)
	1	19*	95	20.4	95	22.5	0.0 %
	2	19	115	97.1	115	25.0	0.0 %
	3	20	87	20.3	87	0.1	0.0 %
	4	20	117	115.7	117	22.3	0.0 %
	5	21	96	22.8	96	1.3	0.0 %
	6	22	99	27.7	99	5.8	0.0 %
	7	23	86	26.1	86	5.2	0.0 %
	8	23	105	40.7	105	1.5	0.0 %
	9	24	102	30.5	102	1.0	0.0 %
	10	24	113	65.2	113	23.4	0.0 %
	Average		101.5	46.6	101.5	10.6	0.0 %

Table

Table 8

 8 Shortest path for 𝑟 = 1 flow on each medium-scale instance.Table8reports the results obtained by the resource-constrained shortest path algorithm with a restriction of 𝑌 𝑖 to 50 labels per node, with 𝑟 = 1 replication per instance. In Table8, the cost of the RCPSP solution associated with the flow is reported in column 4. Unfortunately, the best-found solution of the algorithm cannot be compared to a solution obtained with CLEX. With 30 activities, the linear formulation remains intractable due the huge numbers of both variables and constraints, including binary variables.

	Shortest path optimal resolution (NL=50)

Table 9

 9 Efficiency of the label management rules with 𝑍 𝑖 = 𝑌 𝑖 for small-scale instances.

	Instances	𝑇𝑁𝐿𝐺(𝑥, 𝑟)	𝑇𝑁𝐿𝑃(𝑥, 𝑟)	𝑇𝑁𝐿𝐷(𝑥, 𝑟)	𝑃 𝑃 (𝑥, 𝑟)	𝑃 𝑑 (𝑥, 𝑟)
	LMQV_U1	256 514.9	49 313.8	114 201.4	19.2	44.5
	LMQV_U2	245 631.8	47 122.1	111 452.6	19.2	45.4
	LMQV_U3	298 695.6	57 901.4	136 189.4	19.4	45.6
	LMQV_U4	124 521.7	21 261.5	64 856.7	17.1	52.1
	LMQV_U5	134 996.0	22 109.0	73 049.9	16.4	54.1
	LMQV_U6	198 907.8	28 581.2	112 077.0	14.4	56.3
	LMQV_U7	177 200.4	40 449.2	78 194.4	22.8	44.1
	LMQV_U8	189 100.6	42 760.4	84 848.8	22.6	44.9
	LMQV_U9	217 710.7	51 939.6	92 055.1	23.9	42.3
	LMQV_C1	4.4	2.8	0.0	63.6	0.0
	LMQV_C2	4.4	2.8	0.0	63.6	0.0
	LMQV_C3	4.4	2.8	0.0	63.6	0.0
	LMQV_C4	543 915.1	101 480.3	267 705.7	18.7	49.2
	LMQV_C5	589 227.4	107 571.8	281 184.5	18.3	47.7
	LMQV_C6	580 233.6	107 110.3	280 699.6	18.5	48.4
	LMQV_C7	230 693.0	26 232.9	167 281.8	11.4	72.5
	LMQV_C8	294 602.6	35 820.0	203 370.0	12.2	69.0
	LMQV_C9	273 935.0	33 845.2	187 245.9	12.4	68.4
	𝐴𝑣𝑔(. , . )	241 994.4	42 972.6	125 255.8
	𝑃(. , . )				25.4	43.6

Acknowledgements: This work was carried out and funded within the framework of the ATHENA project (Reference: ANR-13-BS02-0006) and the Labex MS2T. It was supported by the French government through the "Investments for the future" program managed by the French National Research Agency (Reference: ANR-11-IDEX-0004-02).