Philippe Wenger
email: philippe.wenger@lan.ec-nantes.fr

Damien Chablat

Definition sets for the Direct Kinematics of Parallel Manipulators

Keywords: Parallel Manipulator, Workspace, Singularity, Aspect, Uniqueness domains, Octree

The aim of this paper is to characterize the uniqueness domains in the workspace of parallel manipulators, as well as their image in the joint space. The notion of aspect introduced for serial manipulators in [Borrel 86] is redefined for such parallel manipulators. Then, it is shown that it is possible to link several solutions to the direct kinematic problem without meeting a singularity, thus meaning that the aspects are not uniqueness domains. Additional surfaces are characterized in the workspace which yield new uniqueness domains. An octree model of spaces is used to compute the joint space, the workspace and all other newly defined sets. This study is illustrated all along the paper with a 3-RPR planar parallel manipulator.

INTRODUCTION

A well known feature of parallel manipulators is the existence of multiple solutions to the direct kinematic problem. That is, the mobile platform can admit several positions and orientations (or configurations) in the workspace for one given set of input joint values [Merlet 90]. The dual problem arises in serial manipulators, where several input joint values correspond to one given configuration of the end-effector. To cope with the existence of multiple inverse kinematic solutions in serial manipulators, the notion of aspects was introduced [ Borrel 86]. The aspects were defined as the maximal singularity-free domains in the joint space. For usual industrial serial manipulators, the aspects were found to be the maximal sets in the joint space where there is only one inverse kinematic solution. Many other serial manipulators, referred to as cuspidal manipulators, were shown to be able to change solution without passing through a singularity, thus meaning that there is more than one inverse kinematic solution in one aspect. New uniqueness domains have been characterized for cuspidal manipulators [ Wenger 92], [El Omri 96]. It is also of interest to be able to characterize the uniqueness domains for parallel manipulators, in order to separate and to identify, in the workspace, the different solutions to the direct kinematic problem. To the authors knowledge, the only work concerned with this issue is that of [Chételat 96], which proposes a generalization of the implicit function theorem. Unfortunately, the hypothesis of convexity required by this new theorem is still too restrictive. This paper is organized as follows. Section 2 describes the planar 3-RPR parallel manipulator which will be used all along this paper to illustrate the new theoretical results. Section 3 restates the notion of aspect for parallel manipulators. New surfaces, the characteristic surfaces, are defined in section 4, which, together with the singular surfaces, further divide the aspects into smaller regions, called basic regions. Finally, the uniqueness domains are defined in section 5. The workspace, the aspects, the characteristic and singular surfaces, and the uniqueness domains are calculated for the planar 3-RPR parallel manipulator using octrees. The images in the joint space of the uniqueness domains are also calculated. It is shown that the joint space is composed of several subspaces with different numbers of direct kinematic solutions.

PRELIMINARIES

PARALLEL MANIPULATOR STUDIED

This work deals with those parallel manipulators which have only one inverse kinematic solution. In addition, the passive joints will always be assumed unlimited in this study. For more legibility, a planar manipulator will be used as illustrative example all along this paper. This is a planar 3-DOF manipulator, with 3 parallel RPR chains (Figure 1). The input joint variables are the three prismatic actuated joints. The output variables are the positions and orientation of the platform in the plane. This manipulator has been frequently studied, in particular by [Merlet 90], [Gosselin 91] and [ Innocenti 92].

The kinematic equations of this manipulator are

[Gosselin 91] : ρ 1 2 2 2 = + x y (1) ( ) ( ) ( ) ( ) ρ φ φ 2 2 2 2 2 2 2 = + - + + x l c y l cos sin (2) ( ) ( ) ( ) ( ) ρ φ θ φ θ 3 2 3 3 2 3 3 2 = + + - + + + - x l c y l d cos sin (3)
The dimensions of the platform are the same as in [Merlet 90] and in [Innocenti 92] :

• A 1 = (0.0, 0.0) B 1 B 2 = 17.04

• A 2 = (15.91, 0.0) B 2 B 3 = 16.54

• A 3 = (0.0, 10.0) B 3 B 1 = 20.84

The limits of the prismatic actuated joints are those chosen in [Innocenti 92] :

