Julien Provost

Jean-Marc Roussel

Jean-Marc Faure

A formal semantics for Grafcet specifications

This paper shows how the behavior of a model described in the specification language proposed by the IEC 60848 standard can be represented, without semantics loss, in a formal manner, by a finite state machine (FSM) with logic inputs and outputs. This contribution is illustrated on a nontrivial example; this case study points out that the duration of the construction of the equivalent FSM complies with the requirements of designers of automation systems.

I. INTRODUCTION

Standardized specification languages have been developed to ease design of industrial systems. To meet this objective, they propose powerful, often graphical, constructs that allow the designers express easily their needs and facilitate communication during the life-cycle. In the case of control systems, the IEC 60848 standard presents a specification language, called Grafcet, which describes graphical constructs to express parallelism, concurrency, rendez-vous, outputs assignment, and other mechanisms frequently met in this class of systems. Unfortunately, no formal semantics of this language is provided, as this is usually the case in standards. This drawback prevents from using formal analysis methods, like model-checking [START_REF] Bérard | Systems and software verification : modelchecking techniques and tools[END_REF], to verify whether a Grafcet behaves as expected once it is built.

The aim of this paper is to tackle out this issue by providing a formal semantics of the IEC 60848 Grafcet language. This will be achieved by representing the full behavior of a Grafcet model in the form of a finite state machine, named Stable Location Automaton (SLA). For room reasons, only non-timed models will be considered in this paper; this limitation is not too strong because the first concern of engineers, during development, is functional correctness, time correctness becoming a concern once functional correctness is ensured.

It shall be noted that similar works have been achieved for the IEC 61131 programming languages [START_REF] Bauer | Verification of plc programs given as sequential function charts[END_REF], [START_REF] Bel Mokadem | Verification of a timed multitask system with UPPAAL[END_REF], [START_REF] Gourcuff | Efficient representation for formal verification of PLC programs[END_REF], [START_REF] Huuck | Semantics and analysis of instruction list programs[END_REF], [START_REF] Rausch | Formal verification of PLC programs[END_REF]. Whatever the value of these works, it must be highlighted that it is more significant, for costs reasons, to analyze specification models, e.g. Grafcet models, before these models are implemented, in the form of PLC programs for instance, because the earlier in the life-cycle flaws are detected, the less expensive flaws removal is; verification of a specification does not prevent from checking the implementation of this specification but facilitates strongly this latter analysis. Moreover, the formal semantics used in the referred works is often that of a specific tool, e.g. a nontimed or timed model-checker, which limits the scope of the contributions, while the method proposed in this paper is based on a generic model which can be translated into several well-known formalisms, like Mealy machines or transition systems.

Several formalization methods of Grafcet specifications have been proposed earlier [START_REF] Lhoste | Grafcet: from syntax to semantics[END_REF], [START_REF] Bierel | Grafcet: from theory to implementation[END_REF], [START_REF] Cassez | Formal semantics for reactive GRAFCET[END_REF], [START_REF] Roussel | Validation and verification of Grafcet using state machine[END_REF]. [START_REF] Lhoste | Grafcet: from syntax to semantics[END_REF] and [START_REF] Bierel | Grafcet: from theory to implementation[END_REF] present a formalization of the Grafcet behavior using a static meta-model. Then, interpretation rules need to be introduce in order to take into account the dynamic aspect of the Grafcet behavior. [START_REF] Cassez | Formal semantics for reactive GRAFCET[END_REF] proposes a formalization of reactive Grafcet (Grafcet with event-based inputs), unfortunately this formalization does not take into account any logical output. [START_REF] Roussel | Validation and verification of Grafcet using state machine[END_REF] proposes a formalization method based on iterative computation of the reachable sets of active steps from the initial set of active steps defined in the Grafcet specification.

More recently, [START_REF] Philippot | From Grafcet to equivalent graph for synthesis control of discrete events systems[END_REF] proposed a formalization of Grafcet for DES control synthesis. This formalization, based on the current version of the Grafcet standard [12], does not take into account the different types of actions associated to the Grafcet steps, e.g. stored actions and conditional actions.

The formalization method proposed in this paper permits to take into account the main features of the Grafcet semantics (conditional and stored actions, macro-steps, ...). Besides, since the knowledge of relations between inputs and outputs is necessary to many verification and validation methods, this formalization extends the one proposed by [START_REF] Roussel | Validation and verification of Grafcet using state machine[END_REF] and puts the stress on the definition of the emitted outputs.

The outline of this paper is the following. The Grafcet syntax and semantics are reminded in Section II. The formal definitions of Grafcet and SLA are given respectively in Sections III and IV while Section V deals with the construction of the equivalent SLA of a Grafcet. This proposal is exemplified in section VI and some perspectives for further work are sketched in section VII.

II. GRAFCET SPECIFICATION LANGUAGE

Grafcet is a standardized graphical specification language [12] to describe the behavior of logic sequential systems. This language is widely used in several industrial domains, like railway transport, electrical power production, manufacturing industry, environment, to specify the expected behavior of a logic control system which is connected to a physical system (plant) that sends logic signals to the control system and receives the logic signals which are generated in response. Grafcet was first standardized in France at the beginning of the 1980s, and at the international level in 1988. Since this date, several extensions have been proposed to enhance the modeling possibilities; they are included in the last version of the standard [12]. A good scientific presentation of the main features of the previous and current versions of the Grafcet standard can be found respectively in [START_REF] David | Grafcet: a powerful tool for specification of logic controllers[END_REF] and [START_REF] Guéguen | Extensions of Grafcet to structure behavioural specifications[END_REF]. Last, the reader is warned that the specification language described in the IEC 60848 standard differs from the SFC (Sequential Function Chart) proposed by the IEC 61131-3 standard [START_REF]Programmable controllers -Part 3: Programming languages[END_REF], even if both are often named SFC in English and if models in these two languages may look similar; the differences stand both in syntax and semantics. The main differences between those two languages will be discussed in subsection 'Differences between Grafcet and SFC'. To avoid misunderstandings, only the term Grafcet will be kept in the sequel of this paper for the specification language.

Grafcet has been developed from the results of the Petri nets community and in particular from those on Interpreted Petri Nets. A specific syntax and semantics have been defined, in a textual way, however in the standard, to take into account the specific needs of engineers when specifying complex sequential systems. The key features of these definitions are briefly recalled in what follows.

A. Grafcet syntax

A Grafcet model describes the expected behavior of a logic controller which receives logic input signals and generates logic output signals; then, the input and output variables of a Grafcet are both logic variables. A Grafcet (Figure 1) comprises steps, graphically represented by squares, and transitions, represented by horizontal lines; a step can only be linked to transitions and a transition only linked to steps. The links from steps to transitions and from transitions to steps are oriented links. The default orientation is from top to bottom and it is not necessary in this case to put an arrow on the link. An arrow must be put on a link if this link goes from bottom to top or may be put on any link to ease understanding. A step defines a partial state of the system and can be active or inactive; hence, a Boolean variable, named step activity variable can be defined for each step. Actions may be associated to a step; an action associated to a step is performed only when this step is active and then acts upon an output variable. A transition condition must be associated to each transition; this condition is a Boolean expression which may include input variables, steps activity variables and conditions on time. As only non-timed systems are considered in this work, only the Grafcets whose transition conditions are built from input variables and steps activity variables are dealt with.

Moreover, macro-steps may be introduced in a Grafcet, to ease modeling. A macro-step, represented graphically by a square with double-lines on top and at the bottom, is a synthetic view of a part of the specification. The detailed description of this part is termed macro-step expansion chart and is a set of connected steps and transitions that starts and ends by only one step, called macro-step expansion input and output steps. Then, a Grafcet model may be composed of several charts: classical charts, that include (normal or macro) steps and transitions, and macro-step expansion charts.

Figure 1 depicts a Grafcet that comprises a part of an example coming from industry. This model is composed of two classical charts (on the left side) and two macro-step expansions (on the right side); these latter charts are the expansions of macro-steps 'M10' and 'M20'.

B. Evolution rules

The detailed behavior of any Grafcet model can be obtained by applying five evolution rules that can be stated as follows: R1 At the initial time, all the initial steps, defined by the model designer and double-squared, are active; all the other steps are inactive. R2 A transition is enabled when all the steps that immediately precede this transition (upstream steps of the transition) are active. A transition is fireable when it is enabled and when the associated transition condition is true. A fireable transition must be immediately fired. R3 Firing a transition provokes simultaneously the activation of all the immediately succeeding steps and the deactivation of all the immediately preceding steps. R4 When several transitions are simultaneously fireable, they are simultaneously fired. R5 When a step shall be both activated and deactivated, by applying the previous evolution rules, it is activated if it was inactive, or remains active if it was previously active. These textual definitions of the evolution rules come from the standard and are obviously not formal; formal definitions of these rules will be given in Section V. However, these rules show that the global state of a Grafcet, called situation, is defined by the set of all the simultaneously active steps; the initial situation of the model of figure 1, for instance, is {A1,30,32,34,36,38}. An evolution from the current situation to a new one corresponds to the firing of simultaneously fireable transitions, according to rules 2 (fireable transitions are compulsory fired) and 4 (simultaneously fireable transitions are simultaneously fired). This new situation may be transient or stable; a situation is transient if at least one transition of the Grafcet can be fired from this situation without change of the inputs values, and stable if no enabled transition is fireable from this situation for the current values of inputs. Then, the state of a Grafcet evolves from stable situation to stable situation, possibly by crossing transient situations. An evolution between two stable situations corresponds, in a Grafcet model, to a sequence (may be reduced to one) of firings of sets of fireable transitions and is instantaneous. Examples of evolutions will be given in section VI, once the formal semantics of Grafcet defined.

C. Actions

Two kinds of actions can be used in a Grafcet to specify the values of outputs: continuous actions and stored actions. An action is graphically represented by a rectangle linked to the step symbol. • A stored action describes how a Boolean value is allocated to an output variable, according to an allocation rule. A rising arrow associated to the action symbol means that the output variable is allocated when the step becomes active. On the other hand, a falling arrow means that the output variable is allocated when the step is deactivated. For the example, output 'LockWheel' is allocated to true (Set) when step 'E20' becomes active and allocated to false (Reset) when step '24' becomes active. It matters to underline that a continuous action is executed if and only if the current situation is stable whereas a stored action is executed whatever the situation.

