Carlos Herrera
email: carlos.herrera@cran.uhp-nancy.fr

Sana Belmokhtar
email: sana.belmokhtar@cran.uhp-nancy.fr

André Thomas
email: andre.thomas@cran.uhp-nancy.fr

Sana Belmokhtar Berraf

Viable System Model

Keywords: Product-driven systems, intelligent manufacturing systems, viable system model, manufacturing planning and control

HAL is

Introduction

The economic context including globalization and free competition triggers quick evolutions of several technologies available for the industry and users. That pushes firms to be more reactive, more innovative, more agile.

In this context, Intelligent Manufacturing Systems (IMS) (arisen in the earlies 90's), aim to improve the conventional Manufacturing Planning and Control Systems (MPCS) in terms of flexibility, reconfiguration and scalability, among others. In this class of systems, Product-Driven Control Systems (PDCS) [START_REF] Mcfarlane | Product identity and its impact on discrete event observability[END_REF], based on intelligent products [START_REF] Mcfarlane | The intelligent product in manufacturing control[END_REF], change the vision of products from a passive state into active actors in the decision process concerning itself [START_REF] Morel | Manufacturing plant control challenges and issues[END_REF]. Nevertheless, one of the major limitation of these kind of systems is the absence of specific frameworks to guide the process of analysis, design and implementation.

For that purpose, in this paper, we propose a general framework to model product-driven control systems applied to MPCS. The proposed framework is designed to be used in a wide range of production or services product-driven systems. This leads us to a generic concept which provide sufficient theoretical concepts and implementation guidelines to manage the inherent complexity of this kind of systems.

Our work has been motivated by the design of intelligent products as living beings, focusing our research in theories and models concerning the structure and organization of these living machines [START_REF] Maturana | Autopoiesis and cognition: The realization of the living[END_REF]. The objective is to use such models to design manufacturing systems that can show properties like autonomy, selforganization and adaptability. These properties can be summarized as viability commonly present in living beings. The presence of such properties has lead to the conceptual framework present in the Viable System Model [START_REF] Beer | Brain of the firm: the Managerial cybernetics of organization[END_REF][START_REF] Beer | The viable system model: Its provenance, development, methodology and pathology[END_REF]. The choice of VSM has been made since this framework is suitable to model these properties.

Main property in VSM is recursion, that allows to manage complexity and find a compromise between control and autonomy to implement principles as heterarchy and cooperation [START_REF] Herrera | A viable system model for product-driven systems[END_REF]. These are central elements of product-driven control systems and in a more general way a key objective of IMS. Manage complexity allows to consider each system as a whole preserving the emergent properties which can only be understood using a holistic vision, in contrast to reductionist ones.

VSM since its origin in the earlies 70's as result of the research of Stafford Beer, has been object of a constant validation with several applications until nowadays. The pertinence of this model can be justified regarding to the recent applications concerning domains like material management [START_REF] Herrmann | Lean production system design from the perspective of the viable system model[END_REF][START_REF] Rosenkranz | Designing ic structures by variety engineering[END_REF], autonomous distributed systems [START_REF] Ribeiro-Justo | Intelligent reconfiguration of dynamic distributed components[END_REF], autonomous software [START_REF] Herring | Viable Systems: The Control Paradigm for Software Architecture Revisited[END_REF][START_REF] Laws | Genetically modified software: Realizing viable autonomic agency[END_REF] or autonomous communities of agents [START_REF] Truszkowski | A cybernetic approach to the modeling of agent communities[END_REF].

Our contribution deals with the use of VSM applied to PDCS as an integrated modeling framework. The most important paradigms arisen from IMS are biological [START_REF] Ueda | Modelling of biological manufacturing systems for dynamic reconfiguration[END_REF], fractal [START_REF] Warnecke | The Fractal Company[END_REF] and holonic manufacturing systems [START_REF] Valckenaers | Holonic manufacturing execution systems[END_REF]. The biological paradigm and properties like synthesis has been essential parts of biological systems, recursion is the basis property of fractal system and the difficulty to separate parts from the whole is a main concept in holonic systems. Our intention is to show that VSM can be used like a consensual framework for all these research threads.

This paper is organized as follows: section 2 presents a general description of the main concepts involved in VSM, and presents the approach focusing on the elementary object of the proposed structure, that is the intelligent product. Section 3 describes an application of the proposed approach for a Manufacturing Planning and Control System. In section 4 a discussion of the main findings is presented. Finally, section 5 presents the conclusion.

VSM for holonic product-driven manufacturing systems

The origins of VSM arise from the work of Beer applied to the steel industry in the fifties. This research can be placed in the line of works of Norbert Wiener, Warren McCulloch and Ross Ashby [START_REF] Espejo | The viable system model a briefing about organisational structure[END_REF]. The main objective of the model was to identify and to explain how systems are viable, in other words, how it is possible that some systems can maintain an independent existence.

Although VSM is a general model for the study of any viable system, the most concerned application area has been human activity organizations, i.e., corporations, firms or governments [START_REF] Beer | The liberty machine[END_REF]. In this domain, VSM changes the view of the traditional management model based on command and control, in which a control system is designed as a pyramid and such decisions are disaggregated in a top-down manner at different structural levels. The main difference, inspired by the biological organization, consists in mapping this hierarchy into a structural recursion.

The premise of this change of perspective was inspired from the living beings composition (cells, organs, systems, etc.). Indeed, they have properties of autonomy, self-organization and self-regulation, allowing them to have an independent existence. The differentiation of their functions and the relationships between these elementary components produce more complex systems, without that subsystems essential properties would be lost. However, one of the most important properties of a viable system is their intrinsic recursion. In fact, any viable system contains and is contained by another viable system. Every subsystem maintains its autonomy towards its environment, but it also contributes to generate the viable system in which it is included. In that way, a viable system and its different subsystems have the same structural requirements. A viable system supports its objectives thanks to an overall cohesion and adapts itself by the autonomy of its subsystems.

VSM was developed looking for invariances in organic systems. These invariances allow to define a homomorphism of their functions, organization and structure. Beer defines five elementary functions that any viable system must have: implementation, coordination, control, intelligence and policy. In the following are defined more in details each one of these functions:

Implementation : this function refers to primary activities that materialize the identity of the system. These activities are identified after an analysis of what the system does, then directly related to the system transformation and environment interaction.

Coordination : this function corresponds to the coordination among primary activities. In a viable system, this coordination is not necessarily accomplished in a top-down manner like in a hierarchical management system. Primary activities can be coordinated in a centralized or distributed way thanks to cooperation and information exchanges.

Control : control refers to the function which regulates and ensures the selforganization of the system. This is due to coordination and monitoring functions. Monitoring function (or sporadic audit function) allows at the same time to evaluate the actions of primary activities and to hold the coherence of the global activity (all primary activities). Control function is the function that defines the control/autonomy degree of primary activities.

Intelligence : the intelligence function is responsible for system adaptability. To achieve this adaptation, the intelligence function must be capable of treating the information which comes from the environment, with the objective to anticipate perturbations.

Policy : the policy function keeps the system objectives at its level. As it was expressed by Ashby [START_REF] Ashby | An introduction to cybernetics[END_REF] in the law of requisite variety a controller will be effective only if it is capable of attaining at least the same number of states as those which it wants to control. The variety of a system is defined as all possible states of a system and it can be used as a complexity measure.

"A controller has requisite variety -that is, has the capacity to maintain the outcomes of a situation within a target set of desirable states -if and only if it has the capacity to produce responses to all those disturbances that are likely to take the outcomes out of the target set".

To achieve that, the viable system tries to reduce the variety coming from the environment and to amplify the variety of its control function to reach a balance (homeostasis). Figure 1 shows an example of a viable system which is decomposed into three subsystems. The recursion property of VSM allows continuing this process until the required level of detail. In the example presented in figure 1, it is possible to break down each of the three viable systems in new viable sub-systems. Also, the whole system can be considered as a subsystem of another viable system at an upper recursive level. Notice that all systems have the same structure.

Fig. 1. A Viable System Model

A conventional recursive decomposition of a production system, will decompose the system, for example, on the shop-floor, production cells, production lines, production modules and machines. In such case, machines would be the elementary (atomic) entities of the system at the lowest recursion level.

In contrast with this conventional interpretation, we consider the product to be the elementary decision-making entity responsible for driving work tasks. Therefore, it is considered as the basic element of the production process and it is designed as a viable system. Others system entities such as machines, conveyors, automated guided vehicles, team workers, etc., are then considered in the environment. These entities interact with the product only in terms of events leading to lack of availability, disruptions, constraints, etc. Figure 2 shows the intelligent product structure which is proposed. As it has been said in the introduction, the intelligent product is defined as an entity able of interacting and communicating with its environment. When this physical entity transits on the shop-floor, it will be able to recover information concerning both its own state and the system state. Then, focusing on the product, all the production planning system can be structured from the information recovered by this intelligent product. Also, decision-making problems are addressed to their corresponding recursion level.

The primary activities of the intelligent product are data collection and interaction functions. The data collection activity is designed as the action which allows the product to get information from other products and to give information to them. On the other hand, interaction functions allow products to interact with their environment.

Application to MPC systems

Manufacturing Planning and Control Systems contain five main functions which can be described as : Strategic Planning, Sales and Operations Planning (S& OP), Master Production Planning (MPS), scheduling and execution. Each of these functions corresponds to a level in the decision making process regarding to different horizons going from a longer to shorter one. In practice, these decisions are taken using a rolling horizon to take into account the frequent changes that occur in the data (demand, capacity, etc.). Thus, the strategic planning is revised once a year, the S&OP is computed monthly, the MPS is get per week, and the schedules are performed daily or more frequently depending on disturbances. Each function deals with a corresponding aggregation level of products respectively families, finished products and items (components). In this context, one of the major issue is to adapt decisions at each level when disturbances (internal or external) happen. The frequent resulting modifications in the decision making process lead to the so-called nervousness system which deteriorates the system performance (productivity and efficiency). One should notice, that the shorter is the horizon the more frequent are the changes. Thus, the performance are more deteriorated at the lower level (scheduling level).

More precisely, our proposition is to provide a generic model based on VSM dealing with production planning considering both MPS level and scheduling (lot-streaming). The MPS allows to define quantities for finished products per periods on a specific horizon. This is usually performed with a capacitated lotsizing problem which is classically formulated with a mixed integer program. This model is implemented at the higher level in the figure 3. Generally, once lot sizes are determined, sub-lots have to be sequenced and dimensioned to be launched on the shop-floor (lot-streaming problem) [START_REF] Sarin | Flow Shop Lot Streaming[END_REF]. This model is implemented at the level two from the bottom in the figure 3. Thus, different objectives could be reached corresponding to each decision level (minimizing stocks and set up costs at the MPS and minimizing makespan at lot-streaming level). However, disturbances are frequent in this context, such an example could be found in the demand changes or the capacity reduction (machine failure). As a consequence of these disturbances, the computed predictive planning would be inadequate and should be adjusted regarding to the new conditions (data). Nevertheless, the combinatorial nature and the variability of the different parameters of the considered problems do not allow an on-line computation. The characteristic of self-adaptation is then present with an adjustment of machine capacity when a failure happen in a certain limit. Obviously, when the capacity comes down a certain threshold then it becomes impossible to find a solution, in this case the problem is forwarded to the upper level (a bottom-up process).

For external disturbances, the centralized system modify the threshold and the global objectives to adapt itself in a top-down manner by defining new targets for the bottom level. At the opposite to the bottom-up decision making process which has a cooperative characteristic, the adjustment process (top-down) has a coercive characteristic.

The figure 3 shows an example of four recursion levels. This system has been proposed with the hypothesis of using intelligent products mainly concerned with RFID technology to embed and communicate information.

The proposed model aim to face external and internal disturbances which could occur. This system is based on a holarchy of products regarding to VSM modeling. Each decision level corresponds to a certain recursion level. The dif-ferent levels of recursion are defined as agents communities which should adapt themselves to the decision making conditions. Moreover, they have the objective to collaborate to find a suitable solution. Figure 3 is subdivided into 4 parts (I,II,III et IV) in order to simplify the explanations. The two axes allow to represent different points of view where the horizontal axis distinguish the physical world from the virtual one. Whereas the vertical axis shows at the left side the design which is a representation of the system. At the right side, the implementation deals with both the knowledge managements and decision making systems. This part is relative to the centralized or cooperative system representation. The representation is decomposed into four recursive levels of product entities. At each level, the concerned entities (weekly production, manufacturing orders, lots and products) are modeled thanks to the basic object proposed in the figure 2. To take decision, a product or a group of products will have policies, intelligence and control functions, coordination and communication mechanisms.

The products being defined as agents with a specific control/autonomy level, three alternatives are possible. First, if the system is strictly distributed or heterarchic, agents communicate only in a cooperative way for decision-making process. Second, if the system is strictly centralized, decision are taken with methods (models) that collect information thanks to agents and aggregate it to propose centralized planning orders. Third, between these two opposite solutions, many combinations are able to be implemented adapting different degree of control/autonomy.

Part II : Design/Physical

This part of the figure is relative to the product instantiation at the physical level. Each of the four decision-making levels of the previous part could generate plans for the corresponding level. According to the physical/virtual nature of the entities, products will be built as holons in this part. They will have specific functions to be able to interact with their environment. Each of the four recursive levels would be designed like holons in the same way. For example, the physical part of a manufacturing order holon would be the manufacturing order paper form or a kanban card would be the physical part corresponding to a lot.

Part III : Implementation/Physical

In this part product holons are able to make decisions according to events concerning their own evolution. Specific functions are embedded in these intelligent products leading them to react to events in an individual or collective way.

Part IV : Implementation/Virtual

This last part is relative to the treatment of information coming from the shopfloor and concerning disruptions and product actions, on one hand. On the other hand, decision making process is also handled in this part. In the same way, each recursive level corresponds to a decision making one which interacts with the corresponding knowledge level. This treatment could be defined as a information and knowledge model [START_REF] Zins | Conceptual approaches for defining data, information, and knowledge: Research articles[END_REF].

Discussion

An important concern of VSM is adaptability as it was described in the previous section, VSM was developed with the objective to understand the mechanisms which allow biological organisms to survive to changes in the environment. A viable system is designed to self-adaptation in a changing environment, by the implementation of the necessary mechanisms to support its viability. Indeed, it is not possible to identify a specific function which ensures adaptability, since the whole system is defined to fulfill this objective, thanks to its different elementary functions. This characteristic of adaptability is also one of the main objectives of the paradigms arising from IMS initiative.

One of the basic properties of the viable systems is scalability because these systems are structurally recursive. This notion of recursion has been mainly exploited by biological manufacturing systems, which make an analogy from biological organisms. Recursion has been also exploited by fractal manufacturing systems which show clear properties of modularity and auto-similarity. Autosimilarity in fractal systems is also included in the viable systems through its property of structural recursion. In that way, a viable system will keep the same structural requirements at any complexity level. These concepts have a direct relationship with re-usability, which is another objective of IMS systems. These concerns of autonomy, adaptability and scalability highlight the strong relationship between VSM and IMS objectives.

Considering the context of our study dealing with the Product Driven Control Systems which consider the product as an intelligent entity, the idea of the proposed VSM model takes the product as the elementary (primary) recursive component. The others recursive levels of our model are established according to the classical decomposition resulting from MPCS management which provides : products, lots, manufacturing orders and MPS weekly quantities. Note that the product is a generic term and could be extended to component or raw material. In such case, corresponding lower levels should be added.

Conclusion

In this paper, we have presented the main concepts involved in the VSM and how those can be applied to model product-driven control systems. It has been highlighted that VSM has nice properties to model intelligent manufacturing systems. We have presented an application of the proposed modeling framework to model a MPCS product-driven system. The main advantage of this application is to reach a coherence among the different decision levels giving a high degree of flexibility to the system. The proposed modeling approach applied to productdriven systems could be implemented in different industrial context.

Fig. 2 .

 2 Fig. 2. An intelligent product modeled using VSM

Fig. 3 .

 3 Fig. 3. VSM based product-driven control system applied to MPCS

Acknowledgments. The authors gratefully acknowledge the financial support of the CPER 2007-2013 Competitiveness Fibre Cluster (Structuration du Pôle Compétitivité Fibres Grand'Est), local (Conseil Général des Vosges), regional (Région Lorraine), national (DRRT and FNADT) and European (FEDER) funds.


Richard Moot
email: moot@labri.fr

Laurent Prévot
email: laurent.prevot@lpl-aix.fr

Christian Retoré
email: retore@labri.fr

Discursive analysis of itineraries in a historical regional corpus of travels: syntax, semantics, and pragmatics in a unified type theoretical framework

Introduction

In this paper we will discuss the application of (Segmented) Discourse Representation Theory and the Generative Lexicon to the analysis of a historical French corpus of itineraries in the Pyrénées. Our research will focus in particular on how type coercion [START_REF] Pustejovsky | The generative lexicon[END_REF] can help us give a correct analysis of cases of so-called "fictive motion" [START_REF] Talmy | Fictive motion in language and "ception[END_REF], which is evident is phrases like.

(1) The road runs along the coast for two hours.

(2) The path descended abruptly. This case is particular in that an entity (which is considered immobile and which, in the context, defines a path) is the subject of a movement verb and that the combination is interpreted as a generic statement about the nature of this path, without any movement necessarily taking place.

Context

The context of the current research project is to provide a semantic representation the paths traversed or described by the authors of the different books in a corpus of itineraries in the Pyrénées mountains. It is a 19th century corpus consisting of 576.334 words, containing (among many other details and descriptions) narratives of the routes followed and the places visited by the authors. Other information about the corpus and its spatiotemporal analysis can be found in [START_REF] Loustau | Interprétation automatique d'itinéraires dans des récits de voyages D'une information géographique du syntagme à une information géographique du discours[END_REF][START_REF] Asher | Spatial entities are temporal entities too: The case of motion verbs[END_REF].

The problem on which we will focus here is that in many cases, non-agentive movement verbs, such as "descendre" (corresponding to go/come * Richard Moot and Christian Retoré have benefited from a grant from the Conseil Régional d'Aquitaine, in the context of the Itipy projet and like to thank the other participants of the Itipy project for their discussion on many of the themes of this paper down in English) can take as its subject not only a person (sentence (3) below), but also an immobile subject, provided it can be associated (or coerced) to a path, such as a fence or a road (sentence (4)).

(3) Jean descend.

(4) Le chemin descend.

The phenomenon evident in Examples (1), ( 2) and ( 4) has been called "fictive motion", [START_REF] Talmy | Fictive motion in language and "ception[END_REF]: our mind's eye or an imaginary traveler moves along a stationary object such as a road, a fence or a table. It is our goal to give an account of this phenomenon in a type-theoretic framework.

The examples below, which are taken from our corpus, show some further particularities of fictive motion.

(5) Nous coupons ici un sentier qui vient du port de Barroude (...) Here, we cross a path which comes from the pass of Barroude (6) Plus loin, de nobles hêtres montent sur le versant (...) Further away, noble beeches climb the slope (7) (...) cette route qui monte sans cesse pendant deux lieues this road which climbs incessantly for two miles

In example (5), it is clear -by the meaning of "couper" (cross) -that the authors do not take the path described. In example (6), there is no real path specified and we intepret the sentence as the author's gaze following a path along the beeches up the slope, whereas in example (7) there is adverbial modification: "incessantly" and "for two miles". Though the class of permitted adverbs is semantically restricted 1 , it is possible to have temporal adverbs such as "the road went along the coast for two hours" and some manner adverbs such as "the path descended abruptly/slowly" which do not commit us to inferring that the author actually took the road. All of this suggests that we can interpret a static object as the (abstract) process of traveling along it.

Syntax and Semantics

Our semantic framework is integrated in a widecoverage categorial grammar for French (Moot, 2010a), which has been semi-automatically extracted from the French Treebank [START_REF] Abeillé | Building a treebank for French[END_REF]. The wide-coverage grammar and the Grail parser (Moot, 2010b) combine to parse unseen sentences with a precision comparable to the bestknown categorial parsers for English. Categorial grammars are an especially appropriate choice in the current context because of their tight integration of syntax and semantics: each derivation in a categorial grammar corresponds to a typed-lambda term and this makes writing Montague-style semantics for categorial grammars particularly simple.

As is well-know, however, the possibilities of lambda-calculus semantics permit an integration with more modern theories of semantics, such as discourse representation theory [START_REF] Kamp | From Discourse to Logic[END_REF] and the Generative Lexicon [START_REF] Pustejovsky | The generative lexicon[END_REF] ( [START_REF] Bos | Widecoverage semantic representation from a CCG parser[END_REF] and (Moot, 2010b) show that wide-coverage compositional semantics using DRT is possible (for English and for French respectively). In addition [START_REF] Bassac | Towards a type-theoretical account of lexical semantics[END_REF] show that ideas from the Generative Lexicon can be implemented using polymorphic lambda term assignments to lexical entries.

The current paper proposes an extension to the work of (Moot, 2010b) which permits the system to handle cases of fictive movement.

Lexical Semantics

Our semantic approach is generated in the tradition of lexical semantics called the Generative Lexicon [START_REF] Pustejovsky | The generative lexicon[END_REF], especially in its type-logical interpretation of [START_REF] Bassac | Towards a type-theoretical account of lexical semantics[END_REF] In our type hierarchy, have two specific types of spatial arguments regions and paths. Two functions source and destination convert a path p to its source region and its destination region 2 . We 2 We are aware that there are many ways to refer to places also assume a spatial variable here which denotes the position and orientation of the spatial reference point (which does not necessarily correspond to the position of the narrator; in this sense it is closer to a spatial equivalent of the Reichenbachian "reference time" than it is to the constant "now": in a DRS it is most naturally implemented as a succession of values as is the reference time t). Both the position and orientation are necessary to understand a discourse like the following.

(8) a. My new apartment is awesome.

b. The entrance hall is spacious. c. To the left, there is the living room.

In this discourse, we can make sense of the expression "to the left" only because we make a kind of "virtual visit" with up/down, forward/backward and left/right well-defined.

The distinction between regions and paths is rather standard [START_REF] Jackendoff | Semantics and Cognition[END_REF]. It is motivated by selectional restrictions on verbs: some verbs, such as "stay + PP" are only grammatical when the PP is a preposition denoting a region argument, whereas other verbs, such as "pass + PP" can only occur with a number of PPs, all of which denote a path. This distinction is muddled slightly by the possibility to coerce a region r into a path. As is well known, some prepositions, such as "vers" (towards), can -at least in their spatial uses -only denote paths.

For our semantic analysis, we interpret all motion verbs as being relations between one or more entities and a path. This argument can be left implicit (ie. when we say "John ran"). Verbs specify lexically which of their arguments follow this path (subject, object or both).

"Le chemin" with type assignment npιx immobile object .chemin(x) does not combine with "descend" which requires a person as its argument, as indicated by its lexical entry which is of the general form np\s -λy person . . . (to focus the discussion on the coercion mechanism, we give only a schematic entry at this point, the complete entry is shown in Figure 1).

Figure 1 shows the λ-DRTs for both the "le chemin" in its coerced form and "descend". Some comments about the lexical semantics. Motion verbs are analysed by the "neutral" predicate travel (in the style of (Miller and Johnson-in the middle of the paths as well. However, we assume that this is done by relations rather than by functions. le chemin: s/(np\s) λP person→event→t λe event y,p,q,here chemin(y) path of(y, p) subpath(q, p) source(q) = here [START_REF] Miller | Language and Perception[END_REF])) which takes an event e, a moving entity x and a path p as its arguments. It is true if the traveler x follows path p during event e.

The functions source and destination are functions from paths to their source and destination regions, whereas height is a function from regions to their vertical coordinate. Taken together, the semantic entry for "descend" states therefore that given an argument which is a person x and an argument which is an event e, the DRS will verify that there is a path p such that x follows p and that the height at the start of this path p is greater than his height at the end of it.

The coerced entry for "le chemin" states that given a vp semantics P and an event e, it will assert that there is an entity y (which is a path in the sense that is extends over a certain amount of space), the predicate path of will relate y to one or more directed paths p and a sub-path q of p going forward from here is selected. Note that having both y and p as referents in the universe of the DRT is necessary to account for modifiers of both aspects of the path, as in "a brick road to Pau". This analysis, with the variable here having both a place and an orientation, has the pleasant consequence of there being no incoherence between saying "le chemin monte" and "le chemin descend" at exactly the same place but with just the orientation reversed.

In addition, it does not commit us to concluding that anyone actually takes the path. This must be deduced separately.

Computing Discourse Representation Structures

So far, we have only treated simple sentences without much of the surrounding context. The real test for this analysis is how it interacts with the contraints on interpretation posed by its surrounding context.

(9) (...) nous descendons, pendant un quart d'heure, la vallée de l'Esera.

we descend, for a quarter of an hour, the Esera valley.

(10) La lune, qui éclaire notre marche, nous fait découvrir sur la droite un sentier qui serpente.

The moon, which lightens our steps, allows us to discover a winding path on our right.

(11) Il nous conduit sur un petit plateau, au milieu de sapins, au-dessus et à quelque distance du torrent de Ramun.

It leads us to a small plateau, surrounded by firs, at some distance of and above the Ramun torrent.

Here, "Il" (it) in sentence (11) refers to "un sentier qui serpente" (a winding path), so correct analysis require resolution of the anaphor before coercion in order to give a correct analysis.

As is well known, the rhetorical relations as used by SDRT [START_REF] Asher | Logics of Conversation[END_REF], provide a set of important constraints on the possible interpretations on discourse. In the exam-ple above, we have the relations Background(9,10) and Narration (10,11).

A second example illustrates the importance of rhetorical structure on the interpretation (as well as the difficulty of automatically obtaining such a structure). ( 12 (15) (...) Après une longue marche, l'on arrive à Barèges à 6 heures du soir. (...) After a long walk, we arrive in Barèges at 6 in the evening.

Here, sentence (12) introduces the destination and therefore the whole extension route. The following will therefore constitute an Elaboration relation between this sentence and the sequence of ( 13)-(15). It is (at first sight) difficult to decide on the discourse relation of Sentence (14): it would certainly be possible to have a later phrase beginning with "Celle de Cauterets" (the road leading to Cauterets) and a number of the following sentences (omitted here for space reasons) give further background information about the road to Lux. However, at sentence (15), it suddenly becomes evident that the author has been describing the road while following it.

Conclusions and Future Work

We have given a treatment of "virtual movement" in a type-logical grammar. Our account merges two successful extensions of "standard" Montague-style semantics into a single, coherent type-theoretic framework.

Figure 1 :

 1 Figure 1: Coerced lambda term for "le chemin" and lambda term for "descend"

In English we can use manner of motion verbs such as "crawl" and "run" as well


Tai-Yu Ma
email: tai-yu.ma@let.ish-lyon.cnrs.fr

A cross entropy multiagent learning algorithm for solving vehicle routing problems with time windows

Keywords: Vehicle routing problem, heuristic, cross entropy

The vehicle routing problem with time windows (VRPTW) has been the subject of intensive study because of its importance in real applications. In this paper, we propose a cross entropy multiagent learning algorithm, which considers an optimum solution as a rare event to be learned. The routing policy is node-distributed, controlled by a set of parameterized probability distribution functions. Based on the performance of experienced tours of vehicle agents, these parameters are updated iteratively by minimizing Kullback-Leibler cross entropy in order to generate better solutions in next iterations. When applying the proposed algorithm on Solomon's 100-customer problem set, it shows outperforming results in comparison with the classical cross entropy approach. Moreover, this method needs only very small number of parameter settings. Its implementation is also relatively simple and flexible to solve other vehicle routing problems under various dynamic scenarios.

Introduction

The vehicle routing problem with time windows (VRPTW) has been known as one of the NP-hard problems in combinatorial optimization. The problem consists of delivering goods to a set of customers, which must be visited within given time windows, at a minimum cost under available capacitated vehicle constraints. The standard VRPTW has been the subject of intensive study because of its importance in real applications, such as pickup and delivery problems in transportation of goods and fleet operation management. The exact and heuristic algorithms have been proposed and applied to Solomon's test instances and many real-life situations. Recent reviews in these solution techniques for the VRPTW can be found in [START_REF] Cordeau | The VRP with time windows[END_REF][2] [START_REF] Braysy | Vehicle routing problem with time windows. part II: Metaheuristics[END_REF].

The state of the art of exact methods has successfully solved most of Solomon's 100-customer benchmark instances. However, only very limited large instances have been solved to optimality [START_REF]The vehicle routing problem, latest advances and new challenges[END_REF]. Hence, an intensive effort has been engaged in proposing efficient heuristics for solving the VRPTW and related vehicle routing problems. The state of the art of heuristics includes: local search [START_REF] Ibaraki | Effective local search algorithms for routing and scheduling problems with general time window constraints[END_REF] [START_REF] Hashimoto | The vehicle routing problem with exible time windows and traveling times[END_REF], adaptive large neighborhood search [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF] and evolutionary mechanism [START_REF] Braysy | Evolutionary algorithms for the vehicle routing problem with time windows[END_REF] [START_REF] Homberger | A two-phase hybrid metaheuristic for the vehicle routing problem with time windows[END_REF]. Basically, these heuristics apply two main procedures to construct and improve the solutions: the route construction procedure and the route improving procedure. The former consists of generating a set of feasible routes based on deterministic or stochastic route-building heuristics. This procedure provides initial points in order to apply some improving local search algorithms for finding high-quality solutions on the neighborhoods. In general, the neighborhood search space is very large; one needs to develop efficient searching strategies to find local optima. To this end, the local search algorithms are widely used, which consist of replacing a subset of initial solutions such that better solutions can be found. Numerous variants based on the local search framework have been proposed such as iterative local search [START_REF] Martin | Large-step Markov chains for the TSP incorporating local search heuristic[END_REF] [START_REF] Hashimoto | An iterated local search algorithm for the timedependent vehicle routing problem with time windows[END_REF], multistart local search [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] [START_REF] Braysy | A multi-start local search algorithm for the vehicle routing problem with time windows[END_REF] and adaptive multistart local search [START_REF] Ibaraki | Effective local search algorithms for routing and scheduling problems with general time window constraints[END_REF]. Basically, these local search algorithms generate initial solutions by the route construction heuristics or some random mechanisms, and then apply the local search heuristics such as k-opt, i.e. replacing k edges on a route traveled by a vehicle with k edges not on this route, or swap move, exchanging the position of two nodes on the same route, to improve solution quality. To avoid being trapped into local optima, related perturbation or randomization procedures need to be applied. The performance of the local search heuristics depends not only on the interaction between the route construction and the improvement procedures but also on the strength of the perturbation or randomization of the two procedures. To this issue, an adaptive large neighborhood search method has been proposed [START_REF] Pisinger | A general heuristic for vehicle routing problems[END_REF]. The authors proposed a flexible framework aiming to adaptively choose a set of local search techniques. This method provided an auto-adjusted mechanism to intensify or diversify searching neighborhood according to the performance of the set of heuristics. However, it needs to implement a set of heuristics, which is more timeconsuming and complicated than single-heuristic-based algorithm.

Different from the aforementioned heuristics, the agent-based distributed solution techniques have been proposed recently. Vokrinek et al. [START_REF] Vokrinek | Agents Towards Vehicle Routing Problems[END_REF] proposed a vehicle routing problem solver based on multiagent framework. The solver is composed of three types of agents in order to collect demand (task agent), allocate demand (allocation agent) and find routes (vehicle agent). The route construction algorithm is based on greedy search heuristics. The experiments were conducted for capacitated vehicle routing problem. The average solution quality within 91.3% optimality was reported. Barbucha and Jedrzejowicz [START_REF] Barbucha | Multi-agent platform for solving the dynamic vehicle routing problem[END_REF] developed a multiagent platform for simulating dynamic vehicle routing system, i.e. customer requests arrive when the vehicles are running. The system is composed of a set of agents with different functionalities for executing different tasks such as initialization, customer request generation and route assignments for requests. Simple insertion rules are applied for customer request assignment to the vehicles. Other applications based on the multiagent framework in logistics can be found in [START_REF] Davidson | An analysis of agentbased approaches to transport logistics[END_REF]. In summary, these studies have developed simulation tools based on the multiagent approach to static or dynamic vehicle routing problems. However, the solutions found by these multiagent approaches are still far from the optima.

In this work, a multiagent learning algorithm based on cross entropy (CE) method [START_REF] Rubinstein | The Cross-Entropy Method for Combinatorial and Continuous Optimization[END_REF] is proposed. We associate a set of routing probabilities with nodes (customers) on the network, iteratively guiding the vehicles to find optimal routes, which minimize total cost, and satisfying capacity and time window constraints. Based on the performance of the routes traveled by the vehicles in each iteration, the choice probability distributions of next outgoing nodes are iteratively updated. We consider the optimum solution as a rare event to be estimated based on the importance sampling theory. More precisely, we specify a random mechanism to generate feasible solutions (samples), controlled by a set of parameterized probability distribution functions (pdf). Based on the performance of the samples, the parameters are updated iteratively by minimizing Kullback-Leibler cross-entropy in order to generate better solutions in next iterations. A set of vehicle-specific transition matrices is associated with the nodes of the network to construct subsequently a feasible route for each vehicle. As the capacity and time window constraints need to be satisfied during the route construction process, a sequential importance sampling technique is utilized by constructing the solution sequentially, conditional on vehicle's capacity and customer's time windows constraints. The stochastic route construction procedure is repeated until all customers are serviced. As the classical CE method may be trapped on the local optima at its early stages, some local search techniques are combined with the CE method to avoid this problem and to improve significantly the convergence speed of the classical CE method.

The rest of this paper is organized as follows. In section 2, we define the VRPTW problem and provide its mathematical formulation. Section 3 introduces the concept of the classical CE method and the proposed multiagent system for the VRPTW problem. Based on the performance of routes travelled by the vehicles, a hybrid scheme combining the agent-based CE algorithm and the local search procedure is proposed. This scheme enables local search performed only on a small subset of good solutions. Section 4 provides the computational results for Solomon's 100-customer VRPTW instances. Finally, the conclusions and future extensions are discussed.

Problem formulation

The mathematical formulation of the VRPTW problem can be stated as follows. Let ) , ( E V G be a directed graph with a vertex set V and an arc set E. The vertex set is composed of one depot (node 0) and n customers 1 to n, denoted as

{ } n V ,..., 1 , 0 = . The arc set is { } V j i j i j i E ∈ ∀ ≠ = , , ) , (
. Each customer is associated with an amount of , for which the customer cannot be serviced before i a and after i b . Let i s be the arrival time for customer i. The service time for customer i is denoted as i u with 0 > i u , but no service time at the depot, i.e. a and return to it after 0 b . Each arc

j i j i ≠ ∀ ), , (
has an asymmetric travel time ij t and an operation cost ij c .

The problem is to determine a set of routes, originating and terminating at the depot, such that total cost is minimal by satisfying: (1) each customer is serviced exactly once; (2) vehicle capacity cannot be violated; (3) all customers must be serviced within the service time windows. Let m r denote a route, starting and terminating at the depot, composed of a sequence of customers visited by the vehicle m. The k-th visited customer of vehicle m is denoted as

) (k r m . Let { } 1 , ,..., 2 , 1 , 0 + = m m m n n δ be a sequence of visiting order of the customers in m r with 0 ) 1 ( ) 0 ( = + = m m m n r r
. We define an indicator im y as 1 if customer i is serviced by vehicle m, and 0 otherwise. The set of routes for all vehicles is denoted as

{ } M r r r ,..., , 2 1 = r
. We formulate the VRPTW problem mathematically as follows:

Min { } ∑ ∑ ∈ δ ∈ - = M m k k r k r m m m c S 0 \ ) ( ) 1 ( ) (r (1) subject to { } ∑ ∈ ∈ ∀ ≤ 0 \ , m r i m i M m q d (2) { } 0 \ , 1 V i y M m im ∈ ∀ = ∑ ∈ (3) { } 0 \ , ) ( ) ( ) 1 ( ) 1 ( ) 1 ( m k r k r k r k r k r k s t u s m m m m m δ ∈ ∀ ≤ + + - - - (4) V i b s a i i i ∈ ∀ ≤ ≤ , (5)
{ } { } M m V i y im ∈ ∀ ∈ ∀ ∈ , 0 \ , 1 , 0 (6)
The objective function Eq. ( 1) minimizes the total travel cost. The constraints (2) mean that each vehicle cannot load goods exceeding its capacity restriction. The constraints Eq. ( 3) ensure that each customer is serviced exactly once. The constraints Eq. ( 4) ensure the consistency of service time for next visiting customer. The time windows are imposed by Eq. ( 5). The constraints Eq. ( 6) are the integrality constraints. Note that the above formulation is route-based, convenient for constructing routes for each vehicle based on the multiagent framework.

Cross entropy learning algorithm

The main concept of the CE method is to associate the optimization problem with an estimation problem throughout the route-searching process. The search process is characterized by a set of density functions associated with the nodes of the network. These density functions are iteratively updated based on the minimization of the Kullback-Leibler distance (cross entropy) between density functions and optimal density functions. In the following, we present first the multiagent model for general vehicle routing problem simulation. Then we describe the cross entropy multiagent learning algorithm to solve the VRPTW problem.

Multiagent model for vehicle routing problems with time windows

The multiagent simulation framework is very convenient for modeling and simulating the general vehicle routing problems since it captures the system behavior dynamics resulting from the interactions of supply and demand. Basically, the system is composed of a set of heterogeneous agents with predefined behavior. The advantage of the multiagent approach resides on its flexibility in capturing complex interactions between different components of the system.

The simulation of the VRPTW problem by the multiagent approach describes vehicle's optimal route search process under its capacity and service time windows constraints. In current application, the system is specified as:

• Customer agent: a set of customers with fixed demand is known a priori. Each customer agent needs to be visited exactly once. • Vehicle agent: a set of vehicle agents with fixed capacity is available in the system. Vehicle agents depart from and return to the depot by picking up customer requests under its capacity and service time windows constraints. The violation of these constraints is not allowed. • Environment (network): it is represented by a directed graph on which a set of vehicles operate on it. The network is characterized by a set of nodes representing the customers and a set of links associated with related characteristics. In static case, the travel time of link is fixed. In dynamic case, one can replace it with time-dependent travel cost function.

The present multiagent framework is convenient in dynamic situations with timedependent travel cost or stochastic customer demand.

Cross entropy learning algorithm

The main idea of the proposed cross entropy learning algorithm is that we specify a parameterized random mechanism for vehicle agents to generate feasible routes. Based on the performance of these "samples" (a sample is a feasible solution of the VRPTW), the parameters of the random mechanism are updated towards the optimal solutions. This stochastic search algorithm is originated from the importance sampling techniques aiming to increase the accuracy of rare-event probability estimation. Basically, the CE learning algorithm is composed of two steps [START_REF] Rubinstein | The Cross-Entropy Method for Combinatorial and Continuous Optimization[END_REF][19]: (1) generate a set of samples according to some stochastic mechanism; (2) update the parameters of stochastic mechanism based on the performance of the samples in order to generate better solutions at next iteration. As the classical CE method may be trapped in local optima, we propose a hybrid scheme by combining local search algorithms in order to overcome this problem and increase the solution quality.

The random feasible route generation mechanism moves vehicle agents from current customer/depot to next unvisited customers, one at each step, based on Markov chain on graph G(V,E), starting and ending at the depot. A set of vehiclespecific transition matrix (a routing probability matrix), P={ M p p p ,..., , 2 1 } are associated with each node of the graph to construct subsequently a feasible route for one vehicle agent. The stochastic route construction procedure is repeated until all customers are serviced. Different from the classical CE method, the idea of the proposed method is based on the sequential importance sampling techniques [START_REF] Rubinstein | Simulation and the Monte Carlo Method[END_REF], i.e. to construct a solution sequentially, conditional on capacity, while time windows constraints and partial solutions are already constructed before the current state. Note that the proposed CE learning algorithm is quite intuitive. It needs only to rescale the transition probabilities at current visiting node by eliminating infeasible candidates (next infeasible not yet visiting customers) in order to generate a feasible route at each step. If there is no feasible candidate to visit, the vehicle agent returns to the depot and next vehicle starts its route construction.

Let As mentioned above, we cast the original optimization problem to an estimation problem of rare event probability. To increase the sampling performance at each iteration, a sequence of new sampling densities, called importance sampling densities, need to be chosen. The optimal importance sampling density * P can be iteratively derived by minimizing the Kullback-Leibler cross-entropy distance [START_REF] Rubinstein | The Cross-Entropy Method for Combinatorial and Continuous Optimization[END_REF] [START_REF] De Boer | A Tutorial on the Cross-Entropy Method[END_REF]. First, a criterion of rare event (an approximate to optimal solution) γ is associated with each iteration and updated according to the performance of independent and identically distributed (i.i.d.) samples. We associate γ with an indicator { } 1)), parameterized by P. The probability of a global tour r is the multiplication of outgoing node choice probabilities in vehicle's route constructing process. Its logarithm can be written as:

{ } ∑ ∑∑ = + = ∈ = ) ( 1 1 1 , ) ( ln ) ; ( ln r R P r M m n k j i m ij k r m ij m p I f , (7)
where

) (r M
is the set of vehicles utilized for the solution r.

) (k ij R
denotes the set of feasible routes such that the k-th transition (move) is from node i to node j. The optimal important sampling distribution based on the minimization of the CE distance can then be obtained as:

M m V i p i j m ij ∈ ∀ ∈ ∀ = ∑ + Λ ∈ , , 1 ) ( ( 10
) M m E j i p m ij ∈ ∀ ∈ ∀ ≥ , ) , ( , 0 (11)
where

) (i + Λ
denotes the successors of node i.

By applying Karush-Kuhn-Tucker optimality conditions, the optimal solution of the above optimization problem can be obtained by differentiating with respect to m ij p as:

{ } { } { } { } { } { } { } { } ∑ ∑ ∑ ∑ ∑ ∑ = + = ∈ γ ≤ = + = ∈ γ ≤ + = ∈ γ ≤ + = ∈ γ ≤ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ ≈ ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ Ε ⎥ ⎥ ⎦ ⎤ ⎢ ⎢ ⎣ ⎡ Ε = - - N h n k k r S N h n k k r S n k k r S n k k r S m ij m i m m ij m m i m w m ij m w I I I I I I I I p 1 1 1 ) ( ) ( 1 1 1 ) ( ) ( 1 1 ) ( ) ( 1 1 ) ( ) ( 1 1 R r R r R r P R r P (12) where ) (k ij R
is the set of routes, for which the k-th transition is from node i to node j.

) (k i R
is the set of routes for which its k-th transition is starting from node i. N is the sample size.

Note that the above updating rule states that m ij p is updated based on the transition proportion from node i to node j of the vehicle m, conditional on the global tour performance satisfying γ ≤ ) (r S . As the above important sampling pdf could generate some infeasible tours in the sequential route construction process, a rescaling procedure is conducted at each step such that next node to be visited is drawn from the feasible node set. The CE learning algorithm is stated as follows.

Algorithm 1: The CE learning algorithm

Step 1: Initialize 0 P as a uniform pdf over the node set V. Order the endings of the time windows

V i b i ∈ ∀ ,
from the smallest to the biggest. Set the iteration index w = 1.

Step 2: Generate N i.i.d. samples according to the feasible route generation algorithm (described later).

Step 3: Order the solution performance

) (r S as a sequence ) ( ... ) ( ) ( 2 1 N S S S r r r ≤ ≤ ≤ .
Apply the local search procedure (described later) for the samples in the λN best solutions. We set

3 . 0 1 . 0 ≤ ≤ λ .
Step 4: Order the solution performance after the local search. The ρ -quantile of the performances

) ( r S , i.e. ⎡ ⎤ N ρ th lowest cost ( ⎡ ⎤
x denotes the smallest integer greater than or equal to x), is denoted as a new "rare-event" criteria:

⎡ ⎤ ) ( N w S ρ = γ (13)
As for the value of ρ and the sample size N, it is recommended that as the sampling number increases, the ρ value decreases. We set ρ as

V c 1 and 2 2 V c N = with 10 1 1 ≤ ≤ c and 1 5 . 0 2 ≤ ≤ c
, where the sample size N is smaller than in the classic CE method, reducing considerably the computational times.

Step 5: Calculate w P by Eq. ( 12) and apply the smoothed updating rule as follows:

w w w α α P P P ) 1 ( : 1 - + = - , (14)
It is recommended that α takes a value in the range of (see [START_REF] De Boer | A Tutorial on the Cross-Entropy Method[END_REF]).

Step 6: To avoid being trapped into local optimum, the following dynamic parameter adjustment process is applied.

If θ ≤ - - - - ) ( / ) ( ) (

Algorithm 2: Feasible route generation algorithm

This procedure rescales the transition matrix m p (eq. 12) for each vehicle in a sequential way such that each customer (node) is visited exactly once and satisfies vehicle's capacity and time windows constraints. The complexity of the rescaling procedure is

) ( 2 n O .
Step 1: Initialization. Set all customers as unvisited and vehicles depart from the depot. Set position index k=0 for each vehicle.

Step 2: Rescaling choice probability of next visiting customers. For vehicle m currently located at its node i (customer), rescale the choice probability m ij p for next visiting node j as follows. First, set the choice probability of infeasible nodes (not satisfying capacity and time windows constraints, eq. ( 2)-( 4)) as 0 and then normalize choice probabilities over all feasible outgoing nodes j to sum up to 1, i.e. , :

∑ Λ ∈ ′ ′ = j m j i m ij m ij p p p
where Λ is the set of feasible nodes for vehicle m at node i.

Step 3: If next visiting node is the depot, stop for vehicle m and set m: = m + 1, otherwise repeat step 2.

Local search procedure

To improve the solution quality for the samples in the ρ -quantile of the best solutions in main algorithm 1, we apply the local search procedure. The procedure contains two phases. First, a greedy local search is applied. Then a route-exchange local search procedure is applied.

• Greedy search: this procedure aims to reduce the number of utilized vehicles and exchanges some nodes to get the largest travel cost reduction. It contains two steps as follows: a. Remove the route with the least customers, b. Insert all nodes of the removed route, one node at a time, at the cheapest position of other routes. • Route exchange search: this procedure applies randomly one of the following two local search methods: c. Reverse move: reverse current ordering two nodes of the same route, d. K-Or-opt [15][22]: remove k nodes of current route and insert them in another position of the same route so that a feasible set of routes is preserved. This local search is implemented in the order of 1-Or-opt, 2-Oropt and 3-Or-opt.

Note that one can also apply some more efficient local search techniques such as LKH local search [START_REF] Helsgaun | An effective implementation of the Lin-Kernighan traveling salesman heuristic[END_REF] or sequential search procedures [START_REF] Irnich | Sequential search and its application to vehicle-routing problems[END_REF] to obtain an improved solution quality.

Computational experiments

The algorithm is tested on three datasets C1, R1 and RC1 of Solomon's 100-customer benchmark instances [START_REF] Solomon | Algorithms for the vehicle routing and scheduling problems with time window constraints[END_REF]. These datasets reflect different characteristics of customers' positions, tight or loose time windows constraints and vehicles' capacity. The algorithm is programmed in C++.

The results are shown in Table 1. The best known or optimal solutions are listed in the left part of Table 1. The results show that the proposed algorithm finds nearoptimal solutions with an average error of 6.24% (N=10000) in comparison with optimal solutions. As the reported results are based on only 1 to 3 tests, better solutions can be found if trying more tests and modifying related parameter settings.

The comparison of running times and solution quality based on different sample size shows that the running time is basically proportional to the sample size. Fig. 1 reports the outperforming results of the proposed hybrid scheme compared with the classical cross entropy method. Note that the hybrid scheme utilizes fewer samples ( ) to achieve better solution quality. Fig. 2 presents the average performance of different sample size on 12 instances of C1, R1 and RC1 classes. Fig. 3-5 presents the impact of different parameter settings on solution quality. These tests are performed on the R102 dataset of Solomon's 100 customer instances. Fig. 3 presents the smooth parameter α on the convergence speed. The test experiences suggest that α may be taken between 0.6 and 0.9 to obtain better solution quality. The impact of the size of the elite sample, parameterized by ρ , on solution quality is shown in Fig. 4. It suggests a range of [0.05, 0.1] for ρ . If ρ is too small, say 0.01, the algorithm converges quickly to local optima. The influence of the sample size of local search on the solution quality is not very significant (Fig. 5). However, more efficient local search techniques play an important role in increasing the performance of the proposed algorithm.

= = = θ = λ = ρ = α k k for all instances, except C103 with 15 . 0 , 07 . 0 = λ = ρ . 2.
The above mentioned result is based on 1 to 3 runs for each instance. 3. Time 1 is the total time executed on Dell Latitude E6400 with 2.53GHz and 3.48G memory. Time 2 is based on the execution of the same program on Asus Intel Pentium M processor 740 with 512MB memory. The speedup ratio between the two laptops is about 2.27. 4. The best know solution is based on [START_REF] Jepsen | Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows[END_REF].

Conclusions

In this paper, a cross entropy learning algorithm is proposed for solving vehicle routing problems with time windows. The advantage of the proposed approach is that the optimal routing probability is iterative learned based on importance sampling and rare event simulation theory. By combing the local search procedure and introducing the dynamic parameter adjustment procedure, the proposed method can avoid being trapped in the local optimum and find quickly near-optimal solutions. The numerical tests show also that the hybridization of the local search technique and the CE method can improve efficiently the solution quality. As the proposed method is based on an adaptive learning procedure, it provides a general method for solving vehicle routing problems under stochastic environment. Moreover, the proposed method needs only very small number of parameters settings. Its implementation is also relatively simple and flexible for various vehicle routing problems. Currently, the numerical study based on some Solomon's 100-customer VRPTW instances is implemented.

Future extension concerns the application of multiagent framework on general dynamic vehicle routing problems solving. It is also interesting to apply an appropriate data structure and more efficient implementation techniques for large scale instance (200 to 1000 customers). Moreover, other efficient local search techniques can be implemented to improve local search performance.

  of homogeneous/heterogeneous vehicles with M being the total number of vehicles. Each vehicle m has a fixed capacity m q . Each customer is associated with a time window

  any vehicle cannot depart the depot before 0

  the transition matrix of vehicle m be M transition probability for the vehicle m moving from node i to node j. Note that m p is a V V × matrix with the first column and row being the depot. We set and 0 otherwise. Each vehicle constructs a route sequentially based on its transition matrix and a prohibition list (infeasible candidates) until current state.

  performance of solution is better than γ , i.e. the probability distribution function (pdf) of r (defined around Eq. (

P.

  above equation derives the optimal important sampling pdf based on known 1 w It is equivalent to the following optimization problem:

  travel distance obtained in iteration w-1. If for some iteration w , the value of w γ stabilizes, i.e. stops; otherwise set w = w + 1 and go to step 2.

Fig. 1 .

 1 Fig. 1. Performance of CE multiagent learning algorithm compared with the classical CE method (without applying local search and dynamic parameter adjustment of Algorithm 1) (Solomon's 50-customer C101 instance, ρ =0.05, α =0.7, optimum= 362.4)

Fig. 2 .

 2 Fig. 2. Influence of sample size on the average performance of the algorithm over 12 instances of C1, R1 and RC1 classes of Solomon's 100-customer instances. The average optimum is 1082.47.

9 Fig. 3 .

 93 Fig. 3. Influence of the smooth parameter α on the algorithm performance (Solomon's 100-customer R102 instance, 2 . 1 , 0 . 2 , 02 . 0 , 2 . 0 , 05 . 0 2 1 = = = θ = λ = ρ k k

Fig. 4 . 4 Fig. 5 .

 445 Fig. 4. Influence of the elite sample size on the algorithm performance (Solomon's 100-customer R102 instance, N=7000, 2 . 1 , 0 . 2 , 02 . 0 , 2 . 0 , 7 . 0 2 1 = = = θ = λ = α k k )

Table 1 .

 1 Application of CE multiagent learning algorithm to Solomon's VRPTW 100 customer instances

	Instance	Optimum/best								CE multiagent learning algorithm
		known solution 4					N=7000							N=10000
		Distance		Distance 1 Relative	Time 1	Time 2	Distance 1 Relative	Time 1	Time 2
									error (%)	(sec.)		(sec.)	error (%)	(sec.)	(sec.)
	C101		827.3			840.1	1.55%			1105 2509	898.7	8.63% 1930 4384
	C103		826.3			890.6	7.78%			1479 3359	896.3	8.47% 1942 4411
	C105		827.3			867.1	4.82%			1366 3104	869.3	5.08% 2250 5111
	C107		827.3			843.1	1.91%			1407 3196	841.1	1.67% 2157 4900
	R102	1466.6			1551.0	5.75%			1325 3010	1539.1	4.94% 2151 4886
	R104		971.5			1061.0	8.04%			1876 4263	1077.8	9.76% 2643 6003
	R106	1234.6			1334.0	8.05%			1292 2936	1323.1	7.17% 2074 4712
	R108		932.1			1040.3	8.26%			1557 3537	1044.2	8.67% 2367 5378
	RC102	1457.4			1571.8	7.85%			1285 2918	1584.4	8.71% 2354 5347
	RC104	1132.3			1248.8	9.98%			1721 3909	1226.6	8.02% 2242 5092
	RC106	1372.7			1477.6	3.71%			1311 2978	1465.6	2.87% 2045 4647
	RC108	1114.2			1242.0	8.97%			1427 3242	1241.2	8.90% 2126 4829
	Average error									6.39%							6.24%
	Remark: 1.The parameter settings are
		0	.	7	,	0	, 05 .	0	, 2 .	0	.	, 02	1	2	.	, 0	2	1	.	2

Acknowledgements

This research has benefited from a grant of ANR (the French Agency for Research) project, Mutualisation et Optimisation de la Distribution Urbaine de Marchandises (MODUM).


Sven Schmiedel

; Blettner

; Kaatsch

; Schüz

Spatial clustering and space-time clusters of leukemia among children in Germany, 1987-2007

Keywords: leukemia, children, clustering, spatial, Germany

Leukemia is the most frequent malignancy in children under the age of 15 years. The question of whether childhood leukemia has a tendency for clustering or forms clusters has been studied for several decades. The environmental risk factor discussed most often is infection, which might result in spatial clustering and spacetime clusters. The German Childhood Cancer Registry provided data on 11 946 children with leukemia diagnosed during 1987-2007, as classified in the International Classification for Childhood Cancer (third edition), aggregated by municipality. We used the Potthoff-Whittinghill model to test for a general trend for clustering and the spatial scan statistic to search for localized clusters. No evidence of global clustering was found, neither for the whole study population nor in sub-groups by age, period or population density, or for different types of leukemia. A similar result was found for localized clusters. The analysis shows no evidence of a tendency to clustering, however, aggregation of data at the municipality level might have diluted small localized clusters. The results of this study do not provide support for the hypothesis of an infectious or a spatial environmental etiology of childhood leukemia.

Introduction

Leukemia is the most frequent malignancy in children under the age of 15 years, with an incidence rate of 5.2 per 100 000 children per year in Germany during 1998-2007. It is a disease of early childhood, with a distinct peak in incidence rate between the ages of 2 and 5 years. The major morphological groups of childhood leukemia are acute lymphoblastic leukemia (ALL) and acute myeloblastic leukemia (AML) [START_REF] Greaves | Science, medicine, and the future: childhood leukaemia[END_REF].

The question whether childhood leukemia has a tendency to cluster has been studied for more than 70 years [START_REF] Kellett | Acute myeloid leukaemia in one of identical twins[END_REF].

It is important to distinguish between 'clusters' and 'clustering'. Whereas a cluster emerges in a small defined area and therefore consists of only a few cases, clustering involves the overall propensity of cases to form clusters. Furthermore, statistical tests on clusters and clustering can be classified as 'focused' or 'general'.

A focused test covers the inclusion area around predefined foci, whereas a general test is of the overall pattern in a study area [START_REF] Besag | The detection of clusters in rare diseases[END_REF].

In the early twentieth century, ALL was thought to be an infectious disease [START_REF] Ward | The infective theory of acute leukaemia[END_REF], and clusters were interpreted as providing supporting evidence for this hypothesis.

Whether infections play a causal role in leukemogenesis is still unclear. There are currently three hypotheses on the role of infections in the etiology of childhood leukemia. (1) Kinlen's hypothesis is based on an unusual type of population mixing in isolated areas with low population density [START_REF] Kinlen | Evidence for an infective cause of childhood leukaemia: comparison of a Scottish new town with nuclear reprocessing sites in Britain[END_REF]. He proposed that the transiently higher rates of childhood leukemia follows this type of population mixing, which leads to infections in previously unexposed susceptible children by infected newcomers.

Leukemia of any kind in both populations would be a rare outcome as a reaction to yet-unknown but mild infectious agents and reflects the immune naivety in both populations. (2) Greaves' 'delayed-infection' hypothesis sought to explain the peak incidence of common B-cell precursor ALL in children aged 2-5 years by proposing infections as a crucial second factor in the context of the 'two-hit model' of Knudson, which postulates that cancer is the result of at least two mutations (hits) to a cell's DNA [START_REF] Knudson | Mutation and cancer: statistical study of retinoblastoma[END_REF]. Greaves' hypothesis postulates an aberrant response to infections as a second necessary 'hit' after lack of exposure to infectious agents during infancy and subsequent failure of modulation of the child's immune system [START_REF] Greaves | Science, medicine, and the future: childhood leukaemia[END_REF]. (3) Smith's hypothesis places the second essential hit during pregnancy, and not during infancy [START_REF] Smith | Considerations on a possible viral etiology for B-precursor acute lymphoblastic leukemia of childhood[END_REF]. The causative agent induces an infection in a pregnant woman, and the infection is then transferred to the fetus and increases the child's risk for ALL before the age of 5 years. All three hypotheses claim a possible role for infections in the etiology of leukemia. If a general trend towards spatial clustering was observed the hypothesis of an infectious etiology of childhood leukemia would be strengthened. If space-time clusters would be detected this would be more in line with the hypothesis of Kinlen.

Since 1990, there have been to our knowledge 15 peer-reviewed publications on studies of clusters, spatial clustering or space-time interaction of childhood leukemia in different countries, in different age groups and with the use of various statistical methods. Ten had their focus on clusters [START_REF] Muir | Clustering'-real or apparent? Probability maps of childhood cancer in the West Midlands Health Authority Region[END_REF][START_REF] Hjalmars | Childhood leukaemia in Sweden: using GIS and a spatial scan statistic for cluster detection[END_REF][START_REF] Mosavi-Jarrahi | Clustering of childhood cancer in the inner city of Tehran metropolitan area: a GIS-based analysis[END_REF] and spatial clustering [START_REF] Westermeier | Applicability of the Poisson distribution to model the data of the German Children's Cancer Registry[END_REF][START_REF] Knox | Spatial clustering of childhood cancers in Great Britain[END_REF][START_REF] Petridou | Aggregation of childhood leukemia in geographic areas of Greece[END_REF][START_REF] Alexander | Clustering of childhood leukaemia in Hong Kong: association with the childhood peak and common acute lymphoblastic leukaemia and with population mixing[END_REF][START_REF] Alexander | Spatial clustering of childhood leukaemia: summary results from the EUROCLUS project[END_REF][START_REF] Dockerty | An assessment of spatial clustering of leukaemias and lymphomas among young people in New Zealand[END_REF][START_REF] Mcnally | Spatial clustering of childhood cancer in Great Britain during the period 1969-1993[END_REF], two on space-time interaction alone [START_REF] Gilman | Childhood cancers: space-time distribution in Britain[END_REF][START_REF] Gustafsson | Space-time clustering of childhood lymphatic leukaemias and non-Hodgkin's lymphomas in Sweden[END_REF]. Three studies investigated both [START_REF] Birch | Space-time clustering patterns in childhood leukaemia support a role for infection[END_REF][START_REF] Mcnally | Space-time clustering analyses of childhood acute lymphoblastic leukaemia by immunophenotype[END_REF][START_REF] Bellec | Spatial and space-time clustering of childhood acute leukaemia in France from 1990 to 2000: a nationwide study[END_REF]. Four found no spatial clustering and clusters at all [START_REF] Muir | Clustering'-real or apparent? Probability maps of childhood cancer in the West Midlands Health Authority Region[END_REF][START_REF] Hjalmars | Childhood leukaemia in Sweden: using GIS and a spatial scan statistic for cluster detection[END_REF][START_REF] Mosavi-Jarrahi | Clustering of childhood cancer in the inner city of Tehran metropolitan area: a GIS-based analysis[END_REF][START_REF] Westermeier | Applicability of the Poisson distribution to model the data of the German Children's Cancer Registry[END_REF], four found statistically significant results for at least one subgroup [START_REF] Alexander | Clustering of childhood leukaemia in Hong Kong: association with the childhood peak and common acute lymphoblastic leukaemia and with population mixing[END_REF][START_REF] Dockerty | An assessment of spatial clustering of leukaemias and lymphomas among young people in New Zealand[END_REF][START_REF] Mcnally | Space-time clustering analyses of childhood acute lymphoblastic leukaemia by immunophenotype[END_REF][START_REF] Bellec | Spatial and space-time clustering of childhood acute leukaemia in France from 1990 to 2000: a nationwide study[END_REF], and five found spatial clustering for the overall group of leukemia [START_REF] Knox | Spatial clustering of childhood cancers in Great Britain[END_REF][START_REF] Petridou | Aggregation of childhood leukemia in geographic areas of Greece[END_REF][START_REF] Alexander | Spatial clustering of childhood leukaemia: summary results from the EUROCLUS project[END_REF][START_REF] Mcnally | Spatial clustering of childhood cancer in Great Britain during the period 1969-1993[END_REF][START_REF] Birch | Space-time clustering patterns in childhood leukaemia support a role for infection[END_REF]. The five studies which investigated space-time interaction all found statistically significant results [START_REF] Gilman | Childhood cancers: space-time distribution in Britain[END_REF][START_REF] Gustafsson | Space-time clustering of childhood lymphatic leukaemias and non-Hodgkin's lymphomas in Sweden[END_REF][START_REF] Birch | Space-time clustering patterns in childhood leukaemia support a role for infection[END_REF][START_REF] Mcnally | Space-time clustering analyses of childhood acute lymphoblastic leukaemia by immunophenotype[END_REF][START_REF] Bellec | Spatial and space-time clustering of childhood acute leukaemia in France from 1990 to 2000: a nationwide study[END_REF]. However, in the explorative approach of Bellec et al. [START_REF] Bellec | Spatial and space-time clustering of childhood acute leukaemia in France from 1990 to 2000: a nationwide study[END_REF] 140 Knox tests were carried out, which leads to problems due to multiple testing.

In summary there is no clear evidence for or against spatial clustering. It is remarkable that most of the studies conducted in the UK show a trend towards spatial clustering, especially in the age group of the incidence peak of childhood leukemia of ages 2 to 5 years and also for ALL, in line with the infectious hypotheses (see above). The populations in these studies partially overlap, and the results are therefore not independent. The most comprehensive study from the UK is summarized in the eleventh report of Committee on Medical Aspects of Radiation in the Environment (COMARE) and here a trend for spatial clustering was found, although the effect was small [START_REF]Eleventh Report. The distribution of childhood leukaemia and other childhood cancer in Great Britain 1969-1993[END_REF]. Studies in other countries show a more diverse picture, although the use of various methods makes direct comparison difficult. The largest study to date, which included more than 13 000 children in several mainly European countries, the so-called EUROCLUS project, showed a statistically significant trend to spatial clustering, although, again, the trend was weak [START_REF] Alexander | Spatial clustering of childhood leukaemia: summary results from the EUROCLUS project[END_REF]. For a detailed review, see McNally and Eden [START_REF] Mcnally | An infectious aetiology for childhood acute leukaemia: a review of the evidence[END_REF].

As infections and most of the environmental agents possibly related to the risk of childhood leukemia, like ionizing radiation due to domestic exposure to radon [START_REF] Raaschou-Nielsen | Indoor radon and childhood leukaemia[END_REF], air pollutants [START_REF] Whitworth | Childhood lymphohematopoietic cancer incidence and hazardous air pollutants in southeast Texas, 1995-2004[END_REF] or pesticides [START_REF] Rudant | Household exposure to pesticides and risk of childhood hematopoietic malignancies: The ESCALE study (SFCE)[END_REF], are spatially heterogeneously distributed, it is conceivable that childhood leukemia also shows a tendency to spatial clustering with a temporal component. Thus, spatial and space-time analysis of the distribution of childhood leukemia might give a hint to environmental agent(s), possibly infections, which are involved in the etiology of the disease.

Our study on clustering of leukemia in Germany is based on data from the German Childhood Cancer Registry, covering a population of approximately 13.2 million children aged 0-14 years per year. The presence of clusters and clustering was investigated at municipality level.

Material and Methods

Cases

We included all children up to the age of 14 years with primary leukemia diagnosed in the period 1987-2007 and registered in the German Childhood Cancer Registry, yielding 11 946 cases. We excluded 36 cases (0.3%) as they were either anonymized (n = 9) or information on the municipality of residence at the time of diagnosis was missing (n = 27). The German Childhood Cancer Registry is estimated to be at least 95% complete [START_REF] Kaatsch | German Childhood Cancer Registry[END_REF][START_REF] Steliarova-Foucher | Quality, comparability and methods of analysis of data on childhood cancer in Europe (1978-1997): report from the ACCIS project[END_REF]. Children under 15 years accounted for on average fewer than 1 000 inhabitants in 9 847 municipalities (80.3 %), for 1 000-10 000 in 2 286 municipalities (18.6 %), for 10 000-100 000 in 125 municipalities (1.0 %) and for > 100 000 in four municipalities (0.03 %). Therefore the expected number of cases in the municipalities varied from 3.3 x 10 -4 to 437. Latter is found in Berlin which is a single administrative unit, which has more than 3.4 million inhabitants.

Statistical methods

Usually, a binomial distribution with parameter p of the chance for being a case in a population of size n should be used for incidence data aggregated at municipality level. As for rare diseases like childhood leukemia p is very small and n is usually very large, a Poisson distribution with intensity parameter λ = n p can be used as an approximation of the binomial distribution. The major assumption of Poisson distribution is the equality of variance and mean. A greater variance than the mean is called 'overdispersion', which is associated with heterogeneity in the data and hence with clustering. The Q statistic is obtained by dividing the empirical variance by the empirical mean [START_REF] Fisher | The significance of deviations from expectation in a Poisson series[END_REF]; if the observed cases follow a Poisson distribution, the mean and the variance should be equal and the statistic should be close to 1. This method was used in a previous investigation of clustering with data from the German Childhood Cancer Registry [START_REF] Hjalmars | Childhood leukaemia in Sweden: using GIS and a spatial scan statistic for cluster detection[END_REF]. The major drawback of this test is that it does not include the number of inhabitants in each municipality. Therefore, municipalities were classified into 100 groups by the number of expected cases to make the variation in the groups comparable.

The Potthoff-Whittinghill statistic is more often used and tests for spatial heterogeneity or a trend for clustering. Under the null hypothesis, the number of cases in each municipality follows a Poisson distribution, as explained above. The alternative to overdispersion is described by a negative binomial, for which the variance of the mean ratio is 1 + β [START_REF] Potthoff | Testing for homogeneity. I. The binomial and multinomial distribution[END_REF][START_REF] Potthoff | Testing for homogeneity. II. The Poisson distribution[END_REF][START_REF] Muirhead | Methods for detecting disease clustering, with consideration of childhood leukaemia[END_REF]. This method expresses overdispersion in relation to the mean by a single parameter β, and β = 0 is tested in a score test.

Analyses were conducted overall and in subgroups by age (0-4, 5-9, 10-14 years), by morphology (all leukemia, ALL, AML) and by time period (1987)(1988)(1989)(1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007). R software was used for analysis [START_REF] Development | R: A language and environment for statistical computing[END_REF].

The Potthoff-Whittinghill method disregards spatial relations among municipalities. In order to use this additional information, the Kulldorff spatial scan statistic was also used for investigating clusters [START_REF] Kulldorff | A spatial scan statistic[END_REF]. This method involves drawing all possible circles in the study region with municipalities' centroids as the centers and determining whether there were more cases inside the circle than expected. The most likely cluster is found by a likelihood ratio test. This method can be expanded to include the time dimension (space-time cluster), whereby the two-dimensional circles drawn in the area can be interpreted as cylinders in a three-dimensional version. We used this approach in order to find space-time clusters. SaTScan software was used for the Kulldorff spatial scan statistic [START_REF] Kulldorff | SatScanTMv5.1: Software for the spatial and space-time scan statistics[END_REF].

Results

Table 1 shows the distribution of the leukemia cases by diagnostic subgroup, as defined by the ICCC-3.

Figure 1 shows the mean and the variance for each of the 100 groups of municipalities based on increasing number of expected cases. The scatter plot covers only 96 of the 100 groups, as three groups were omitted as no cases were observed, and the group with the largest number of expected cases was excluded as its variance was an outlier owing to large differences in the number of inhabitants.

The figure shows that the variance and the mean are close in each group, indicating that the observed cases per municipality follow a Poisson distribution. The variance was greater than the mean only in the last group, due to greater variation in the numbers of children in the largest cities of Germany.

The Q statistic confirms this observation. If the observed cases follow a Poisson distribution, the statistic is expected to be 1. The minimum of the statistic for groups 1-99 was 0.74 and the maximum was 1.81; and for three of these 99 groups, a Q statistic could not be calculated, as no cases were observed. For group 100, the variance was large (72.73), because of the large variation in the number of inhabitants in the municipalities in this group. If Q is greater than 1, this indicates a tendency to overdispersion. This would be expected for half of the groups due to chance; however, this was the case in only 36 of the 97 groups studied.

The score test based on the Potthoff-Whittinghill model (Table 2) showed no statistically significant results overall or for any of the subgroups. Furthermore, classification into former German Democratic Republic (East Germany) and former Federal Republic of Germany (West Germany) and into municipalities with low population density (< 50 persons per 50 km²) did not alter this overall result.

The municipalities were also aggregated into 459 units in order to achieve equal area size (900 km², which is the area of Berlin, Figure 2). The result based on these 459 units was not statistically significant for overall childhood leukemia (β = -0.057, SE(β) = 0.066, p value = 0.77, not calculated for subgroups).

Using the spatial scan statistic (Table 3) we did not find evidence for clusters, neither overall nor in any of the subgroups. This was true for both the purely spatial and for the space-time analysis.

Discussion

This study is based on a large data set from an international highly reputed cancer registry. With 11 946 cases of childhood leukemia, it is one of the largest investigations of spatial clustering of childhood leukemia. None of the analyses showed any evidence for a general tendency to clustering of cases of childhood leukemia. Neither localized clusters nor a tendency to spatial clustering were found in the data. Further, the results of analyses of subgroups by age, morphologic type of leukemia and study period were in line with this overall finding; in particular, there was no evidence of clustering of ALL cases or of cases in children aged 2-5 years, two subgroups of a priori interest on the basis of previous research.

The findings of the present study are in contrast to those of the EUROCLUS project [START_REF] Birch | Space-time clustering patterns in childhood leukaemia support a role for infection[END_REF], in which significant evidence for clustering of all leukemia was found in small administrative units in Europe (p = 0.03). In a recent publication from the UK [START_REF] Bellec | Spatial and space-time clustering of childhood acute leukaemia in France from 1990 to 2000: a nationwide study[END_REF], the authors reported a statistically significant result for overdispersion, providing evidence for spatial clustering for all leukemia and ALL, although the effects were small (overall: β = 0.045 (90 % CI: 0.02; 0.07), ALL: β = 0.05 (90 % CI: 0.025; 0.07)).

There are several possible explanations for these contrasting results. One is that the smallest administrative unit in the United Kingdom, a 'ward', usually has about 6 000 inhabitants. Therefore, any variation in environmental exposure within each administrative unit is likely to be small. In Germany, administrative units vary from those containing only a few people to metropolitan areas like Berlin, with more than 3 million people. Areas with few inhabitants, and therefore with no or one case, are to contribute no information to the statistic based on the Potthoff-Whittinghill model. In cities with many inhabitants, the variations in exposure may be too great to reveal clustering across the city. The last problem cannot be addressed, i.e. large cities cannot be subdivided into smaller units, but small municipalities can be aggregated to obtain areas with larger numbers. This was done by laying a grid with a pixel size of 900 km² (size of Berlin) over a map of Germany and combining the municipalities with centroids in each grid, resulting in 459 artificially created areas (Figure 2). The result of the test did not, however, change the overall finding of no clustering.

Our results are in line with those of a study in France [START_REF] Dockerty | An assessment of spatial clustering of leukaemias and lymphomas among young people in New Zealand[END_REF]; however, French administrative units show similar diversity in the numbers of inhabitants to that in Germany.

By using the approach of Potthoff-Whittinghill, a test with reasonable statistical power in a variety of overdispersion models was chosen [START_REF] Potthoff | Testing for homogeneity. II. The Poisson distribution[END_REF]. It is an appropriate approach to find a general trend of clustering, but not appropriate to locate specific clusters. To locate specific clusters we used the spatial scan statistic as complimentary approach.

This approach has most statistical power in detecting localized clusters appearing in a circular shape [START_REF] Song | Power evaluation of disease clustering tests[END_REF] in a variety of different assumptions of clusters in urban, rural or mixed settings. This method was also used finding space-time clusters; however, no statistically significant results were found.

Strengths of our study are the large sample size, the long observation period and the virtually complete case ascertainment based on an established population-based cancer registry. Moreover, the denominator for the calculations, i.e. the population sizes in each municipality, is highly accurate due to the German system of compulsory resident registration. One limitation of our study is that it is based on data aggregated at municipality level. This might have diluted any effect in two ways. First, clustering might occur across the borders between municipalities. This would be blurred by the arbitrariness of the demarcation and therefore could not be identified.

Secondly, it is possible that clustering exists within large municipalities, which have a large number of inhabitants, and hence cannot be discerned.

At first glance, our findings appear to be in contrast to the statistically significant results of a German study that showed a decreasing risk for childhood leukemia by distance from a nuclear power plant [START_REF] Kaatsch | Leukaemia in young children living in the vicinity of German nuclear power plants[END_REF][START_REF] Spix | Case-control study on childhood cancer in the vicinity of nuclear power plants in Germany 1980-2003[END_REF]. There are two possible explanations for this. First, clusters around the nuclear power plants may be too small to be found at the aggregated municipality level used in this study. Secondly, it is possible that local investigation of a cluster leads to statistically significant results, even though it is still in the range of expectation at the global (or national) scale.

The results of this study do not provide support for the hypothesis of an infectious etiology of childhood leukemia. The clusters found with the spatial scan statistic were not statistically significant. However, it might be that in an albeit large, still relatively homogeneous population like that of Germany, the amount of contact with infectious agents depends more on the individual than on the area, so that no strong spacetime effect is to be expected.

Analysis in the whole of Germany over a 20-year period showed no evidence for a tendency for clustering of childhood leukemia. Thus, although localized clusters might exist and be significant, these might be in the expected range of the global pattern. The results of our study do not provide support for the hypothesis of a spatial environmental factor or an infectious etiology of leukemia in children. Group 100, with the largest estimated number of cases, is not included as it is an outlier, because of to varying numbers of inhabitants. The first three groups were also excluded, as no case was observed.

  Cases are coded according to the International Classification of Childhood Cancer, third edition (ICCC-3) [30]. Contrary to earlier versions of the ICCC, myeloproliferative diseases are now part of the first class, 'Leukemias, myeloproliferative and myelodysplastic diseases', of the ICCC-3, which has been in use at the registry since 2006. Actually 2.9% of the cases have these diseases which represent preleukemic stages. Furthermore, the two subgroups separately analyzed in the result section include only cases with leukemia (ALL and AML). Data from the former German Democratic Republic have been included in the registry since 1991, i.e. shortly after the reunification of Germany. Study population Germany consists of 12 500 administrative units, of which 238 are not inhabited, leaving 12 262 inhabited areas with a total of 82 217 658 inhabitants on an area of 353 044.1 km³. Children under the age of 15 years represent 13.7 % of the inhabitants of Germany (all data are for 31 December 2007, from Bundesamt für Kartografie und Geodäsie, Statistisches Bundesamt). The average population under 15 years in the municipalities ranged from 1 to 438 554 (data on inhabitants in each municipality of each year of the study period 1987-2007 were collected from the statistical offices of each Federal state, for the federal states of the former German Democratic Republic for the years 1991-2007).

Figure 1 .

 1 Figure 1. Mean and variance on logarithmic scale for 100 groups formed from 12 262

Figure 2 .

 2 Figure 2. Aggregation of 12 262 German municipalities into 30 x 30 km² squares by

Table 3 .

 3 Result of use of spatial scan statistic on detection of clusters of childhood leukemia in Germany in the period 1987-2003; purely spatial and space-time analyses

				1987-2007			1987-1997 1998-2007
			0-14 years	0-4 years 5-9 years 10-14 years 0-14 years 0-14 years
	Spatial	Radius (km)	107.7	20.9	27.0	68.4	25.0	46.8
		Observed	1092	69	35	170	48	168
		Expected	956	39	17	120	25	120
		p value	0.28	0.39	0.91	0.25	0.54	0.57
	Space-time	Period* 1998-2007 1988-1990	2003 2006-2007 1990-1991 2005-2007
		Radius (km)	121.3	9.6	7.1	5.8	4.4	32.4
		Observed	539	8	3	5	5	53
		Expected	423	0.6	0.02	0.15	0.11	25
		p value	0.15	0.32	0.72	0.56	0.09	0.70

* Defined by the cluster with the lowest p value

Acknowledgements

The authors would like to thank Claudia Spix and Irene Jung at the German Childhood Cancer Registry for extracting data. We also thank Jørgen Olsen and Finn Diderichsen for the support and Richard Feltbower for the useful discussion on methodology. Sven Schmiedel is supported by an international PhD stipend from the The Danish Strategic Research Council (grant number 645-06-0479).

Childhood Cancer Registry East Germany † * 782 -0.014 [0.023] (0.64) ¶ acute lymphoblastic leukemia, ‡ acute myeloblastic leukemia, † West Germany includes the federal states of the former Federal Republic of Germany (Schleswig-Holstein, Hamburg, Lower Saxony, Bremen, North Rhine-Westphalia, Hesse, Rhineland-Palatinate, Saarland, Baden-Württemberg, the Free State of Bavaria, Berlin), East Germany includes the federal states on the territory of the former German Democratic Republic (Mecklenburg-Western Pomerania, Brandenburg, Saxony-Anhalt, the Free State of Thuringia, the Free State of Saxony) * was only analysed in the second study phase (1988)(1989)(1990)(1991)(1992)(1993)(1994)(1995)(1996)(1997)(1998)(1999)(2000)(2001)(2002)(2003)(2004)(2005)(2006)(2007) as East Germany is included in the registry since 1991