10 0 32 0 . . ≤ ≤ ρ i
The passive revolute joints are assumed unlimited. The octree models of the joint space (in the space ρ 1 , ρ 2 , ρ 3 ) and of the workspace (in the space x, y et φ) of the 3-RPR parallel manipulator are shown in figures 2 and 3. The joint space is not a complete parallelepiped, since any joint vector can't lead to an assembly configuration of the manipulator.

SINGULARITIES

The vector of input variables and the vector of output variables for a n-DOF parallel manipulator are related through a system of non linear algebraic equations which can be written as :

( )

F q X , = 0 (4)
where 0 means here the n-dimensional zero vector.

Differentiating (4) with respect to time leads to the velocity model :

A X B q & & + =0 (5)
where A and B are n × n Jacobian matrices. Those matrices are functions of q and X :

A F X B F q = = ∂ ∂ ∂ ∂ (6)
These matrices are useful for the determination of the singular configurations [Sefrioui 92].

Type 1 singularities

These singularities occur when det(B) = 0.

For the planar manipulator, this condition can be satisfied only when ρ 1 = 0 or ρ 2 = 0 or ρ 3 = 0.

In practise, the type-1 singularities are attained when one of the actuated prismatic joints reaches its limit [Gosselin 90]. The corresponding configurations are located at the boundary of the workspace.

For parallel manipulators which may have more than one inverse kinematic solutions, type-1 singularities are configurations where two solutions to the inverse kinematic problem meet. By hypothesis, type-1 singularities will be always associated with joint limits in this paper.

Type 2 singularities

They occur when det(A) = 0. Unlike the preceding ones, such singular configurations occur inside the workspace. They correspond to configurations for which two branches of the direct kinematic problem meet. They are particularly undesirable since the manipulator cannot be steadily controlled in such configuration where the manipulator stiffness vanishes in some direction.

For the planar manipulator, such configurations are reached whenever the axes of the three prismatic joints intersect (possibly at infinity). In such configurations, the manipulator cannot resist a wrench applies at the intersecting point (Figure 4).

These singular configurations have been built and modelled using octrees (Figure 5). The equation of det(A) can be put in an explicit form y = s(x,φ), only two variables need to be swept in the octree enrichment process

NOTION OF ASPECT FOR PARALLEL MANIPULATORS

The notion of aspect was introduced by [Borrel 86] to cope with the existence of multiple inverse kinematic solutions in serial manipulators. An equivalent definition was used in [Khalil 96] for a special case of parallel manipulators, but no formal, more general definition has been set. The aspects are redefined formally in this section.

DEFINITION

Let OS m and JS n denote the operational space and the joint space, respectively. OS m is the space of configurations of the moving platform and JS n is the space of the actuated joints.

Let g be the map relating the actuated joint vectors with the moving platform configurations:

g OS JS X q g X m n : ( ) → → = (7)
It is assumed m = n, that is, only non-redundant manipulators will be studied in this paper. Let W be the reachable workspace, that is, the set of all positions and orientations reachable by the moving platform [ Kumar 92], [ Pennock 93]. Let Q be the reachable joint space that is, the set of all joint vectors reachable by actuated joints.

{ }

Q q JS i n q q q Q JS n i i i n = ∈ ∀ ≤ ≤ ≤ ⊂ , , , min max (8)
( )

Q g W W OS m = ⊂ , (9)
Definition 1:

The aspects WA i is defined as the maximal sets such that:

• WA i ⊂ W; • WA i is connected; • ∀ X ∈ WA i , ( )
Det WA i ≠ 0 .
In other words, the aspects are the maximal singularityfree regions in the workspace.

The aspects are computed as the connected components of the set obtained by removing the singularity surfaces from the workspace, which can be done easily with the octree model :

∪ = - WA W S i (10)

Application :

For the planar manipulator studied, we get two aspects (WA 1 and WA 2 ), where Det(A)>0 and Det(A)<0, respectively. The singular surface of figure 5 is the common boundary of the two aspects (figure 6). The solutions to direct kinematic problem are (Table 1) .

We notice that solutions -2-, -3-, -6-are in the same aspect (WA 1 ) (Figure 7).

This example clearly shows that the aspects are not the uniqueness domains. Additional surfaces have to be defined for separating the solutions.