This set of evolution rules and actions definitions ensures that Grafcet models are deterministic, what is mandatory for controllers' specifications.

D. Differences between Grafcet and SFC

This comparison is based on the two normative texts that define Grafcet and SFC, respectively [12] and [START_REF]Programmable controllers -Part 3: Programming languages[END_REF]. In what follows, the extracts from these documents will be written in italics.

Grafcet is a specification language for the functional description of the behavior of the sequential part of a control system. On the opposite, SFC is an element to structure the internal organization of a program organization unit executed by a PLC (Programmable Logic Controller) and written with one of the four IEC 61131-3 languages (LD, ST, IL, FBD). Then, a Grafcet model is used to specify a behavior regardless of the controller that will be used to implement this specification, while an SFC model describes (part of) the structure of a software running on a PLC.

The semantics of Grafcet and SFC are different. For instance, in case of selection of sequence, exclusive activation of a selected sequence is not guaranteed from the structure, in Grafcet; the designer should ensure that [...] the transition conditions are mutually exclusive. On the contrary in SFC, any sequence selection is exclusive, [...] it cannot have crossing simultaneous transitions in a sequence selection; to do this, the user can define priorities between branches at the divergence of sequence selection.

But the main semantic difference is that the evolutions of a Grafcet model are caused by the changes of its inputs values (event-driven approach) whereas the evolutions of an SFC model are controlled by the input scanning cycle of the controller that executes this model (time-driven approach). When the value of an input of a Grafcet model changes, this model evolves to a new stable situation; this evolution is instantaneous to avoid inputs values changes be missed, even if transient situations are crossed. On the opposite, in an SFC model, the clearing time 1 of a transition may theoretically be considered as short as one may wish, but it can never be zero; in practice, this time is equal to the input scanning cycle time of the controller on which the SFC runs. The consequence is that only one set of simultaneous fireable transitions (may be reduced to one transition) is fired at every scanning cycle. Hence, the concepts of transient and stable situations do not make sense in SFC; a situation lasts at least one cycle time in this case.

III. FORMAL DEFINITION OF A GRAFCET MODEL

Formally, a Grafcet G is a 4-tuple (I G , O G , C G , S InitG ) where:

• I G is the non-empty set of logic inputs.

• O G is the non-empty set of logic outputs.

• C G is the set of Grafcet charts.

• S InitG is the set of initial steps. The charts set C G is partitioned into the set C C of classical charts and the set C E of macro-steps expansions charts.

• A classical chart c ∈ C C is defined by a 3-tuple (S, T, A) where:

-S: non-empty set of steps s of c.

-T : set of transitions t of c.

-A: set of actions a of c.

• A macro-step expansion chart c ∈ C E is defined by a 5-tuple (m, s I , s O , S oth , T, A) where:

m: macro-step name.

s I : input step of the expansion.

s O : output step of the expansion.

-S oth : set of the other steps s of the expansion.

-T : set of transitions t of the expansion.

-A: set of actions a associated to the steps of c. Let S(c) be the set of all steps of the macro-step expansion chart c (S(c) = {s I (c), s O (c)} ∪ S oth (c)). Let S G be the set of all steps s of the Grafcet.

A transition t ∈ T of a given chart c is defined by a 3-tuple (S U , S D , E Cond(I G ,S G ) ) where:

• S U : set of the immediately upstream steps of t.

• S D : set of the immediately downstream steps of t.

• E Cond(I G ,S G ) : transition condition. It is a Boolean expression on inputs and steps activity variables 2 . Let T G be the set of all transitions t of the Grafcet. The set of actions A is partitioned into the set A S of stored actions and the set A C of continuous actions. Similarly, the outputs set O G is partitioned into the set O S of stored outputs (controlled by stored actions) and the set O C of continuous outputs (controlled by continuous actions).

• A continuous action a c ∈ A C of a given chart c is defined by a 3-tuple (s, o, E Cond(I G ,S G ) ) where:

s: step which the action is associated with.

o: output which is assigned by the action.

-E Cond(I G ,S G ) : continuous action condition. It is a Boolean expression on inputs and steps activity variables.

• A stored action a s ∈ A S of a given chart c is defined by a 4-tuple (s,o,op,inst) where:

s: step which the action is associated with.

o: output which is allocated by the action.

op: kind of allocation, op ∈ {Set, Reset}.

inst: instant when the allocation is done, inst ∈ {Act, Deact}, where Act is the step activation instant and Deact the step deactivation instant. For each continuous output, an output condition emission is then defined by a Boolean expression on inputs and steps activity variables, as follows:

E Emit(I G ,S G ) (o) = a∈A C o(a)=o X(s(a)) • E Cond(I G ,S G ) (a) 2 X(s): activity variable of step s
This expression means merely that a continuous output is emitted if at least one step to which is associated an action that assigns this output is active and the condition of this action true.

On the opposite, the values of stored outputs do not depend simply on the values of inputs and steps activity variables but must be computed dynamically during the construction of the SLA, as it will be shown in Section V.

IV. FORMAL DEFINITION OF THE STABLE LOCATION

AUTOMATON (SLA) OF A GIVEN GRAFCET Formally, a stable location automaton SLA is a 5-tuple (I SLA , O SLA , L, l Init , Evol) where:

• I SLA is the set of inputs of Grafcet G:

I SLA = I G (G). • O SLA is the set of outputs of G: O SLA = O G (G).
• L is a set of stable locations l.

• l Init is the initial location, l Init ∈ L.

• Evol is a set of evolutions e.

A stable location is characterized by a set of simultaneously active steps, a set of emitted outputs and a stability condition, Boolean expression on the inputs values. Then, a stable location is defined by the 3-tuple:

(S Act , O Emit , E Stab(I G ) ) where: • S Act is a subset of steps G, (S Act ⊂ S G (G)). • O Emit is a subset of outputs of G, (O Emit ⊂ O G (G)). • E Stab(I G
) is a Boolean expression on inputs of G. This stability condition is true only for the combinations of inputs values for which the location l is stable. An evolution e of Evol is defined to represent an evolution between stable locations. Each one of these evolutions can be formally defined by the 3-tuple: (l U , l D , E Evol(I G ) ), where:

• l U is the upstream location, l U ∈ L.

• l D is the downstream location, l D ∈ L.

• E Evol(I G ) is a Boolean expression on inputs of G. This evolution condition, is true only for the combinations of inputs values for which the SLA evolves from location l U to location l D . An SLA is well-defined if the following seven properties are satisfied:

1) Uniqueness of locations:

∀(l 1 , l 2 ) ∈ L 2 , (S Act (l 1 ), O Emit (l 1 )) = (S Act (l 2 ), O Emit (l 2 )) 2) Uniqueness of evolutions: ∀(e 1 , e 2 ) ∈ Evol 2 , (l U (e 1 ), l D (e 1 )) = (l U (e 2 ), l D (e 2 )) 3) Absence of self-loop: ∀e ∈ Evol, l U (e) = l D (e) 4) Determinism of evolution 3 : ∀(e 1 , e 2 ) ∈ Evol 2 , l U (e 1 ) = l U (e 2 ) ⇒ E Evol(I G ) (e 1 ) • E Evol(I G
) (e 2 ) = 0 5) Distinguishability between stability and evolution:

∀e ∈ Evol, E Evol(I G ) (e) • E Stab(I G ) (l U (e)) = 0 6) Completeness 4 : ∀l ∈ L, E Stab(I G ) (l) + e∈Evol, l U (e)=l E Evol(I G ) (e) = 1
7) Absence of transient location: ∀(e 1 , e 2 ) ∈ Evol 2 , l D (e 1 ) = l U (e 2 ) ⇒ E Evol(I G ) (e 1 ) • E Evol(I G ) (e 2 ) = 0
V. CONSTRUCTION OF THE SLA OF A GIVEN GRAFCET MODEL As previously pinpointed, every evolution of an SLA comes from a change of inputs values. However, two kinds of evolutions may occur in an SLA:

• Evolutions that correspond to the firing of a sequence of sets of simultaneously fired transitions in the Grafcet. • Evolutions that do not correspond to the firing of Grafcet transitions but only to the change of the emitted outputs. In the first case, the set of active steps S Act is changed; this is not true in the second one where only O Emit and E Stab(I G ) are modified. The SLA of a given Grafcet model G is then built from the initial stable location by determining all these evolutions.

From a stable location l = (S Act , O Emit , E Stab(I G ) ), computation of evolutions conditions is performed by symbolic calculus on Boolean expressions on inputs and steps activity variables; if two sets S 1 and S 2 of inputs values combinations are defined by expressions Exp 1 and Exp 2 , then sets S 1 ∩S 2 , S 1 ∪ S 2 , and S 1 \ S 2 are respectively represented by (Exp 1 •Exp 2 ), (Exp 1 +Exp 2 ) and (Exp 1 •Exp 2 ). Locations stability and outputs emission conditions will be computed in a similar manner. This solution avoids combinatorial explosion and is well suited to Grafcet models where transitions and actions conditions are Boolean expressions.

A. SLA evolutions due to the firing of a sequence of sets of simultaneously fired Grafcet transitions These evolutions are determined from a stable location l = (S Act , O Emit , E Stab(I G ) ), by: 1) Looking for the set of fireable Grafcet transitions and all subsets of simultaneously fireable transitions, from the situation S Act . 2) Determining the situation that is reached when each subset of simultaneously fireable transitions is fired; if the new situation is transient, then 1 and 2 are to be reiterated until a stable situation is found 5 . 3) Finding the set of emitted outputs for the stable situation reached by the sequence of firings. In the remainder of this section, these three computations are detailed and illustrated from the stable location

l s = ({A1, 30, 33, 35, 36, 38}, ∅, ((On + Off) • Cam))
of the Grafcet model presented Figure 1. This location is reachable from the initial location and has been selected because it permits to well illustrate the three computations.

1) Phase 1:

A Grafcet transition is fireable when it is enabled and its associated condition true. Hence, the set of enabled transitions t from location l is first computed:

T Enab (l) = {t ∈ T (G) | S U (t) ⊂ S Act (l)}
5 When the sequence of firings is infinite, e.g. a cycle of evolutions from transient situation to transient situation, the Grafcet is said 'not sound' and is to be redesigned.

Thus, it comes for l s : T Enab (l s ) = {t 1 , t 31 , t 36 } Then, T F ire (l) the set of fireable transitions from location l is calculated. This subset of T Enab (l) contains only transitions t for which the transition condition is compatible with the current location:

T F ire (l) = {t ∈ T Enab (l) | E F ire(l) I G (t) = 0}
Where E F ire(l) I G (t) is the simplification of the transition condition of t according to l. It represents the combinations of inputs for which transition t can be fired from location l. This Boolean expression is easily obtained from the transition condition of t by substituting all steps activity variables by their corresponding value (1 or 0) according to S Act (l).

Thus, it comes for l s : T F ire (l s ) = {t 1 , t 31 } since:

E F ire(l) I G (t 1 ) = On • Off E F ire(l) I G (t 36 ) = 0 E F ire(l) I G (t 31 ) = Cam
Let SSF T (l) be the set of couples (SF T, E F ire(l) SF T ) of subsets SF T of simultaneously fireable transitions from l and the corresponding firing condition E F ire(l) SF T . This set is defined by:

SSF T (l) = {(SF T, E F ire(l) SF T ) | [SF T ⊂ T F ire (l)] ∧ [E F ire(l) SF T = 0]} where E F ire(l) SF T = t∈SF T E F ire(l) I G (t) • t∈T F ire (l)\SF T E F ire(l) I G (t)
For l s , SSF T (l s ) comprises three couples:

SSF T (l s ) = {({t 1 }, On • Off • Cam), ({t 31 }, Cam • (On • Off)), ({t 1 , t 31 }, On • Off • Cam)}
2) Phase 2: The situation that is reached when a given set SF T of simultaneously fireable transitions are fired from location l is defined by:

S l SF T = S Act (l) \ t∈SF T S U (t) ∪ t∈SF T S D (t)
Let SS l SF T the set of couples (S l SF T , E F ire(l) SF T ) of situations S l SF T and the corresponding accessing conditions E F ire(l) SF T . For l s , this gives: The first term of each couple of (S l SF T , E F ire(l) SF T ), may be a fully stable situation, a totally transient situation, or a partially transient situation. A partially transient situation is a situation such that the combinations of inputs values can be partitioned into two subsets: a subset that lets the situation stable and a subset that drives the situation transient.