x This definition is restated here for the case of parallel manipulators.

Definition 2 :

Let WA an aspect in workspace W. The characteristic surfaces of the aspect WA, denoted S c (WA), are defined as the preimage in WA of the boundary WA that delimits WA (Figure 8) :

( ) ( ) ( ) S WA g g WA WA c = ∩ -1 (12)
where :

• g is defined as in (7)

• g -1 is a notation. Let B ⊂ Q : ( ) { } g B X W g X B - = ∈ ∈ 1 ( ) /
The boundaries WA of WA are composed of :

• the type-2 singularities ;

• the type-1 singularities (limits of the actuated joints).

CASE OF THE PLANAR FULLY PARALLEL MANIPULATOR OF TYPE 3 -RPR

The characteristic surfaces are computed using definition (12). The singular surfaces are scanned and their preimages in the joint space are calculated using g. The resulting inverse singularities are mapped back into the workspace using the direct kinematic model. We get one characteristic surfaces for each aspect, denoted S c1 and S c2 , respectively (Figure 9). Let QA bi = g(Ab i ), QA bi is a domain in the joint space Q called basic components. Let WA an aspect and QA its image under g. The following relation holds :

( ) ( ) ( ) QA QAb g S WA i I i C = ∪ ∪ ∈ (14)
Proposition 1 :

The basic components of a given aspect are either coincident, or disjoint sets of Q.

Due to space limitation, no proof is provided in this paper. They can be found in [Chablat 96b]. The following can be shown :

Theorem 1 :
The restriction of g to any basic region is a bijection. In other words, there is only one direct solution in each basic region.

Application :

The basic regions are calculated as the connected components of the set obtained by removing the characteristic surfaces from the aspects :

∪ = - WA WA S bi i ci (15)
We obtain thus 28 basic regions for the planar manipulator at hand (Figure 10). We notice that, in accordance with proposition 1, the basic components are either coincident or disjoint. The coincident components yield domains with 2, 4 or 6 solutions for the direct kinematic problem : the upper two domains contain two coincident basic components, the middle four domains are composed of four coincident domains, and the last two domains contain six coincident basic components (Figure 11).

UNIQUENESS DOMAINS

Theorem 1 yields sufficient conditions for defining domains of the workspace (the basic regions) where there is one unique solution for the direct kinematic problem. However, the basic regions are not the maximal uniqueness domains. The following theorem 2 intends to define the larger uniqueness domains in the workspace.

Theorem 2 :

The uniqueness domains Wu k are the union of two sets : the set of adjacent basic regions ( )

' ∪ ∈ i I i
WAb of the same aspect WA whose respective preimages are disjoint basic components, and the set S c (I') of the characteristic surfaces which separate these basic components :

( ) ( ) Wu WAb Sc I k i I i = ∪ ∪ ∈ ' ' (17) with I' ⊂ I such as ∀ ∈ i I 1 2 ,i ' , ( ) ( ) g WAb g WAb i i 1 2 ∩ =∅ .
Proof of this theorem can be found in [Chablat 96b].

Application :

To build the uniqueness domains, we have to consider the adjacent basic regions corresponding to disjoint, adjacent basic components.

Figure 12 : Octree model of the six uniqueness domains Six uniqueness domains have been found for the planar manipulator (Figure 12), that is as many as the number of direct kinematic solutions. Note that in general, the number of uniqueness domains should be always more or equal to the maximal number of direct kinematic solutions. We notice that, in the joint space, a nonsingular configuration changing trajectory has to go through a domain made of only two coincident basic components, that is, a domain where there are only two direct kinematic solutions (one in each aspect). In addition, it is worth noting that the domain with six coincident basic components map into six basic regions which are linked together by singular surfaces. This means that a non-singular configuration changing trajectory cannot be a straightforward motion between two such basic regions, but should pass through another intermediate basic region (Figure 13).

Figure 1

 1 Figure 1 : 3-RPR planar manipulator 2.2 OCTREE MODEL The octree is a hierarchical data structure based on a recursive subdivision of space [Meagher 81]. It is particularly useful for representing complex 3-D shapes, and is suitable for Boolean operations like union, difference and intersection. Since the octree structure has an implicit adjacency graph, arcwise-connectivity analyses can be naturally achieved. The octree model of a space S leads to a representation of S with cubes of various sizes. Basically, the smallest cubes lie near the boundary of the shape and their size determines the accuracy of the octree representation. Octrees have been used in several robotic applications [Faverjon 84], [Garcia 89], [El Omri 93]. In this work, the octree models are calculated using discretization and enrichment techniques as described in [Chablat 96a].

Figure 2 :

 2 Figure 2 : Octree model of the joint space Figure 3 : Octree model of the workspace

[

  Chablat 96b].

  Figure 4 : Type-2 singular configurations

  Finding the solutions X to equation q= g(X) means solving the direct kinematic problem. For our planar parallel manipulator, it has been shown that the direct kinematic model can admit six real solutions [Gosselin 91].

Figure 6 :

 6 Figure 6 : Octree model of the aspects 3.2 NON-SINGULAR CONFIGURATION CHANGING TRAJECTORIES In [Innocenti 92], a non-singular configuration changing trajectory was found for the planar manipulator. However, it appears that this trajectory passes close to a singular configuration. We have been able to confirm that non-singular configuration changing trajectories do exist for this robot. For the following input joint values : ρ ρ ρ 1 2 3 14 98 15 38 12 0 = = = . . . (11)

Figure 7 :

 7 Figure 7 : Three direct kinematic solutions in one single aspect 4. CHARACTERISTIC SURFACES 4.1 DEFINITION The characteristic surfaces were initially introduced in [Wenger 92] for serial manipulators.

Figure 8 :

 8 Figure 8 : Definition of the characteristic surfaces (scheme)

Figure 9 :

 9 Figure 9 : Octree model of the singularities and of the characteristic surfaces S c1 5. UNIQUENESS DOMAINS 5.1 BASIC COMPONENTS AND BASIC DOMAINS Definition 3 : Let WA be an aspect. The basic regions of WA, denoted { } WAb i I i , ∈ , are defined as the connected components of the set ( ) WA S WA C & -

Figure 10 :

 10 Figure 10 : Octree model of the basic regions The basic components are computed as : ( ) QA g WAb i i = (16)

Figure 11 :

 11 Figure 11 : Octree model of the basic components

Figure 13 :

 13 Figure 13 : Basic regions and basic components with 6 solutions to the direct kinematic problem6. CONCLUSIONThe problem of determining the uniqueness domains in the workspace of parallel manipulators has been studied in this paper. The aspects, originally introduced for serial manipulators, have been redefined here as the largest singularity-free regions in the workspace. The aspects were shown to be divided into distinct basic regions where there is only one solution to the direct kinematic problem. These regions are separated by the singular surfaces plus additional surfaces referred to as characteristic surfaces. Physically, the basic regions separate the different solutions to the direct kinematic problem : given a point in the joint space, the corresponding configurations of the moving platform are distributed in the different basic regions. The maximal uniqueness domains have been defined as the union of adjacent basic regions whose preimages in the joint space are not coincident. All results have been illustrated with a 3-DOF planar RPR-parallel manipulator. An octree model of space and specific enrichment techniques have been used for the construction of all sets. This work brings preliminary material to further investigations like trajectory planning [Merlet 94], which is the subject of current research work from the authors.

Table 1 :

 1 y Six direct kinematic solutions for the planar manipulator

	φ


Christian Serrano
email: christian.serrano@emse.fr

Javier Moral
email: javier.moral-blanco@renault.com

Xavier Delorme
email: delorme@emse.fr

Alexandre Dolgui
email: alexandre.dolgui@mines-nantes.fr

Cross-docking Operation Scheduling: Truck Arrivals, Shop-Floor Activities and Truck Departures

Keywords: Cross-docking, Integer Linear Programming, International logistics, Operation Scheduling, Truck scheduling problem (TRSP)

Cross-docking is a relatively new logistic strategy which seeks to make economies in transportation, decrease lead time and reduce inventory. The main principle is to unload, sort, consolidate and transfer delivered packages from inbound trucks to outbound trucks, with a minimum of storage or treatment in between. Two key issues associated to this field are the truck scheduling and the shop-floor operation scheduling. We propose a mixed integer linear programming model to schedule truck arrivals, shop-floor activities and truck departures. The cross-dock configuration we study is based on an industrial case on the automotive industry. In particular, a repack operation and two temporary storage zones are considered. The objective is to minimize internal operation cost (penalty related to extra capacity needs) and outbound transportation cost (number of trucks). The model is implemented and tested in CPLEX with small size instances, based on industrial data. The proposed model could be easily adapted to a variety of cross-dock configurations, in terms of internal capacity and cost distribution.

INTRODUCTION

Nowadays supply chain performance is crucial to maintain competitiveness in a more and more globalized industrial environment [START_REF] Dolgui | Supply chain engineering: Useful methods and techniques[END_REF]. In order to respond to customer's demand in terms of timing, quality and cost, companies implement new logistic strategies. One of them is cross-docking.

A cross-dock platform is an intermediate point in the supply chain, in which incoming deliveries are transferred to outgoing vehicles, with almost no internal treatment or storage. Its main purpose is to enable economies in transportation, thanks to product consolidation [START_REF] Boysen | Cross dock scheduling: Classification, literature review and research agenda[END_REF], but a reduction of lead time and a decrease (or even elimination) of stock levels are also expected benefits of cross-docking (Saddle Creek Report, 2011). In a cross-dock centre products are unloaded from incoming trucks, moved across the platform, sorted by outbound destination and finally loaded onto outgoing trucks.

In the context of global sourcing and internationalisation strategies, several carmakers have set up cross-docking facilities to optimize transportation costs. Renault Group share of sales outside Europe has doubled in the last decade, reaching 46% in 2014. The company relies on a worldwide network of cross-dock centres, called ILN (International Logistic Network). These centres mainly link overseas assembly plants with inland suppliers. Figure 1 shows the logistic network of an ILN and situates the problem treated in this research work. For more details on the functioning mode of ILN platforms, see Serrano et al. (2015). They propose a distribution and operation planning model to minimize transportation costs (inbound and outbound) and internal costs (storage and resources). Their research treats tactical decisions, since they seek to plan the weekly activity at the logistic platform. Our paper complements the cited work, by proposing an operational decision model, to deal with daily decisions at a cross-dock centre. Some characteristics of the overseas outbound transportation that takes place in Renault ILN platforms are considered in this research work. The first one is related to a repack activity needed for some products, in order to adapt their packages to the specific conditions of maritime transportation. This fact must be taken into account during the scheduling of shopfloor activities. The second feature is that every outbound truck is routed to the harbour, where products wait for their corresponding vessel departure. The latter simplifies the decisions on the outbound segment of the cross-dock. In particular, there is neither a vehicle routing problem (all must go to the harbour) nor hard constraints on departure time of trucks (the only constraint is that all products must be shipped before the end of the planning horizon). This research work treats the operation scheduling problem at a cross-dock platform, based on a case of study on the automotive industry. It is assumed that all inbound trucks are available at the beginning of the planning horizon. In the shop-floor, we include a repack activity (needed for some products) and two temporary storage (or staging) zones. Finally, outbound trucks must be departed before the end of the planning horizon and the customer demand must be completely fulfilled at this point as well. To our knowledge, no previous work has treated together the aforementioned cross-dock configuration. An industrial case is studied to support the assumptions of the studied approach and test the proposed model. The paper is organised as follows: section 2 presents the current research on scheduling within crossdocking. The next section gives more details on the case study and the characteristics of the Renault cross-dock platforms that are considered in this research work. Afterwards, we define the problem we treat and accordingly, a mixed-integer linear programming model is proposed. Numerical experiments' conditions and results are presented next. Finally, we address both conclusion and perspectives. In the last decade, cross-docking operation scheduling has received considerable attention. In [START_REF] Li | Crossdocking: JIT Scheduling with Time Windows[END_REF] the shopfloor operation scheduling is modelled as the well-known machine scheduling problem. Two main operations are defined: breakdown incoming containers and build-up outgoing containers. They consider containers as jobs that must be treated by parallel machines (shop-floor teams). Intermediate storage is necessary if all machines are busy. The objective is to minimize holding cost and penalty cost associated to earliness and tardiness.

An exact method and two heuristics are developed and tested. They generate a set of 16 instances of various sizes. The exact method finds the optimal solution for 5 out of 16. Heuristics offer good solutions both in terms of cost and computing time. Yu and Egbelu (2008) consider a cross-dock platform with a temporary storage zone and conveyor belts to transport products. They propose a model that seeks to allocate products to outbound trucks and to determine truck sequence at inbound and outbound docks. They consider moving times in the shop-floor and the objective is to minimize makespan. A transhipment problem within a crossdocking network is studied by Miao et al. (2009). They consider time window constraints for both inbound and outbound trucks. Penalty costs are associated to tardiness on the outbound schedule. Cargos can be delayed in cross-dock for consolidation under a holding cost. Transportation costs are also included and are related to the distance travelled by trucks. The objective is to minimize total cost and a genetic algorithm is developed and tested with 8 set of instances. [START_REF] Boysen | Truck scheduling at zero-inventory cross docking terminals[END_REF] studies the truck scheduling problem (TRSP) at a cross-dock centre in the food industry. A zero inventory policy is adopted and therefore a completely synchronised inbound and outbound truck schedule is mandatory. An exact method model based on dynamic programming and a simulated annealing heuristics are presented.

Three different minimization objectives are considered: total flow time, outbound trucks' processing time and tardiness (based on customer due dates). It is shown that the heuristic method is suitable for real-world instances. Vahdani and Zandieh ( 2010) propose 5 meta-heuristics to schedule inbound and outbound trucks at a cross-dock, considering a temporary storage zone and which objective is to minimize total operation time.

The meta-heuristics are compared to a mixed integer linear model presented in a previous research work. Tests are run over 25 large-scale problems and meta-heuristics show, in overall, a better performance than the MILP model. A simultaneous scheduling of truck arrivals, truck departures and shop-floor pallet handling is studied by [START_REF] Ladier | Scheduling truck arrivals and departures in a crossdock: Earliness, tardiness and storage policies, Industrial Engineering and Systems Management[END_REF]. Earliness and tardiness are considered for both inbound and outbound trucks and a temporary storage of products is allowed. They present and integer program and a heuristics that seek to minimize the storage cost and the penalty costs associated to earliness and tardiness. [START_REF] Agustina | Vehicle scheduling and routing at a cross docking center for food supply chains[END_REF] present a model to treat simultaneously the vehicle routing and the truck scheduling problems, taking into account the consolidation at a cross-dock centre and customer time windows. The mixed integer program they propose seeks to minimize earliness and tardiness penalty costs, the holding and outbound transportation costs. Tested in CPLEX, the first model seems suitable only for small scale problems. In order to treat medium-size real-life instances, an alternative version that simplifies the vehicle routing problem, based on the adoption of customer zones and hard time windows constraints is proposed.

PROBLEM DESCRIPTION AND MODELING

Problem definition

We propose an operation scheduling model at a cross-dock platform to determine the inbound trucks' arrival time, the internal flows between the different stages at shop-floor (temporary staging zones, repacking zone and departure) and, finally, an approximation of the number of outbound trucks needed to fulfil customers' demand. Since the problem treats operational-related decisions, we consider a platform that is already functioning and the following parameters are given as input data:

 The number of inbound and outbound doors. Both are modelled as hard constraints.  The shop-floor capacity is limited. It concerns the storage capacity (temporary staging zones), the package moving capacity and the repack zone capacity. The first two are modelled as soft constraints and the latter as  Since there is a relatively high diversity on the size of packages, all capacities related to shop-floor activities are given in m 3 .  Time space is discretised in periods of a fixed length, which are considered long enough to transport packages between zones and to carry the repack activity (periods of one or two hours).  The previous assumption implies that distances between different shop-floor zones are not considered. The model seeks to minimize internal operation cost and outbound transportation cost. The first one represents the penalty costs associated to the extra capacity needs on shopfloor (temporary storage area and package moving activity). The outbound transportation cost is related to the number of trucks used to fulfil customer demand.

Characterization of the proposed cross-dock centre

Based on the cross-dock settings studied by [START_REF] Ladier | Cross-docking operations: Current research versus industry practice[END_REF] and taking into account the industrial situation described above, we characterize the platform modelled in this paper. Main parameters are presented below (in italics).

First of all, on the strategic level, we assume the shape (physical layout) is not relevant, since the distance between doors is not taken into account in the model. The number of doors is known and we consider internal transportation as manual (workers and forklifts).

Secondly, main characteristics on the tactical level are: an exclusive service mode, since each door is solely dedicated either to inbound trucks or outbound trucks. Pre-emption is not allowed, which means that the loading or unloading of a truck cannot be interrupted. Finally, the temporary storage capacity and the internal resource capacity are limited.

Third and last, on the operational level the cross-dock is characterized as follows: the arrival times of inbound trucks must be established and we assume that all trucks are available at the beginning of the planning horizon.

Outbound trucks content must be defined by the model and their departure time deadline corresponds to the final period of the horizon. Product interchangeability is allowed and for each destination a given demand must be fulfilled (products can be loaded indistinctly in the outbound trucks).

Input parameters and decision variables

The described framework uses the following notation:

∑ k Y i,k,t = RD i,t + S o D i,t + AD i,t ∀i,t (20) ∑ t Y i,k,t = icu i,k ∀i,k (21) ∑ i (Y i,k,t * v i ) <= OT k,t * vc ∀k,t (22)
The objective function in (1) seeks to minimize internal operation cost (storage and package moving) and outbound transportation cost. Equations ( 2) and (3) characterize internal costs and it refers, respectively, to the extra needs on storage capacity and package moving activity. Equation ( 4) characterizes outbound cost, based on the approximation on the number of trucks needed. Constraint (5) guarantees the respect of the number of inbound doors available at the crossdock. Equation ( 6) assures the arrival of all inbound trucks. Arrival flot conservation is represented in (7). Constraints ( 8) and ( 9) are related to global flot conservation. Equations ( 10) to ( 13) describe the flot of temporary staging zones (repack and outbound). Repack zone is characterized from ( 14) to ( 16): flot conservation, assure all concerned products are repacked and respect of total capacity, respectively. Constraints ( 17) and ( 18) link available and extra capacity of temporary staging zones and shop-floor package moving capacity. Equation ( 19) assures the respect of the number of outbound doors available. Constraints ( 20) and ( 21) are, respectively, related to departure flot and total demand. Finally, ( 22) represents the outbound trucks capacity.

NUMERICAL EXPERIMENTS

In this chapter we present the instance generation method as well as the related numerical results. We used CPLEX on a 4GB RAM Intel Celeron P4600 @ 2.00GHz CPU.

Instance generation

The following input data is collected from our case of study:

 An aggregated list of products going through the crossdock platform. For each product, the following associated data is available: v i (volume, m 3 ), rt i (repacking information, approximately 30% of products) and the corresponding supplier and customer. The latter information permits to deduce K (total number of customers) and to calculate icui, k (total product demand per customer).  An estimated outbound trucks costs and capacity: cfc k and vc, respectively.  Inbound transportation data. A given supplier can be affected to dedicated trucks or a milk-run. The rest of parameters are generated based on the following protocol:

 Set the total volume (m 3 ) that will be treated.  Fix the number of inbound (ind) and outbound (oud) and the time periods (T).  Allocate products to inbound trucks, based on supplier and inbound transportation data. We obtain itr i,j and by extension J. The filling rate of inbound trucks is randomly generated within a pre-defined range. Inbound trucks are generated until the total volume (m 3 ) set in 1 is attained. By extension we obtain I and K.  Calculate the average workload per period, for each stage at the shop-floor: staging zones, repack operation and package moving activity. Based on these values we determine cs, crz, ct.

Experiments and results

The last parameters to be set concern the cost distribution for which two different scenarios are proposed, which are based on our industrial experience. For both scenarios we consider that the outbound cost is highly superior to penalty costs. This seems logical if we consider the overseas transportation between a Renault ILN and its customers. Concerning penalty costs, the first cost distribution represents a crossdock platform in which the storage cost is greater than the package moving activity cost. We could imagine a platform with very limited space, but with flexible manpower with a relatively low cost. The second scenario envisages the opposite. One might think of a cross-dock centre situated in a country with a high manpower cost, serving several companies for which the storage space is allocated upon request.

The six problem sets described on Table 1 are run for each cost distribution scenario, resulting on 12 different tests. We consider 5 type of products (2 of which must be repacked), demanded by 3 different customers. Fixing previous parameters, we tested different levels of volume in this way: total number of products varies from 171 to 433. The inbound and outbound doors are between 3 and 4. In terms of number of trucks, they go from 7 inbound trucks and 5 outbound trucks for the smallest one, to 16 and 9, respectively, for the major one.

Table 2 summarize tests' results. Other than the instance size, computational time seems to be related to the cost distribution. In terms of outbound performance, we notice the same result for the two cost distribution scenarios. The difference lies on shop-floor operation. To better asses this impact, we calculate the average load per time period and the standard deviation for the storage level and the package moving activity. Cost distribution #1 shows a highly variable workload on package moving activity, with an average storage level lower than the available capacity (for 5 out of 6 sets). This can be explained because since the storage cost is higher than the packing moving cost. On the opposite, results on cost distribution #2 reveal a smooth workload, close to the available capacity, with a higher occupation of storage space. The latter analysis is illustrated on Figure 3, for the problem set #2. Further tests and analysis with other configurations are needed to better assess the performance of the proposed model. Based on our industrial experience, the cost distribution between inbound, internal and outbound segment can be considerably different from one cross-dock to another and its impact on shop-floor

Fig. 1 .

 1 Fig. 1. Renault ILN supply chain network 2. RELATED WORK Current research work related to cross-docking can be classified by decisional level (Van Belle et al., 2012). Main strategic issues are related to geographical location and shopfloor layout. On the tactical level, papers are focused on network flows, distribution planning and vehicle routing. Finally, operational decisions mainly concern dock door assignment, truck scheduling and shop-floor activity. Our interest is focused on the last two subjects.

  hard constraint. If the cross-dock centre serves several companies, extra storage capacity could be acquired by renting space allocated to another company. Package moving capacity could be obtained by hiring temporary employees. Other important assumptions are:

Fig. 3 .

 3 Fig. 3. Results' comparison between the two cost distributions, for problem set #2

Table 1 .

 1 Problem sets characteristics ://www.sclogistics.com/news-resources/white-papers/41cross-docking-trends-report-1/file]. Serrano, C., Delorme, X.,Dolgui, A. (2015), Distribution and operation planning at a cross-dock platform: A case of study at Renault, 4th IEEE International Conference on AdvancedLogistics and Transport, 193-198. State of the art, Omega, 40, 6, 827-846. Yu, W., Egbelu, P. J. (2008), Scheduling of inbound and outbound trucks in cross docking systems with temporary storage, European Journal of OperationalResearch, 184, 1,[377][378][379][380][381][382][383][384][385][386][387][388][389][390][391][392][393][394][395][396]

	Problem size

http

Table 2 .

 2 Results of numerical experiments.Cost distribution #1: storage cost > package moving cost Cost distribution #2: storage cost < package moving cost

					Storage	Package moving				Storage	Package moving
	Problem	CPU	Outbound	Total	Capacity	Average	Capacity	Average	CPU	Outbound	Total	Capacity	Average	Capacity	Average
	set	(s)	trucks	cost*	(m3 / t)	(m3 / t)	(m3 / t)	(m3 / t)	(s)	trucks	cost*	(m3 / t)	(m3 / t)	(m3 / t)	(m3 / t)
	1	3,5	5	10499	9,4	7,7 ± 5	46,9 50,0 ± 16	3,3	5	10749	9,4 17,8 ± 15	46,9	49,6 ± 5
	2	67,7	5	10752	7,0	8,8 ± 5	35,2 40,9 ± 35	108,6	5	11400	7,0 26,4 ± 12	35,2 40,6 ± 10
	3	9,4	8	16512	16,7	7,0 ± 4	83,3	81,0 ± 6	11,8	8	16512	16,7	7,8 ± 6	83,3	80,1 ± 7
	4 59,7	8	16515	12,5	8,0 ± 5	62,47	62,8 ± 2	237,5	8	16545	12,5	9,8 ± 4	62,0	62,0 ± 1
	5	24,9	9	18921	23,8	11,6 ± 9	119,0 116,1 ± 7	228,1	9	18934	23,8 13,8 ± 10	119,0 117,9 ± 2
	6 32,54	9	23096	21,4	9,5 ± 7	107,2 100,4 ± 7	23,6	9	23094	21,4	17,4 ± 9	107,2 106,4 ± 1