SS ls SF T = {({F1,
Hence, for each situation sit reachable from location l by firing the set SF T of simultaneously fireable transitions, the stability condition E Stab and the transient condition E T ran are to be calculated as follows:

E Stab (sit) = E F ire(l) SF T • t∈T F ire (sit) E F ire(sit) I G (t) E T ran (sit) = E F ire(l) SF T • t∈T F ire (sit) E F ire(sit) I G (t)
If one of these expressions is always false the situation is fully stable or totally transient; otherwise, the situation must be split into two situations, one stable and one transient, according to the subsets of inputs combinations.

From a transient situation sit, computation of the next sets of simultaneously fireable Grafcet transitions and reachable situations from sit is to be reiterated until a stable situation is reached. A continuous action a c is executed from a situation sit if the continuous condition of this action satisfies:

E Exe(sit) I G (a c ) = 0 Where E Exe(sit) I G (a c
) is the simplification of the continuous condition of a c according to sit. It represents the combinations of inputs for which action a c can be executed in situation sit. This Boolean expression is easily obtained from the continuous condition of a c by substituting all steps activity variables by their corresponding value (1 or 0) according to sit.

A continuous output o c is emitted for a stable situation (sit, E Stab (sit)) for the following condition:

E Emit(sit) I G (o c ) = E Stab (sit) • ac∈A(oc,sit) E Exe(sit) I G (a c ) where A(o c , sit) = {a c | [s(a c ) ∈ sit] ∧ [o(a c ) = o c ]} Let SSEO(sit, E Stab ) be the set of couples (SEO c , E Emit(sit) SEOc
) of subsets SEO c of simultaneously emitted continuous outputs from sit and the corresponding emission condition E Emit(sit) SEOc . This set is defined by:

SSEO(sit, E Stab ) = {(SEO c , E Emit(sit) SEOc ) | [SEO c ⊂ O C ] ∧ [E Emit(sit) SEOc = 0]} where E Emit(sit) SEOc = o∈SEOc E Emit(sit) I G (o) • o∈O C \SEOc E Emit(sit) I G (o)
The set of emitted outputs that are controlled by stored actions is determined by analyzing the sequence of firings between two successive stable situations. When a stored action is associated to a step that belongs to a (stable or transient) situation crossed by this sequence, the corresponding output is set or reset, according to the action type. When several stored actions on the same output are sequentially executed during a sequence, only the consequence of the latter one remains.

B. SLA evolutions without firing transitions

These evolutions correspond to changes of the set of emitted outputs while staying in the same situation. They are determined by finding the sets of simultaneously emitted continuous outputs obtained from the combinations of inputs that satisfy this equation (no transition enabled for S Act (l) can be fired).

E Stab = t∈T F ire (l) E F ire(l) I G (t)

VI. ILLUSTRATION ON THE EXAMPLE

A software tool has been developed during this work to automate the construction of the SLA of a given Grafcet by using the above-presented definitions. This tool is available at http://www.lurpa.ens-cachan.fr/isa/teloco.

It has been used for the example presented on figure 1; the SLA of this Grafcet contains 343 locations and 7813 evolutions. The construction of this SLA lasts approximately 30 s, what shows that the use of such a tool in an industrial context is quite realistic. For the studied location l s = ({A1, 30, 33, 35, 36, 38}, ∅, ((On + Off) • Cam)) only 11 evolutions to other stable locations are possible. Table I presents these evolutions, line by line. The first column gives the location that is reached when the evolution occurs, the second column contains the evolution condition (when the source location is active and this condition true, the evolution occurs), the third column the sequence of sets of simultaneously fired transitions from the source to the target location and the continuous outputs calculation. For the fourth and fifth evolutions, for instance, two sets of transitions are successively fired; from the source location, transitions t 1 and t 31 are first simultaneously fired, leading to a transient situation, then transitions t 34 and t 36 are fired simultaneously and the stable locations ({F1,37,E10}, {RotateM1}, Off•Cam•DrawIn•DrawOut) and ({F1,37,E10}, {RotateM1,OutDrawer}, Off • Cam • DrawOut) are finally reached. The difference between these two evolutions is that the evolution condition of the first one does not satisfy the continuous action condition associated to output 'Out-Drawer', whereas the second one does.

For

  l s , these conditions are: E Stab ({F1, 30, 33, 35, 36, 38}) = 0 E T ran ({F1, 30, 33, 35, 36, 38}) = On • Off • Cam E Stab ({A1, 31, 33, 35, 36, 38}) = (On + Off) • Cam E T ran ({A1, 31, 33, 35, 36, 38}) = 0 E Stab ({F1, 31, 33, 35, 36, 38}) = 0 E T ran ({F1, 31, 33, 35, 36, 38}) = On • Off • Cam 3) Phase 3: For each stable situation, it is necessary to determine the emitted outputs.

In Boolean equations, 0 means False, 1 means True

For each location and for each combination of inputs values, the behavior is completely defined (either the location is stable, or there exists an evolution from this location).

This work is funded by the French Research Agency (TESTEC project, Ref. TLOG 07-022)

VII. CONCLUSIONS AND PROSPECTS

A proposal to endow the Grafcet model with a formal semantics is the main contribution of this paper. On this basis, any non-timed IEC 60848 model can be translated into an equivalent formal model, a FSM with inputs and outputs, which can be used for verification purposes or to build conformance test sequences [START_REF] Provost | Translating Grafcet specifications into Mealy machines for conformance test purposes[END_REF]. The knowledge of the SLA permits for instance to check absence of deadlock, reachability of particular locations, possibility of firing sequences or absence of conflicting outputs at every moment. Moreover, experiments have shown that this translation is fast enough to be integrated into industrial environments for automation systems development.

Further work is aiming at extending this contribution by focusing on timed systems. Timed constructs of Grafcet, timed actions and transition conditions with timed constraints on time, will be then to consider and the semantics shall be expressed by a timed extension of the SLA.


Guillaume Raschia
email: guillaume.raschia@univ-nantes.fr

Adeel Anjum
email: adeel.anjum@etu.univ-nantes.fr

Spatial Indexing Techniques for Privacy-Preserving Data Publishing (position paper ) L'indexation spatiale au service de la publication de données qui préserve la vie privée

Keywords: H.2.8 [Information Systems]: Database Management-Database applications; E.1 [Data]: Data Structures Anonymization, Spatial Indexing, Point Access Method

Il existe une littérature foisonnante au sujet de l'anonymisation de données par généralisation des valeurs d'enregistrement. Les contributions portent soit sur le modèle de généralisation, enrichissant le K-anonymat de L. Sweeney, soit sur un algorithme de calcul d'une version anonymisée d'un jeu de données, étant entendu qu'il a été prouvé que le problème est N P-difficile, et donc que la plupart des algorithmes offrent des solutions approchées.

Les méthodes d'accès spatiales (MAS), bien étudiées dans le champ des bases de données, suscitent un intérêt grandissant dans le contexte de l'anonymisation de données par généralisation des valeurs d'enregistrements, étant données (i) leur capacité à atteindre des grandeurs d'échelle inégalées par d'autres approches, et (ii) l'adéquation du format des entrées de l'index avec les données anonymisées.

Nous proposons dans cette communication un état des lieux et une analyse critique des MASs étudiées sous l'angle de l'anonymisation de données. Nous évaluons les propositions existantes et suggérons des pistes de travail encore non explorées à ce jour.

INTRODUCTION 1.1 Motivation

As stated by Jim Gray [START_REF] Hey | The Fourth Paradigm: Data-Intensive Scientific Discovery, chapter Jim Gray on eScience: A Transformed Scientific Method[END_REF], we are entering the fourth age of science defined by a new paradigm where data play a central role in the production of science and innovation. To achieve that bright vision, scientific data must be unleashed from private repositories, and publicly released for the all research community. The Open Access movement, first concentrated on free access to scientific publications, turns now to Open Data initiative. In the same time, new business models have emerged to offer valuable services and take benefits from open data.

Then, organizations are strongly encouraged to release their micro-data to support data analysis, to provide new business opportunities and to allow every kind of scientific study and to support data journalism as well. For example, patients' medical records may be released by a clinic to support medical research and epidemiological studies.

However, releasing medical records about individuals violates their privacy thus, Privacy-Preserving Data Publishing (PPDP) has become a critical issue for companies and organizations. To obviate identity disclosure, many organizations usually remove the uniquely identifying information like name, SSN or IP address from the public release. However, as stated first by Latanya Sweeney in [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF], observing a 30-year tradition of inference problem in statistical databases, this sanitization of data might not be helpful in keeping the secrecy of given individuals since several attributes, coined quasi-identifiers, if they are put together, could surely lead to identity disclosure.

Preliminaries

This gave rise to the need for robust sanitization methods to publish sensitive individual data keeping their privacy intact. The seminal K-anonymization paradigm [START_REF] Sweeney | k-anonymity: A model for protecting privacy[END_REF] was proposed to achieve this goal by means of a generalization model. Basically, anonymization based on generalization consists in decreasing accuracy of values from quasi-identifiers. For instance, 44100 Zip code would become 44XXX and 70 pounds would be said to range between 50 and 80 pounds. More precisely, a table satisfies K-anonymity if every record is indistinguishable on quasiidentifiers from at least K -1 other records. This indistinguishability principle supports an equivalence relationship on the records of an anonymous public release and prevents from identity disclosure of individuals with a probability of

Typical Use Case

Public release supports exploration, analysis and scientific studies. The very first and popular processing of public release is then to search and filter tabular data by the way of point queries and window queries. Indeed, regular database records can be geometrically interpreted as points in a multidimensional space where each dimension is a column of the raw table. Point coordinates are then defined by attribute values. Transformation is obvious for numerical and ordinal variables. Categorical variables could also be equipped with a total ordering, except that without any "native" ordering, the process is driven by the application domain and background knowledge.Thus database queries are transformed into queries against a set of points.

Translated to anonymous public releases, sanitized records become hyperrectangles in a multi-dimensional space, where each dimension is a field in the set of quasi-identifiers. For instance, sanitized records from To achieve such querying scenario, anonymous records are mutually disjoint spatial objects with a rectangular extent and window queries are orthogonal range queries. And any record that overlaps/lies within query region is a member of the result set. There exist many efficient algorithms and data structures [START_REF] Agarwal | Range searching[END_REF] to compute such orthogonal range queries against the spatial representation of the anonymous database. Furthermore, since any orthogonal range query can be decomposed into a collection of 1-dimensional range queries, it is then easy to manage filters on the tabular representation of the public release within a basic spreadsheet or web-client technologies as well. Query Q2 over Table 1 gives an example of such straightforward decomposition. Those practical features are very useful in lots of iterative exploration processes that would support analysis and scientific studies. Then, we argue that the axis-parallel rectangular coding of anonymous records is a strong requirement for a generic PPDP task.

Other kinds of range queries are defined by the shape of query region: sphere, half-space, simplex, polytope. Sphere range queries, so-called nearest-neighbor queries have been extensively studied and there also exist efficient algorithms to compute such popular queries especially on rectangular objects. However, none of these range queries satisfies the decomposition property that makes anonymous releases human-friend under tabular representation.

Summary of the Requirements for PPDP

To sum-up the above discussion, we argue that every generic PPDP task should meet at least the following theoretical and practical requirements in order to be valuable for the end-user:

1. Indistinguishability principle -to ensure K-anonymity;

2. Mutually disjoint equivalence classes -to preserve quality of the anonymous public release;

3. Multidimensional point partitioning -to support point and range queries on the anonymous public release;

4. Hyperrectangular coding of equivalence classes -to allow decomposition of orthogonal range queries.

To follow-on

Section 2 reviews existing structures that support anonymization algorithms, and it presents features of the main logical structures eligible for a PPDP task. Next, Section 3 focuses on a special kind of those structures, so-called nested hyperrectangle-based bucketed point access methods, that have very nice features for the anonymization. Definition and searching strategies for such structures are provided. Then, Section 4 states several open issues to address in order to accommodate and optimize the index structures to the PPDP task.

POINT ACCESS METHODS

Point Access Methods (PAMs) are logical structures that organize a set of point for efficient searching. We will see in this section that PAMs have features that are suitable for the anonymization problem, and as such, we argue in the following that they are the preferred data structures to support K-anonymization algorithms.

Point Partitioning for PPDP

It is worth to notice that public release with one single equivalence class described on each dimension by the all domain is obviously K-anonymous (K ≤ n the number of records) but it is definitely useless for the end-user. Thus, the main challenge of K-anonymization is to compute a public release where the information loss has been minimized, in the sense of a general criteria such like certainty metric [START_REF] Xu | Utility-based anonymization using local recoding[END_REF], discernibility penalty [START_REF] Bayardo | Data privacy through optimal k-anonymization[END_REF] or KL-divergence [START_REF] Kifer | Injecting utility into anonymized datasets[END_REF] for the most popular ones. This optimization problem was proved to be N P-hard [START_REF] Meyerson | On the complexity of optimal k-anonymity[END_REF].

Hence, many approximation algorithms have been proposed in the literature since the seminal work of L. Sweeney [START_REF] Sweeney | Achieving k-anonymity privacy protection using generalization and suppression[END_REF]. Usually, Mondrian approach [START_REF] Lefevre | Mondrian multidimensional k-anonymity[END_REF] is thought as the baseline algorithm since it has the basic good properties we could expect from such algorithms: local recoding and multidimensional partitioning. Mondrian iteratively operates a binary partitioning of the data space until every block contains between K and 2K -1 points. Actually, Mondrian builds a kd-tree over the raw data and publishes bounding boxes of the leaves as equivalence classes of the anonymous release. Construction has time complexity

O(N • log N ),
where N is the number of records in raw data.

Following the geometric representation of the data, Iwuchukwu et al. [START_REF] Iwuchukwu | K-anonymization as spatial indexing: Toward scalable and incremental anonymization[END_REF] propose to use a bulk-loading implementation of an R + -tree, one of the most popular spatial access methods for databases, to compute the K-anonymous release. It outperforms Mondrian thanks to buffering and efficient bottom-up index construction algorithm, and it scales up to very large data sets. Furthermore, the hierarchical structure of the R + -tree natively supports (B ℓ K)-anonymity for all level ℓ in the tree, with B the fanout parameter. And with an ordered leaf scan, it could support (cK)-anonymity as well, for all c in N. Time complexity remains in O(N • log N ). And

I/O cost for external computation is in O(N/B • log N/B).
Since the R + -tree bulk-loading algorithm is applied on a set of points rather than a set of spatial objects with an extent, it is actually a variant of a kd-B-tree structure where hyperrectangles have been shrinked to the minimum bounding boxes (MBB) of the subset of points in each equivalence class. Remind that a kd-B-tree is a bucket-oriented variant of a kd-tree where the fanout of each node is defined by parameter B that usually fits the disk block size. The many good features of the R + -tree approach makes it therefore the reference algorithm for K-anonymization until now.

Many works also proposed point partitioning structures in low dimension (2-3D) for privacy preserving location-based queries [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF][START_REF] Ghinita | Private queries in location based services: Anonymizers are not necessary[END_REF][START_REF] Mokbel | The new casper: Query processing for location services without compromising privacy[END_REF][START_REF] Damiani | The probe framework for the personalized cloaking of private locations[END_REF]. In this application domain, privacy is related to instant location of users and queries as well. Popular approaches design an anonymizer that dynamically provides a Cloaking Region to the Location-Based Service. For that purpose, Gruteser et al. [START_REF] Gruteser | Anonymous usage of location-based services through spatial and temporal cloaking[END_REF] implements a kd-tree, whereas Mokbel et al. [START_REF] Mokbel | The new casper: Query processing for location services without compromising privacy[END_REF] uses a variant of a PR quadtree in Casper. Ghinita et al. [START_REF] Ghinita | Private queries in location based services: Anonymizers are not necessary[END_REF] accommodate partitioning structures from kd-tree and R-tree to hash a database of Points Of Interest (POI) and answer approximate nearestneighbor queries in a Privacy Information Retrieval (PIR) approach. They also consider Hilbert space filling curves to map 2D points to single-dimensional data structures like B + -trees to index POIs. Actually, they argue that their PIR approach is independent from the partitioning structure as far as it provides at most √ N buckets within up to √ N POIs each. Other work [START_REF] Krishnamachari | Privacy-preserving publication of user locations in the proximity of sensitive sites[END_REF] focused on geo-privacy in the sense of privacy-preserving location data publishing. In this context, a space filling curve was also employed to order both data points and POIs on the map. Quad-trees and space filling curves do not scale for higher dimensions, and the latter cannot guarantee non overlapping bounding boxes in the worse case.

The above short review states that every approach to geoprivacy accommodates in memory and implements well-known structure for multi-dimensional point data partitioning. K-anonymity were also studied from the cardinality constraint clustering point of view. On the one hand, anonymization algorithms were proposed [START_REF] Byun | Efficient k-anonymization using clustering techniques[END_REF][START_REF] Chiu | A k-anonymity clustering method for effective data privacy preservation[END_REF][START_REF] Aggarwal | Achieving anonymity via clustering[END_REF] that achieve good quality, whereas neither they scale up in the size of the data set, nor they meet the basic orthogonal range query requirement since patterns are spheres (centers and radius) of each cluster. On the other hand, many grid clustering techniques ( [START_REF] Wang | STING: A statistical information grid approach to spatial data mining[END_REF][START_REF] Pilevar | GCHL: A grid-clustering algorithm for high-dimensional very large spatial data bases[END_REF] for a short excerpt) have been proposed. However, none of them are as fast and scalable as Point Access Methods (PAM) since external storage support and dedicated insert-delete-search operations are missing. Then, PAMs remain the preferred logical structures for the anonymization of very large data sets.

Comparative Analysis of PAMs

For an insight into multi-dimensional Point Access Methods, the reader is strongly invited to refer to the first chapter of [START_REF] Samet | Foundations Of Multidimensional And Metric Data Structures[END_REF]. In Table 2, we present a short comparison between the most popular PAMs that could be of interest for PPDP task. For the sake of simplicity, we omit the multiple extensions of each structure, available in the literature, since the main criteria of our comparison are inherent to each structure such that they remain valid whenever the extension.

Criteria are as follows:

• bucket? -decides whether the PAM is bucketed or not, i.e. each element of the logical structure has a parametrized size rather than a fixed-length size. Bucket PAMs are those that could be used as spatial indices for databases since the bucket size B is set to the disk page size and then, the I/O cost of such structures is controlled. • orientation -separates PAMs into 2 categories: those that decompose the underlying space, and those that aggregate the data points. The former are top-down since they iteratively divide the space to build the blocks, and the latter are bottom-up since they operate from the data to the blocks;

• shape -blocks of the partitioning could have various shapes in the space. The most simple but popular one is the hyperrectangle (HR);

• grid? -decides whether pre-defined scales support the PAM or not, such that every partition line follows a grid in the space. PAMs with such feature adopt regular decomposition.

• done -already used into an anonymization approach? (see Section 2.1 above for a review).

The 5 first raws of Table 2 refer to in memory structures. Except the BSP tree, all of them build (nested) hyperrectangular ((N)HR) blocks, thus they meet the PPDP requirements as stated in Section 1.4. The NHR property will be discussed further in Section 3.1. The BSP tree builds convex polytopes that do not allow to decompose orthogonal range queries then it is not eligible for a PPDP task. The only BD-tree, that builds nested HRs, has not already been support of an anonymization process.

The all remaining raws are Bucketed PAMs (BPAMs) that is, indexing structures for point databases. Among them, the 4 first structures generate HR blocks, whereas the 3 last ones provide nested HRs. The only R + -tree was used for PPDP until now.

Moreover, we argue that bottom-up spatial indexing is not systematically more efficient than top-down approaches as opposed to the conjecture from [START_REF] Iwuchukwu | K-anonymization as spatial indexing: Toward scalable and incremental anonymization[END_REF]. This result is given by our own experiments comparing in the same running environment R + -tree approach (bottom-up) with the BANG file (top-down). Following usual analysis on spatial access methods, we claim that the performance is mainly dependent from the splitting strategy. In the BANG file, we use regular decomposition following the grid whereas the original R + -tree grows by means of a quadratic procedure comparing pairwise distances of elements in an overflow bucket.

Those strategies determine a constant factor (w.r.t. N , the number of points) in time complexity that makes the execution time slower for the R + -tree. Hence, both top-down and bottom-up approaches deserve to be studied in the context of PPDP.

Finally, the grid-based PAMs have the ability to support background knowledge in the space decomposition process by means of dimensional scales. Consequences are multiple. First, the block splitting strategy is straightforward since scales have been pre-defined over each dimension, so that the algorithm performs very well. Second, the lowest K value is given by the density of the finest regions in the grid.

Hence the user controls the privacy requirement by means of the grid resolution rather than a parameter K. Obviously, grid resolution could be adapted to match a given K value when needed.

Focus on Bucketed PAMs

Bucketed PAMs (BPAMs) are well-suited for the anonymization task. The very first reason is that BPAMs fulfill the basic requirements for PPDP as stated in Section 1.4. But BPAMs have many other nice features that could be of interest in the context of PPDP. First, since they support spatial indexing techniques in databases, they leverage 30years research and experience in effective and efficient multidimensional partitioning data structures built from very large data sets. Thus, they scale up and perform very well.

Next, BPAMs natively offer basic insert-delete-search operations that straightforwardly make the anonymization process incremental. It then supports dynamic updates of the dataset before the generation of the anonymous public release, and it provides a framework to study the open issue of continuous publication.

Moreover, BPAMs require a search operation to perform at least in O(log n) to be efficient. Thus, they all develop a hierarchical structure, so-called tree directory, that makes possible multi-granular anonymization with partitioning extraction at any level in the tree. The only exception would be the Grid file that performs in O(1) such like linear hashing, having the main drawback of a low filling rate in each block and a large and sparse directory.

NESTED HYPERRECTANGLES

We focus in this section on a category of BPAMs: those with nested hyperrectangle blocks. We first present their features and then we discuss about open issues such that they could effectively support PPDP tasks.

Features of NHR-based BPAMs

We argue that. . .

Point and Range Queries against NHRs

Remind that one of the PPDP requirements is to provide user-friend descriptions of anonymous data set to ease point and range searching in very simple but popular environments such like spreadsheets. Remind that point queries and orthogonal range queries both have the property of being decomposable into dimensional filters. HR-based BPAMs are obviously tailored to fulfill such requirement. We argue that anonymous public releases built with NHR-based BPAMs could also support point and orthogonal range queries, without disregarding quality and efficiency of the anonymization process.

Then, we present a first attempt to resolve point and orthogonal range queries against NHRs within a tabular representation of anonymous records. To this end, each equivalence class of the public release is encoded by its enclosing hyperrectangular region such that nested regions are allowed in the table. And the partitioning level of each region is provided in an additional column. Hence, it becomes very easy to process point queries in the anonymous table :   1. define filters on each dimension; Orthogonal range searching is slightly more difficult to manage. Indeed, if we follow the above point query process, defining range filters rather than exact match filters, then we are left with false negatives since enclosing regions could be partly covered by the range query. At the contrary, if we stop at step 2, then there could be false positives in the answer set.

Then, we propose the following methodology to manually perform orthogonal range searching in anonymous public releases. The query is first decomposed into elementary range queries that cover the entire query space with small cuboids that correspond to the finest resolution of regions in the public release. The resolution can be determined by means of the highest level value. Obviously, the resolution depends on the K value for a given public release. Then, each elementary range query is performed in the same way than point queries, except that filters on dimensions are ranges rather than exact matching. Finally, the answer set is the union of all the elementary range query results.

For instance, assume a range query Q that spans the subspace of A shown on Figure Obviously, the BPAM tree directory remains available for very large data sets and could be used as a regular database access method for any kind of range queries over the leaves of the index structure (the M -anonymous release).

DISCUSSION 4.1 Extension to other generalization models

K-anonymity is the very first generalization principle to achieve sanitization of data. Its main purpose is to prevent from identity disclosure. Other more sophisticated models have emerged in recent years to overcome shortcomings of K-anonymity, especially the attribute disclosure risk. Among the most popular generalization principles are ℓdiversity [START_REF] Machanavajjhala | Venkitasubramaniam. l-diversity: Privacy beyond k-anonymity[END_REF] and t-closeness [START_REF] Li | t-closeness: Privacy beyond k-anonymity and l-diversity[END_REF].

As stated in [START_REF] Iwuchukwu | K-anonymization as spatial indexing: Toward scalable and incremental anonymization[END_REF] for the R + -tree, any BPAM would be able to incorporate constraints from the definition of the various existing generalization models in its anonymization process.

The only accommodation would be to redefine the assignment and splitting strategies such that both resulting blocks satisfy the generalization model. For instance, to make the anonymous release ℓ-diverse, it requires that at least ℓ sensitive values are "well represented" in each equivalence class. Thus, the algorithm would incorporate checking on sensitive values in its splitting decision to only create new ℓ-diverse blocks from old ones. And it would add constraint on assignment of a new point into an existing block such that the resulting block still satisfies the ℓ-diversity, otherwise the algorithm would locally redistribute points into blocks.

Many other models of anonymization exist in the literature, such like the ε-differential privacy [START_REF] Dwork | Differential privacy[END_REF] to prevent from probabilistic attacks, but they do not use generalization to preserve privacy of records and they are far from practical approaches for most of the current anonymization requirements in real-life. For a comprehensive review of anonymization models and algorithms, the reader is invited to refer [START_REF] Fung | Privacy-preserving data publishing: A survey on recent developments[END_REF].

Compaction procedure

In [START_REF] Iwuchukwu | K-anonymization as spatial indexing: Toward scalable and incremental anonymization[END_REF], the authors propose a compaction procedure that simply shrinks the envelop of each block to its MBB as shown on Figure 2. Consequently, the average volume of the blocks is minimized.

The R + -tree approach natively computes such MBBs for every block. However, top-down NHR-based BPAMs operate a decomposition of the space such that the union of all the blocks spans the entire space. Obviously, a compaction of each block would yield to a more accurate anonymous public release, and would still increase its quality. Thus, it can be considered as a straightforward improvement of top-down NHR-based BPAMs, even if computation of non hyperrectangular "MBB" such like those on Figure 3 must be carefully defined first.

CONCLUSIONS

In this communication, we advocated the use of Bucketed Point Access Methods for Privacy-Preserving Data Publishing tasks. We focused on the K-anonymity generalization model for data anonymization. We first reviewed the existing approaches based on multidimensional point partitioning. Then, we presented an almost comprehensive list of PAMs eligible to the PPDP task. We argued that Nested HyperRectangle-based BPAMs are the most promising structures to support PPDP. Then, we considered decomposable point and range queries against tabular representation of anonymous public releases, and we proposed a first attempt to answer such queries. Finally, we discussed about obvious extensions to various generalization models and compaction of NHRs to Minimum Bounding Boxes.

As a follow-on of that study, there could be many tracks to investigate. First, it is obvious that several instances of NHR-based BPAMs must be implemented and compared for K-anonymization. Next, extensions to other generalization models could be experimented as well. Besides, the development of a toolbox that supports search and analysis of nested hyperrectangular anonymous records would be highly valuable. Indeed, we argue that those shapes are the most sophisticated ones that could be managed by regular end-users. And finally, the definition of a compaction procedure for NHRs is also an interesting problem in the field of computational geometry.

.

  . . NHR-based BPAMs are the most sophisticated and suitable logical structures to support PPDP tasks.

Figure 2 :Figure 3 :

 23 Figure 2: Low quality binary partitioning of a set of 6 points into blocks of at least 3 points, following either (a) X-axis, or (b) Y-axis.

Figure 4 :

 4 Figure 4: Example of a 2D data space partitioned with NHR-based BPAM into 7 nested regions {A, B, C, D, E, F, G}.

Figure 5 :

 5 Figure 5: Example of a sub-space spanned by a range query on the partitioning of Figure 4.

Table 1 :

 1 Example of a 3-Anonymous Public Release (with raw values into bracket).

	Id	Age	Zipcode	Gender Disease
	(1) [48-62] (62) 441XX (44120) * (F)	Flu
	(2) [48-62] (51) 441XX (44190) * (M)	Flu
	(3) [48-62] (48) 441XX (44100) * (M)	HIV
	(4) [59-77] (59) 444XX (44470) * (F)	Flu
	(5) [59-77] (77) 444XX (44420) * (M)	Gastritis
	(6) [59-77] (66) 444XX (44420) * (M)	HIV
	1/K.
	Table 1 provides a toy example of a public release of 6 med-
	ical records following 3-anonymity, i.e. each public record
	is identical on quasi-identifiers (Age, Zip and Gender ) with
	at least 2 other records. For instance, records 1, 2, 3 from
	Table 1 belongs to the same equivalence class and are in-
	distinguishable one with each other. Pattern of the class is
	(Age=[48-62], Zip=441XX, Gender=*). Similarly, records
	4, 5, 6 form the second equivalence class.

Table 1

 1

are cuboids in the 3dimensional space (Age, Zipcode, Gender) as shown by Figure

1

. As a point query example Q1, user would filter data to retrieve possible patient's record designated by Age=62 AND Zip:=44120 1 AND Gender:=F 2 and she would be returned the answer set {1, 2, 3} from Table

1

. Similarly, an example of a window query Q2 would yield to searching for patient's records satisfying Zip IN [4442X,4447X] AND Age>=50 AND Gender=*. It would then return the set {4, 5, 6}.

Table 2 :

 2 Comparison of index structures for multidimensional point data. HR stands for HyperRectangle, NHR is Nested HR, CP means Convex Polytope.

	Those structures are external or secondary
	storage structures and then, they can grow as much
	as the size of the data set requires to, without main
	memory limitations;

  ) is a false negative. To fix this wrong behavior, the above methodology for range searching first decomposes the query into 3 elementary queries Q (1) , Q (2) and Q (3) that span respectively the sub-part of D, region E and region G. Values of dimensional filters are given by the examination of bounds in each column of the equivalence classes. Next, Q (1) is computed as a point query (with range filters) and gives the intermediate result set {(A, 0), (D, 1)}. Then the answer is [D]. The process is repeated for Q (2) and Q (3) and it returns resp. [E] and [G]. Union of the 3 result sets is the answer to Q.

	5. Step 2 of point queries with
	range filters returns the intermediate result set {(A, 0), (D, 1), (E, 2), (G, 2)}, whereas step 3 gives {(E, 2), (G, 2)}. In the former result set, (A, 0) is a false positive, and in the later re-
	sult set, (D, 1


H Aljewifi
email: hana.aljewifi@u-cergy.fr

B Fiorio
email: bruno.fiorio@u-cergy.fr

J-L Gallias
email: jean-louis.gallias@u-cergy.fr

Groups of physical parameters influencing the three stages pull-out behaviour of glass multifilament yarns embedded in micro-concrete

Five different continuous glass yarns have been embedded in cement based micro concrete. The pull-out behaviour of the yarns has been characterized by the way of a classical pull-out test when the physical state of the impregnation has been characterized by different dedicated methodology (differential mercury intrusion porosimetry, flow test, SEM characterization). By studying the correlation between the mechanical behavior and the physical properties of the impregnated yarns, groups of physical parameters have been identified as associated to each of the three stages of the pull-out behavior. The overall result of this work is a better understanding of the relationship between, on one hand, the physical state and the impregnation of the yarns and, on the other hand, the pull-out behavior.

Introduction

Glass fiber reinforced cement composite have been used for many nonstructural applications since the early 1970s. An important step in the development of this kind of reinforcement was the introduction of the first alkali-resistant (AR) glass fiber by Pilkington about three decades ago [START_REF] Jesse | The present and the future of textile reinforced concrete[END_REF]. As glass fibers are not sensitive to corrosion, unlike steel, the concrete cover can be reduced in order to minimize the thickness of the structural members. This reduction is particularly high in the case of textile reinforced concrete (TRC).

The properties, performances and applications of TRC have been described by many authors [START_REF] Brameshuber | Textile reinforced ultra high performance concrete[END_REF]. Current studies have confirmed that complex processes of interaction occur inside the composite between the yarns and the cementitious matrix, and inside the yarns between the glass filaments and the penetrating cement paste or between the filaments themselves [START_REF] Konrad | Textile Reinforced Concrete Part II: Multi-Level Modeling Concept in proceedings: Internationales Kolloquium über Anwendungen der Informatik und der Mathematik in Architektur und Bauwesen[END_REF]. These interactions are largely influenced by the yarns impregnation, and govern the mechanical properties of the TRC.

The purpose of this paper is to present results of measurements of different physical parameters related to the yarn impregnation made for different yarns and different impregnation conditions and to study the relationship between these parameters and the mechanical pull-out behaviour.

Especially, attention was paid to the relationship between the physical state of the impregnation and the three stages of the pull-out behaviour.

Glass yarn embedded in matrix

Yarn impregnation

Five different kinds of multi-filament yarns have been used in this work (the basic properties of the yarns are given in table 1). It should be noticed that the geometrical properties of the yarns are much more numerous than given in table 1, due to the multi-scale assembly of the filaments. Moreover glass filaments were coated by sizing which influenced the yarns processing but also the adhesion with the matrix. Yarns were centered in a cylindrical shape cementitious matrix using a specific mold [START_REF] Aljewifi | Characterization of the impregnation by a cementitious matrix of five glass multi-filament yarns[END_REF]. The matrix was a micro-concrete made from CEM I cement (0.48 water on cement ratio; 1.4 sand on cement ratio with 0-1.25mm sand; a superplasticizer was used with a dry extract dosage of 0.125 % of the cement mass). Properties of the matrix were as follow: 2.135 g/cm3 density, 31500 MPa Young's modulus, 55 MPa compressive strength. Before casting, yarns were applied one of the three following pre-treatments: water pre-wetting (W); air drying (D); mechanically induced pre-impregnation by a cement slurry (PI; composition of the slurry was identical to those of the cement paste of the matrix). The pre-treatment had an influence on the resulting impregnation of the yarn by the matrix [START_REF] Aljewifi | Characterization of the impregnation by a cementitious matrix of five glass multi-filament yarns[END_REF].

Physical characterisation of the impregnation

Impregnation of the yarns was characterized by the mean of three different techniques: SEM observations of longitudinal section of impregnated yarns, flow rate measurements, differential mercury intrusion porosimetry.

The SEM observation allows the average penetration depth of the cementitious matrix into the yarn to be determined. An impregnation index i y was defined as the ratio of the impregnated area to the apparent area of the cross-section of the yarn [START_REF] Aljewifi | Characterization of the impregnation by a cementitious matrix of five glass multi-filament yarns[END_REF]. It was determined considering a cylindrical shape of the yarn with constant penetration depth of the matrix.

The values of the impregnation index significantly vary with the pre-treatment applied to the yarn. W pre-treatment, by water-saturating the porosity of the yarn, prevents the yarn from matrix penetration and gives low values of impregnation index. D pre-treatment leads to a moderate increase of the impregnation index for SG2, SG3 and OC1 yarns when the increase was almost unobserved for SG1 and OC2 yarns. This can be explain by a filter effect of the glass filaments, that stops the in-depth penetration of the water carried cement particles during the wetting of the yarn. The wettability of the yarn, which depends on the type of sizing, is also an influential parameter. PI pre-treatment, by forcing the introduction of matrix inside the yarn, allow the full impregnation (100%) to be obtained.

Flow rate measurements were achieved on 2cm thickness sample of micro concrete in which a pre-treated yarn was embedded. The test consists in measuring the steady state flow rate of water along the yarn, under a 107.5 kPa/cm pressure gradient [START_REF] Aljewifi | Characterization of the impregnation by a cementitious matrix of five glass multi-filament yarns[END_REF].

Mercury intrusion porosimetry (MIP) was used to determine the total pore volume of samples of embedded yarns and surrounding cementitious matrix. Samples were obtained by coring the center of the cylindrical specimens detailed in 2.1. By comparison with reference matrix samples for capillary diameter in the range 0.3 to 30µm, the void volume inside the impregnated yarn was determined (see [START_REF] Aljewifi | Characterization of the impregnation by a cementitious matrix of five glass multi-filament yarns[END_REF] for details). It is called "yarn pore volume" in the following.

Fig 1,

left, shows the relationship between the impregnation index and the flow rate measurement. Flow rate decreases when the impregnation index increases, which is the consequence of the matrix filling of the inter-filaments voids. For low impregnated yarns, water is in direct contact with glass filaments and the flow rate depends on the wettability of the yarn when for high impregnation there is no influence of the yarn (flow occurs in the porosity of the matrix).

Fig 1, right, gives the relationship between the impregnation index and the yarn pore volume. This volume is generally more important when the impregnation index is high, due to the disorder in the filaments organization induced by the introduction of the matrix. This is particularly the case for PI pre-treatment for which a mechanical action is required.

Mechanical pull-out behaviour of the embedded yarns

Testing method

The load-displacement (P-δ) curves for pull-out tests were obtained from tension test performed with a universal testing device (30 kN capability) as described in [START_REF] Aljewifi | Pull-out behaviour of a glass multi-filaments yarn embedded in a cementitious matrix[END_REF]. The pull-out tests were made by applying a tensile load on the free end of a yarn, which extremity was embedded in a micro-concrete cylinder (6 embedded lengths have been used in the range 1 to 25 cm). The free length of the yarn was 10 cm. Loading was applied at constant strain rate (0.01 mm/min). Three tests were performed for each configuration (one set of yarn type, pre-treatment type, and embedded length). Three different stages are usually observed for the pull-out behaviour of yarns (St1 to 3 in fig 2). The first stage (St1) corresponds to the progressive loading of the filaments. It is characterized by delayed activation of the filaments associated to the progressive failure of some of them. In the second stage of the behavior (St2), the maximum strength is reached and a majority of filaments progressively failed, leading to a progressive fall of the load when the pull-out displacement is in-

Contribution of the embedded length to the pull-out behaviour

The evolution of the maximum pull-out strength P max for increasing embedded length is given in fig 3 (example of SG1 yarns). The pull-out strength increases when the embedded length increases as long as the embedded length is lower than a threshold length L min (defined in fig 3 by the slope change of the line). This length corresponds to the length needed to have all the filaments of the yarn in contact with the matrix, considering the twisted shape of the yarn. For embedded length lower than L min , the number of anchored filaments and therefore the pullout strength increases when the embedded length increases. Over L min , the pull-out strength remains constant as a change of the embedded length does not modify the anchoring conditions of the filaments. L min is influenced by the yarn pre-treatment. In particular, PI pre-treatment gives very low L min (under 1 cm). The same analysis can be done with the values of the stiffness k bond . In the following section, we retain the average values of the behaviour parameters obtained for embedded length over L min as characteristic of the pull-out behaviour.

Relationship between physical and mechanical parameters

Pre-peak stage of the pull-out behaviour

The pre-peak stage of the pull-out behaviour is characterized by the maximum pull-out load (P max, lim ) and the first stage stiffness k bond,lim . Index "lim" refers to the average of the values obtained for embedded length higher than L min . As shown in fig 4, the pull-out load is an increasing function of the impregnation index. Differences are observed from one yarn to the other. In particular, OC yarns give slightly lower values of the pull-out load and seem to be less sensitive to the impregnation index. These tendencies are also observed for the relationship between the stiffness and the impregnation index but in this case stiffnesses of OC and SG yarns are very similar. The increase of the impregnation index traduces a better penetration of the matrix in the yarn, which tends to reduce the free length of the filaments. As a consequence, filaments work more simultaneously, leading to enhanced pull-out load and stiffness. As the penetration of the matrix in the yarn creates obstacles to the flow of water, the correlation between iy and the pre-peak behaviour is also observed with the flow rate (fig 5): a decrease of the flow rate is associated to an increase of pullout load and stiffness. The correlation with the flow rate is particularly good in the case of k bond where it seems to be almost uninfluenced by the type of yarn.

Concerning the relationship to the yarn pore volume, no general correlation are observed (fig 6), neither for the pull-out strength nor for the stiffness.

Post-peak stage of the pull-out behaviour

The post-peak stage of the pull-out behaviour is characterized by the second stage stiffness k debond,lim . Fig 7 gives the values of k debond,lim versus flow rate and impregnation index. As there is no specific correlation, relationship of k debond,lim to the yarn pore volume is not given.

Residual stage of the pull-out behaviour

The residual stiffness and load that characterized this stage of the pull-out behaviour are both increasing when the yarn pore volume increases. As explained in 2.2, this can be linked to the penetration of the matrix in the yarn that induces disorder in the filaments arrangement and therefore enhances the friction between filaments (possibly with cement particles acting as a third body).

Conclusion

The here-presented results appear as complex because the specific structure of impregnated yarns generates multi-influenced behaviour. Despite of this difficulty, the results gives general trend associated to the pull-out behaviour. In particular, it appears that the pre-and post-peak behaviour are linked to the capability of water to flow along the impregnated yarn, when the residual behaviour can be correlated to the specific pore volume of the yarn. These results make possible to connect the micro-structure of the impregnated yarns to its pull-out behaviour.

Fig 1 .

 1 Fig 1. Impregnation index, iy vs flow rate (left) and yarn pore volume (right).

Fig 2 .

 2 Fig 2. Parameters of the pull-out behaviour.

  third stage (St3) of the pull-out behaviour corresponds to the residual friction of the intermixed broken filaments. It is characterized by slowly decreasing level of friction. Fig 2 shows the parameters retained as characteristic for the pull-out behaviour: maximum pull-out strength P max ; stiffness k bond and k debond of the first and second stages of the pull-out behaviour (determined in the range 0.5-0.8 P max ); stiffness k frictional of the third stage (residual load; determined in the δ range 5-8 mm); and second to third stages transition load P residual .

Fig 3 .

 3 Fig 3. Values of Pmax and kbond versus the embedded length (SG1 yarn).

Fig 4 .

 4 Fig 4. Pmax,lim (left) and kbond,lim (right) vs impregnation index iy.

Fig 5 .

 5 Fig 5. Pmax,lim (left) and kbond,lim (right) vs flow rate.

Fig 6 .

 6 Fig 6. Pmax,lim (left) and kbond,lim (right) vs yarn pore volume.

Fig 7 .

 7 Fig 7. kdebond,lim vs impregnation index (left) and flow rate (right).

Fig 8 .

 8 Fig 8. Relationship between kfrictional (left), residual strength (right) and yarn pore volume.

Table 1 .

 1 Physical and mechanical characteristics of the multi-filament yarns.

		SG1	SG2	SG3	OC1	OC2
	Type of glass	AR	AR	AR	E	E
	Type of roving	Assembled Assembled Assembled Assembled	direct
	Filament diameter (µm)	14	14	14	12	17
	Finesses (tex=g/km)	2450	2450	2500	2400	2400
	Glass density (kg/m 3 )	2680	2680	2680	2530	2530
	Max.strength (N)	714.4	856,6	830.4	1116,3	900.5
	Yarn stiffness (kN/mm/mm)	56.5	44.9	45.5	54.8	55.9


Olivier Guyon

A MODELING APPROACH FOR LOCATING LOGISTICS PLATFORMS FOR FAST PARCEL DELIVERY IN URBAN AREAS

This study aims at defining a framework for optimizing, in a sustainable way (i.e. economical, eco-friendly and societal), the location of logistics platforms in urban areas. A first case study for our work is the city of Marseilles (France) which already has a logistics platform right in its centre (ARENC: 41362 m 2 of warehouses and offices).

In this abstract, we first provide a precise description of the problem we intend to solve. We then propose a mathematical model for representing it. Preliminary experimentations, based on the city of Marseilles, are then described; figures and preliminary results which are proposed for this first case study are obtained thanks to a decision-making software we have implemented. Conclusions and future works are finally drawn.

INTRODUCTION

City logistics has raised the interest of many researchers from different communities and countries in the last decade (Taniguchi and Thompson, 2002;[START_REF] Boudouin | Guide méthodologique: les Espaces Logistiques Urbains[END_REF][START_REF] Crainic | City Logistics, CIRRELT[END_REF][START_REF] Guyon | Planification stratégique pour la logistique urbaine verte[END_REF]. The subject of this paper is the location of logistics platforms in the context of fast parcel delivery in urban areas.

Regarding the last miles, fast parcel deliveries is generally managed as follows by carriers. Parcels are supplied to platforms early in the morning (late in the night) and sorted according to their final destination. Trucks are then loaded and drivers start deliveries. Once finished, collection of parcels are started and distributed to platforms in the mid afternoon, so that parcels can be sorted and dispatched in the evening. An important matter is that a single route is scheduled for delivery, followed by a single route dedicated to collection.

A strong tendency that could be observed in most urban areas during last decades was to limit the presence of the logistics platforms in urban areas. Several simple reasons can explain this phenomenon. Inhabitants do not appreciate living around these platforms that might cause increases of traffic (and specially traffic of large vehicles), generate noise and pollution, or have some unpleasant visual impact. Also, available surfaces in cities are rare and expensive. From a pure economical point of view, carriers used to prefer less expensive locations, at some distance of the city, though the inconveniences of being distant from final customers. Also, local authorities gave priority to more noble activities for these available surfaces: commercial centers, apartments, public services as libraries or concert halls... Due to many recent factors, the benefits of this policy, both for local authorities and carriers (and eventually inhabitants), can be questioned. Environmental issues become more and more important. New purchase channels as e-business modify profiles of carrier customers and imply different organizations and services. Disposing of urban platforms can then offer several possibilities as using electric vehicles (whose limited autonomy prevents from travelling long distances) or scheduling several successive deliveries or collection routes (which is not tractable with distant platforms).

Though some urban platforms exist and their performance on different criteria can be analyzed, no model seems to allow quantifying a priori the effect of locating a platform at a given position. In this study, we propose an original model that aims at answering to the following problems:

• given a set of available surfaces in and outside of the city,

• given an average distribution activity of the city, o how many logistics platforms have to be built ? where should they be located ? and how should they be sized ? o how should be the vehicle fleet of each logistics platform composed of ? o what should be the (approximate) daily route of each vehicle ?

• so that the distribution is performed at optimal performance regarding a set of criteria including economic, environmental and social impacts. given a set of available surfaces in and outside of the city, Operations research literature is rich of works devoted to location of logistics platforms or design of distribution networks. Some important references are [START_REF] Crainic | Service network design in freight transportation[END_REF][START_REF] Daskin | Network and Discrete Location: Models, Algorithms, and Applications[END_REF][START_REF] Klose | Facility location models for distribution system design[END_REF][START_REF] Melo | Facility location and supply chain management -a review[END_REF][START_REF] Revelle | A bibliography for some fundamental problem categories in discrete location science[END_REF]. While some of them concern city logistics [START_REF] Crainic | City Logistics, CIRRELT[END_REF][START_REF] Taniguchi | Optimal size and location planning of public logistics platforms[END_REF], none of these works address the issues investigated here.

PROBLEM DESCRIPTION AND MODELING APPROACH Problem description

The model we propose involves a set ܦ of spatially distributed zones of demand, a set ܮ of available surfaces for logistics platforms and a set ܸ of vehicles to transport goods (i) from the logistics platforms to the zones of demand, (ii) within the zones of demand through routes.

Each zone ݀ א ܦ has a demand of ߛ ௗ positions (a position being defined as a stop of a vehicle for serving a customer). All ߛ ௗ positions are distributed within ݀ through a single route of ߜ ௗ kilometres. A set Δ ௗ ك ܦ of compatible zones is assigned to ݀ ; the compatibility of zones is used to define routes of vehicles. Indeed, routes of different zones can be merged if and only if the concerned zones are compatible. A congestion cost ܿ ௗ (taking values in {A, B, C, D, E}) is assigned to ݀ in order to represent the difficulty of driving within ݀; ܿ ௗ can depend on the population density of ݀, its topology, the width of its streets...

Each available surface ݈ א ܮ for logistics platforms has a size defined as a maximal number ݍ of doors which can be built on ݈. Each door of ݈ can ensure the distribution of ߠ positions. The distance between an available surface ݈ א ܮ and a zone of demand ݀ א ܦ is denoted ܯ ௗ . The total cost of selecting ݈ is divided into four costs: (i) an economic fixed cost ܿ ௦ for the construction or the maintenance of ݈ (euro), (ii) an economic cost ܿ ௧ for building a door on ݈ (euro), (iii) a cost ܿ of the inhabitants acceptability ({A, B, C, D, E}) and (iv) a cost ܿ for the pollution created by a door built on ݈ ({A, B, C, D, E}).

Each vehicle ݒ א ܸ has a capacity ߚ ௩ (number of positions) and a distance-autonomy ߙ ௩ ௗ௦௧ (Kms). The driving time per day of ݒ is limited by two parameters: (i) ߙ ௩ ௧ (minutes) which depends on the specific technical characteristics of ݒ , and (ii) ܶ ௫ (minutes) which is a workload limit. ݒ is furthermore limited to travel on a subset J ௩ ك ܦ of zones of demand (because of the legislation, the width of the streets...). Travel times in our model depend on the type of vehicles. We thus use, for each vehicle ,ݒ the notations ܵ ௩ௗ and ܶ ௩ௗ that respectively define the travel time for serving the zone of demand ݀ א ,ܦ and the travel time between ݀ and an available surface for logistics platforms ݈ א .ܮ The total cost of using ݒ is divided into five costs: (i) an economic fixed cost ܿ ௩ ௨ for the purchase of ݒ (euros), (ii) a driving cost ܿ ௩

ௗ௩

(euros/Km), (iii) a cost ܿ ௩ for gas emissions of ݒ (euros/Km), (iv) a cost ܿ ௩ of the inhabitants acceptability ({A, B, C, D, E}) and (v) a congestion cost ܿ ௩

({A, B, C, D, E}).

Hypotheses of our model and justifications

One carrier. This paper addresses solutions for locating public logistics platforms where goods are consolidated in order to be delivered in the cities by one single carrier (public or private).

One route per vehicle. To cope with the current organization of the carriers (because of constraints on drivers, on incompressible processing times for sorting and consolidating goods in distribution centres), we assume that each vehicle cannot be assigned to more than one route per day.

One vehicle per zone of demand. To cope also with the current organization of carriers, we assume that each zone of demand is served by a single vehicle. It implies that, as in practice, the size of each zone of demand fits in at least one vehicle.

Transportation costs are estimated. Exact transportation costs are complicated to handle. Two main approaches to estimate them can be found in the literature. Either transportation costs are roughly approximated as being simply dependent on the distance between the platform and the zone of delivery; such approach does not make sense in an urban context, with a heterogeneous fleet of vehicles. Or vehicle routes are explicitly constructed (in so-called Location-Routing Problems); we do not believe that going into such deep details is necessary here, as decisions are very strategic, concern a very dynamic context (urban areas, fast delivery) and are based on very approximated/aggregated data (demand, costs...). We rather evaluate transportation costs as follows: the transportation cost of a route depends on the first zone served (indicating the cost of entering the city from a distant platform) and the set of zones of delivery (indicating the distances traveled during the deliveries). Constraints are introduced, through the use of the compatibility between zones, to avoid including distant zones in a same delivery route.

A logistic platform has a 10-year life cycle and works 300 days per year.

MIP model

In this section, we propose an Integer Linear Programming model associated with the problem at hand. For the sake of clarity, the presentation of this mathematical formulation is split into three parts: the decision variables, the constraints and the different optimization criteria of the model.

Beforehand, we define two additional sets ܦ ௩ and ܸ ௗ we use in our model:

ܦ ௩ ൌ ሼ݀ א ܦ | ሺ݀ א ܬ ௩ ሻ ר ሺߚ ௩ א ߛ ௗ ሻሽ ܸ ௗ ൌ ሼݒ א ܸ | ሺ݀ א ܬ ௩ ሻ ר ሺߚ ௩ א ߛ ௗ ሻሽ
ܦ ௩ stands for the set of zones of demand the vehicle ݒ א ܸ can serve (it is allowed to serve the zones and its size fits their demand), and ܸ ௗ defines the set of vehicles which can be used to serve the zone of demand.

Decision variables. The decision variables of our mathematical model are:

• ݑ ൌ 1 if a logistics platform is built on the available surface ݈, 0 otherwise ; ݈ א ܮ • ݓ is the number of doors to be built on the logistics platform located on ݈ ; ݈ א ܮ • ݔ ௩ௗ ൌ 1 if the vehicle ݒ is assigned to the logistics platform located on ݈ and serves the zone of demand ݀, 0 otherwise ; ݈ א ,ܮ ݒ א ܸ, ݀ א ܦ ௩ • ݖ ௩ௗ ൌ 1 if the vehicle ݒ is based in the logistic platform located on ݈ and begins its daily route by serving the zone of demand ݀, 0 otherwise ; ݈ א ,ܮ ݒ א ܸ, ݀ א ܦ ௩

Constraints.

Doors can only be built, up to the size of the site, on selected available surfaces for logistics platforms (1). The demand of each zone has to be fully fulfilled (2), i.e. a vehicle has to be assigned to each zone of demand. Constraints (3) and ( 4) are capacity constraints for, respectively, platforms and vehicles: we cannot assign too many positions (through the assignment of vehicles) to each platform (3) and the number of positions served by a vehicle is limited by its size (4). The daily use of each vehicle is limited by its distance autonomy (5) and its travel autonomy (6). Constraints ( 7) formalize constraints of compatibility between zones of demand: incompatible zones (typically zones that are distant one from each other) cannot be served in a single route. Constraints (8), ( 9) and ( 10) define the assignment of variables ݖ ௩ௗ ; each first zone of a route has to be a served zone (8), each route cannot have more than one zone (9) and each route has to have a first zone (10). Constraints ( 11), ( 12), ( 13) and ( 14) define the variable domains.

Optimization criteria.

As mentioned before, this paper addresses investigations about sustainable solutions for the location of logistics platforms in urban areas. The global objective function of our model is thus composed of different criteria around the three aspects of sustainability: economy (15), ( 16), (17), environment ( 18), ( 19), (20) and society (20), ( 21). Some of these objective functions manage qualitative costs ({A, B, C, D, E}). In our experiments, all these costs are converted into numerical values according to their category.

For the economic purpose, our model addresses the fixed cost of building or maintaining logistics platforms (15), the fixed cost of purchasing vehicles ( 16) and the variable cost of using vehicles (17).

The environmental cost function of our model is split into three parts: a variable pollution cost caused by travels of vehicles (18), a variable pollution cost caused by logistics platforms (19) and a variable congestion cost due to both vehicles and platforms.

Our model also addresses fixed acceptability costs through two criteria: the acceptability by inhabitants near logistics platforms (21) and the acceptability by inhabitants impacted by vehicles movements (22).

In a first approach, we define the global objective function of our model as the sum of these 8 optimization criteria. Future works will investigate multi-objectives methods to deal with the diversity of these criteria.

GENERIC OPTIMIZATION SOFTWARE

To experiment our model, we have developed a generic optimization tool able to create, compute and evaluate different scenarios in any urban area.

In this software, users can split a geographical urban area into different zones of demand and describe for each zone: the demand, specific vehicle traffic rules, and other properties such as size and travel time... Different types of vehicle can also be created according to their own list of attributes (which corresponds to the elements of our mathematical model). Available surfaces for logistics platforms, and their properties, can also be created and edited in our tool. Figure 1 is a screenshot of the software used on a map of Marseilles (a French city), with the editing of three data tables: available surfaces for logistics platforms, zones of demand and vehicles on Figures 2, 3 and4, respectively.

A FIRST CASE STUDY BASED ON MARSEILLES (FRANCE)

The study proposed in this paper is done in partnership with a French consultancy service specialized in transports economics (JONCTION) which has collected aggregate data about actual distribution systems in the second largest city of France: Marseilles (852,395 inhabitants in 2007). JONCTION indeed met thirteen companies that already operate in Marseilles and its surroundings. They thus have collected both figures and actual ways of working of these thirteen companies. The model presented above is based on the conclusions and exploits the data of this study for Marseilles.

To experiment our model and the software we have developed, we created an instance based on real data for Marseilles. In this instance, Marseilles' urban area is split into 94 sectors requiring 2957 deliveries per day. Five categories of vehicles are considered: two electric and three gasoline ones. Their maximum carrying capacities vary from 3.5 to 15 tons. The set of available surfaces for logistics platforms is composed of 5 localizations; three inside the urban area, and two in its surroundings.

Preliminary results for our case study consists in selecting three of the four platforms (the two ones that are inside the urban area, and one on its periphery), and using 94 vehicles. About 300 vehicles run currently each day in Marseilles for this service. Therefore, we can expect to divide by three the size of the fleet delivering Marseilles, by merging the activities of the thirteen companies.

CONCLUSION

We have proposed a new mathematical model for a strategic problem of City Logistics: the location and sizing of logistics platforms. For a concrete use of this model by local authorities of large cities, we have implemented an optimization tool for both editing data, finding a feasible solution and visualizing it. Such a tool can thus be used in order to compare different scenarios (location of candidate logistics platforms, policy rules on eligible fleet of vehicles inside the city...) and then take a strategic decision on the location of logistics platforms. Future works will address the creation of an instance, still dedicated to Marseille, which will be based on exact data. Ad hoc solution methods will also be developed in order to find good feasible solutions in a reduced CPU time. For the moment, we use a commercial optimization software that meets difficulties for solving very large instances.

In our presentation for the 7 th International Conference on City Logistics, we will present our model and precisely describe the data we use for our case study (Marseille). We will also present an ad hoc solution method and its associated concrete results. An application of the optimization software we have implemented will also be demonstrated.

Figure 1

 1 Figure 1 Optimization tool -map

Figure 5

 5 Figure 5 Optimization tool -solver

ACKNOWLEDGEMENTS

This work was carried out in partnership with JONCTION (consultancy service specialized in transports economics), SOGARIS (specialist in logistics property for urban and inter modal purposes) and the CLUSTER PACA LOGISTIQUE (association which federates logistics activities in the french region Provence-Alpes-Côte d'Azur). It is funded by the French Minister of Ecology, Sustainable Development, Transport and Housing, subsidy 09 MT CV 39.