Angeliki Skoura

Vasileios Megalooikonomou

Predrag R Bakic
email: predrag.bakic@uphs.upenn.edu

Andrew D A Maidment
email: andrew.maidment@uphs.upenn.edu

Classifying Ductal Tree Structures Using Topological Descriptors of Branching

Keywords: medical image classification, galactography, tree-like structures

We propose a methodological framework for the classification of the tree-like structures of the ductal network of human breast regarding radiological findings related to breast cancer. Initially we perform the necessary preprocessing steps such as image segmentation in order to isolate the ductal tree structure from the background of x-ray galactograms. Afterwards, we employ tree characterization approaches to obtain a symbolic representation of the distribution of trees' branching points. Our methodology is based on Sholl analysis, a technique which uses concentric circles that radiate from the center of the region of interest. Finally, we apply the k-nearest neighbor classification scheme to characterize the tree-like ductal structures in galactograms in order to distinguish among different radiological findings. The experimental results are quite promising as the classification accuracy reaches up to 82% indicating that our methods may assist radiologists to identify image biomarkers in galactograms.

Introduction

Several structures in human body follow a tree-like topology. Characteristic examples include the bronchial tree, the blood vessel network, the nervous system and the breast ductal network (Fig. 1). Nowadays, medical imaging modalities, such as Magnetic Resonance Imaging (MRI), Computed Tomography (CT) and radiographs have made available large series of images that visualize the above mentioned structures. Properties of the tree topology including spatial distribution of branching, tortuosity and asymmetry have been analyzed in literature so far and have been associated with altered function and pathology [START_REF] Bullit | Analyzing attributes of vessel populations[END_REF]. This type of information can be used to facilitate more accurate medical diagnoses. For example regional changes in vessel tortuosity were utilized to identify early tumor development in human brain [START_REF] Bullit | Vessel Tortuosity and Brain Malignancy: A Blinded Study[END_REF]. Moreover, the three dimensional analysis of the airway tree inside the lungs was used to distinguish pathologic formations from normal lung structures [START_REF] Tschirren | Matching and anatomical labeling of human airway tree[END_REF]. Similarly, careful examination of the morphology of the ductal network visualized in galactograms provided valuable information related to the risk of breast cancer [START_REF] Dinkel | Predictive value of galactographic patterns for benign and malignant neoplasms of the breast in patients with nipple discharge[END_REF]. The motivation of this study is to provide insight into the discriminative characteristics of ductal networks in normal galactograms and in galactograms with reported radiological findings. Here, we propose descriptors for trees' topological analysis: the Sholl Analysis, the Sectoring Analysis and the Combined Method. These descriptors focus on the spatial distribution of tree branching points and we employ this information to characterize normal or disease states of the breast ductal tree. In order to evaluate the new descriptors, we use the classification scheme of k-nearest neighbors. Our approach has the potential benefit of advancing our understanding in breast anatomy and physiology and could assist early cancer detection and cancer risk estimation. Moreover, the proposed methodology could also be applied to other tree like structures of the human body such us the blood vessel network in order to detect ischemic or thrombotic patterns, or the bronchial tree to provide a primary detection of lung cancer or other malformations.

Background

Several studies in the literature have demonstrated that examining the morphology of the ductal network can provide valuable insight into the development of breast cancer and assist in diagnosing pathological breast tissue. For example, Bakic et al. [START_REF] Bakic | Classification of galactograms with ramification matrices: preliminary results[END_REF] proposed a quantitative method based on Ramification matrices (R-matrices) to classify galactograms regarding radiological findings. An R-matrix represents a description of branching structures at the topological level and the elements of such a matrix represent the probabilities of branching at various levels.

More recently, Megalooikonomou et al. [START_REF] Megalooikonomou | A Representation and Classification Scheme for Tree-like Structures in Medical Images: Analyzing the Branching Pattern of Ductal Trees in X-ray Galactograms[END_REF] proposed a multi-step approach for representing and classifying trees in medical images including galactograms. The authors employed tree encoding techniques such as the depth-first string encoding and the Prüfer encoding to obtain a symbolic string representation of the tree's branching topology. Based on these encodings, the problem of comparing tree structures was reduced to the problem of string comparison. Moreover, they used the tf-idf text mining technique to assign a weight of significance to each string term. The classification was performed using the k-nearest neighbor scheme and the cosine similarity metric.

In the field of mammography, fractal analysis was also employed for characterizing the parenchymal pattern, distinguishing architectural distortion and detecting microcalcifications [START_REF] Kontos | Classification of galactograms using fractal properties of the breast ductal network[END_REF]. Fractal analysis can be used to describe properties that are not interpretable by the traditional Euclidean geometry and most of the above approaches utilize fractal analysis to characterize texture properties. In another approach, the tree asymmetry index was employed to characterize the topology of the ductal network in order to classify galactograms [START_REF] Skoura | Classification of ductal tree structures in galactograms[END_REF]. Finally, a combination of texture and branching descriptors was investigated to deepen the understanding of the relationships among the morphology, function and pathology of the ductal tree [START_REF] Barnathan | Analyzing Tree-Like Structures in Biomedical Images Based on Texture and Branching: An application to Breast Imaging[END_REF].

In this paper, we compare the proposed descriptors to the state-of-the-art Prüfer encoding approach and show that our methods compare favorably to it. A detailed description of the Prüfer encoding technique applied in galactograms can be found in [START_REF] Megalooikonomou | A Representation and Classification Scheme for Tree-like Structures in Medical Images: Analyzing the Branching Pattern of Ductal Trees in X-ray Galactograms[END_REF].

Methodology

The goal of this paper is to investigate whether the distribution of branching points of ductal trees consists a discriminative factor concerning radiological findings in galactograms. Towards this direction, we present three methods that capture topological information regarding the tree branching points. The proposed methodology for analysis begins with the preprocessing of the images to segment the tree-like structures from the rest of the tissue depicted in the medical images. Then, we perform characterization of the extracted tree topologies applying the proposed techniques. Given a collection of such structures and the query tree, we perform similarity searches in order to find the ductal tree structures that are most similar to a query. Finally, we use the k-nearest neighbor classification scheme to evaluate the accuracy of the methods.

Image Preprocessing

Image preprocessing includes several steps needed to extract the tree structures from the background of the original medical images (Fig. 2(a)) and transform them into a suitable form for analysis. Initially, the Region Of Interest (ROI) of the galactograms, which is the part of the medical image where the ductal tree appears, is recognized (Fig. 2(b)). After focusing on the ROI, the segmentation of tree-like structures follows. Image segmentation is the boundary identification of objects or regions of special interest from the rest of the displayed objects or the background. In the application presented here, the task of segmentation has been done manually by medical experts (Fig. 2(c)). Then, the tree-like structures are reconstructed by identifying true positive branching points often resolving potential ambiguities such as anastomoses occurring mostly as a result of two-dimensional acquisition artifacts [START_REF] Moffat | Three dimensional anatomy of complete duct systems in human breast: pathological and developmental implications[END_REF]. Although more sophisticated and fully-automated methods of reconstruction could potentially be applied, such an approach is beyond the scope of this work as our main objective is the feature analysis and the classification of the tree-like structures. The final preprocessing step is the skeletonization of the ductal structures. This thinning process that reduces most of the original foreground pixels in a binary image to obtain a skeletal remnant that preserves the extent and the connectivity of the original structure is necessary in order to detect the exact of the branching points.

Spatial Distribution of Tree Branching Points

Sholl Analysis.

The first method that we propose for capturing information about the spatial distribution of branching points is based on Sholl analysis [START_REF] Sholl | Dendritic organization in the neurons of the visual and motor cortices of the cat[END_REF].

According to Sholl's methodology, a number n of concentric circles having as center the mass center of the ROI is applied. As the common center of all circles, we consider the root node of the tree structure. More specifically if the first circle has a radius b, the radii of the concentric circle is correspondingly. Based on these circles, a vector that counts the number of tree branching points between any two successive concentric circles is computed. The vector's length is equal to the number n of circles of Sholl's analysis. The element i of the Sholl's vector is computed as follows:

Sholl (i) = the number of branching points existing between the i th circle and (i+1) th circle. ( 1)

For example, the application of Sholl Analysis Fig. 3(b) with radius pixels to the image Fig. 3(a) with dimensions 1150x790 pixels, produces the vector

Sectoring

Analysis. While Sholl's method captures the spatial distribution of branching points radiating out of the tree root, the second method we propose, the Sectoring Analysis, reflects the distribution of branching points based on consecutive clockwise sectors. As a typical ductal tree covers at most one out of the four quadrants of the plane, we focus only on the quadrant that contains all tree nodes. We omit the remaining three quadrant of the plane to avoid zero elements in the final vector. The quadrant, where the tree structure is depicted, is divided into a number of consecutive sectors. The m sectors have as common starting point the root of the ductal tree and each triangular sector covers a part of the plane of a central angle equal to . According to the above partition of the plane, the Sectoring vector counts the number of tree branching points that belong to each sector. The vector's length is equal to the number m of Sectoring analysis. The i th element of the Sectoring vector is computed according to following formula:

Sectoring (i) = the number of branching points existing inside the i th sector. [START_REF] Bullit | Vessel Tortuosity and Brain Malignancy: A Blinded Study[END_REF] An example of the application of Sectoring method using sectors is presented in Fig. 3(c). The resulted vector is

(a) (b) (c) (d)

Combined Method.

The idea of combining the Sholl and Sectoring methods resulted in the third method we propose. According to this approach, we apply both Sholl and Sectoring Analysis to a tree structure. The center of Sholl as well the center of Sectoring Analysis is the root of the ductal tree. The application of the Combined method to an image divides one plane quadrant to a number of cells, where n is the total number of circles of Sholl Analysis and m is the total number of sectors produced by Sectoring Analysis. The vector that reflects the spatial distribution of branching points using the Combined Method is constructed as Fig. 3(d) shows. The i th element of the Combined vector counts the branching points inside the i th cell where the i th cell is the cell produced by the circle of Sholl Analysis and the ( ) sector of Sectoring Analysis. More formally, the i th element of the Combined vector is: Appling the Combined Method to the initial image Fig. 3(a) is presented in Fig. 3(d) and the Combined vector becomes containing a total of elements.

Combined (i) =

Galactogram Characterization

In order to characterize a clinical x-ray galactogram, we perform classification experiments considering two classes: galactograms with no radiological finding and galactograms with radiological findings. Using the above mentioned methods, the problem of galactogram classification is reduced to the problem of classification of the visualized tree structure. We employ the k-nearest neighbor classification scheme, which assigns the test tree to the class that appears most frequently among its neighbors. As the three methods presented above represent the spatial distribution of branching points with a numeric vector, we utilize the cosine similarity metric to retrieve the k closest neighboring tree structures. Given the vectors and b of length t that represent the branching point's distribution of two trees correspondingly, the cosine similarity between them is computed by the following formula:

.

Results

We applied the proposed methodology to a clinical galactogram dataset and we performed similarity search experiments and classification experiments to evaluate the accuracy of our methods. A detailed description of the dataset and the experimental results are presented below.

Dataset

Our dataset consisted of 50 x-ray galactograms performed at Thomas Jefferson University Hospital and the Hospital of the University of Pennsylvania. From these images, 28 corresponded to women with no reported galactographic findings (class NF) and 22 to women with reported galactographic findings (class RF). The ductal trees visualized in the original galactograms were manually extracted and delineated by medical experts.

Similarity Experiments

We applied the proposed methods to the dataset and performed similarity search experiments. In similarity experiments, we considered each tree and its corresponding vector of spatial distribution of branching points as a query and retrieved the k-most similar trees based on the cosine similarity metric. The parameter k ranged from 1 to 5. To evaluate the methodology we reported the precision i.e., the percentage of neighboring images belonging to the same class as the query averaged over the entire dataset. As the two classes in our dataset are unbalanced, we randomly under-sampled the NF class to the size of the RF class and averaged the results over 100 sampling iterations. The following tables illustrate the precision obtained using the Sholl Analysis (Table1), the Sectoring Analysis (Table1), the Combined Method (Table2) and the tree characterization technique presented in [START_REF] Megalooikonomou | A Representation and Classification Scheme for Tree-like Structures in Medical Images: Analyzing the Branching Pattern of Ductal Trees in X-ray Galactograms[END_REF] (Table2). We mention that in the experiments the parameter of Sholl Analysis was equal to 10 pixels, the parameter m of Sectoring Analysis was equal to 16 sectors and the parameters b and m of Combined Method were 10 pixels and 16 sectors correspondingly.

Classification Experiments

Here, we performed leave-one-out k-nearest neighbor classification experiments using the cosine similarity metric. Also in this case, the values of k ranged from 1 to 5 and the NF class was under-sampled to the size of the smaller RF class. To evaluate the classification, we compared the accuracy obtained using the Sholl Analysis (Table3), the Sectoring Analysis (Table3), the Combined Method (Table4) and the state-of-theart Prüfer/tf-idf method presented in [START_REF] Megalooikonomou | A Representation and Classification Scheme for Tree-like Structures in Medical Images: Analyzing the Branching Pattern of Ductal Trees in X-ray Galactograms[END_REF] (Table4). The values of parameter b and m were equal to the values in similarity search experiments.

Conclusion

We presented a new methodology for capturing branching properties of tree-like structures in medical images. Based on Sholl Analysis, we proposed Sectoring Analysis and we combined the two methods to obtain a more detailed analysis of the spatial distribution of branching points. We applied our approach to a dataset of clinical galactograms attempting to correlate the topological features of branching points with the underlying pathology of breast ductal trees. Our experimental results suggest that it is possible to deduce valuable information about the radiological findings from the topology of the ductal trees. Within our future research plans is the fine-tuning of the values of parameters and m, as well as the application of statistical tests in order to check the statistical significance of the results. In addition, the study of other topological descriptors and the combination of all of them is a promising perspective to achieve even higher classification accuracy.

Fig. 1 .

 1 Fig. 1. Characteristic examples of tree shaped structures in medical images: (a) the human airway tree, (b) an angiography visualizing the hindlimb arterial network in a rabbit, (c) the network of human ducts depicted in a galactogram.

Fig. 2 .

 2 Fig. 2. Segmentation of a ductal tree: (a) an original galactogram, (b) the Region Of Interest of the medical image showing enlarged the ductal network, (c) the segmented tree structure manually traced by medical experts.

Fig. 3 .

 3 Fig. 3. Applying three methods to characterize the spatial distribution of tree's branching points: (a) the initial delineated ductal structure, (b) application of Sholl Analysis, (c) employment of Sectoring Analysis, (d) application of Combined Method.

  the number of branching points existing inside the cell generated by the[START_REF] Tschirren | Matching and anatomical labeling of human airway tree[END_REF]

Table 1 .

 1 The obtained precision of similarity searches for Sholl and Sectoring Analysis.

			Precision of Similarity Searches
	k	NF	Sholl Analysis RF	Total	NF	Sectoring Analysis RF	Total
	1	100%	100%	100%	100%	100%	100%
	2	98.44%	74.06%	86.25%	99.06%	78.44%	88.75%
	3	86.04%	65.62%	75.83%	87.29%	57.50%	72.40%
	4	82.34%	65.31%	73.83%	83.13%	55.31%	69.22%
	5	74.00%	60.75%	67.38%	74.00%	55.63%	64.81%

Table 2 .

 2 The obtained precision of similarity searches for Combined and Prüfer/tf-idf methods.

			Precision of Similarity Searches
	k	NF	Combined Method RF	Total	NF	Prüfer/tf-idf method RF	Total
	1	100%	100%	100%	100%		100%	100%
	2	96.25%	86.56%	91.41%	92.94%	74.53%	83.73%
	3	85.21%	68.13%	76.67%	77.67%	66.92%	72.29%
	4	78.91%	65.00%	71.95%	67.72%	66.70%	67.21%
	5	70.13%	61.88%	66.00%	71.16%	60.16%	65.66%

Table 3 .

 3 The obtained classification accuracy using Sholl and Sectoring technique.

			Classification Accuracy
	k	NF	Sholl Analysis RF	Total	NF	Sectoring Analysis RF	Total
	1	95.00%	61.25%	78.13%	93.75%	46.88%	70.31%
	2	96.88%	48.13%	72.50%	98.12%	56.87%	77.50%
	3	69.58%	41.04%	55.31%	73.54%	39.37%	56.46%
	4	73.39%	53.70%	63.54%	74.27%	40.36%	57.32%
	5	66.63%	52.25%	59.44%	65.50%	42.13%	53.81%

Table 4 .

 4 The obtained classification accuracy using Combined and Prüfer/tf-idf methods.

			Classification Accuracy
	k	NF	Combined Method RF	Total	NF	Prüfer/tf-idf method RF	Total
	1	91.87%	70.63%	81.25%	73.61%	53.61%	63.61%
	2	92.50%	73.12%	82.81%	85.88%	49.06%	67.47%
	3	68.75%	49.38%	59.06%	58.73%	50.92%	54.82%
	4	73.59%	52.86%	63.23%	55.56%	56.60%	56.08%
	5	62.87%	51.00%	56.94%	63.56%	50.20%	56.88%

Acknowledgments. This research has been co-financed by the European Union (European Social Fund -ESF) and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) -Research Funding Program: Heracleitus II. Investing in knowledge society through the European Social Fund.


Kolyo Onkov
email: kolyoonkov@yahoo.com

Object Oriented Modelling in Information Systems Based on Related Text Data

Keywords: expert data, natural sciences, key words, text data retrieval, relational database, object oriented modelling, crop protection

Specialized applied fields in natural sciences -medicine, biology, chemistry etc. require building and exploring of information systems based on related text forms (words, phrases). These forms represent expert information and knowledge. The paper discusses the integration of two basic approachesrelational for structuring complex related texts and object oriented for data analysis. This conception is implemented for building of information system "Crop protection" in Bulgaria based on the complex relationships between biological (crops, pests) and chemical (pesticides) terms in textual form. Analogy exists between class objects in biology, chemistry and class objects and instances of object oriented programming. That fact is essential for building flexible models and software for data analysis in the information system. The presented example shows the potential of object oriented modelling to define and resolve complex tasks concerning effective pesticides use.

Introduction

Text is the most common form for presenting expert information and knowledge. Paper guides and reference books using knowledge from natural sciences -medicine, biology, physics, chemistry etc., aim to impose the state rules and regulations in order to keep proofs of decisions made and to share and disseminate the useful information. As being heavily used by specialists it is difficult when the volume of text data is large and there are complex relationships between basic terms in textual form, for example the names of drugs and diseases. The following basic problems arise in the process of transformation text data containing related key words and phrases into intelligent computer based system: a) to retrieve related key words and phrases and to define relationships between them; b) to store text data and relationships in easy accessible database; c) to develop software for database analysis to meet information and knowledge requirements determined by specialists in the applied fields.

This paper reveals one conception for building of information systems based on related text data through integration of two approaches -relational for data structuring and object oriented for data modelling and analysis. This conception is implemented for the development of Bulgarian information system "Crop protection".

The conceptual framework of building and exploring of information system based on related text data is presented in figure 1.

In many cases paper or electronic guides and reference books in pharmacology, veterinary, agronomy etc present knowledge from natural sciences in the form of semi-structured or unstructured text data [START_REF]Bulgarian Ministry of Agriculture: List of the permitted products for plant protection and fertilizers in Bulgaria[END_REF], [14]. The core of these expert texts is a set of contextually related words and phrases (terms in the fields). The retrieval of "key words" and relationships among them is usually done through text mining methods and algorithms [START_REF] Feldman | The text mining handbook. Advanced Approaches in Analyzing Unstructured Data[END_REF], [START_REF] Bramer | Principles of data mining[END_REF], [START_REF] Crowsey | An Evaluation of Unstructured Text Mining Software[END_REF], [START_REF] Mahgoub | A Text Mining Technique Using Association Rules Extraction[END_REF], [START_REF] Mooney | Mining Knowledge from Text Using Information Extraction, Natural language processing and text mining[END_REF]. The process of verification and correction [START_REF] Lopresti | Optical character recognition errors and their effects on natural language processing[END_REF], [START_REF] Onkov | Effect of OCR-errors on the transformation of semi-structured text data into relational database[END_REF] is needed to guarantee storing correct expert data in the database.

Figure 2 presents information model for treatment of subjects which is common for several natural sciences: medicine, biology, chemistry and pharmacology. The relationships between terms (key words, elements of the sets) exist in both sequences: (M 1 _ M 2 _M 3 ) and (M 3 _ M 2 _M 1 ). Coding of key words is applied for building entity-relationships database model [START_REF] Dimova | An algorithm for automated creation of a PC database storing related text objects[END_REF]. Ontology-based extraction and structuring [START_REF] Embley | Ontology-Based Extraction and Structuring of Information from Data-Rich Unstructured Documents[END_REF], conceptual modelling of XML data [START_REF] Necasky | Conceptual Modeling for XML[END_REF] and relational system between two databases [START_REF] Kouno | Development of Relational System between Plant Pathology Database and Pesticide Database[END_REF] are developed for structuring this type of data. Relational software provides easy access to data while object oriented approach is the proper paradigm for building flexible models. The objects classifications in natural sciences are usual form of knowledge presentation. That is additional and important argument for building object oriented software for data analysis.

Object Oriented Modelling in Bulgarian Information System "Crop Protection"

The Bulgarian ministry of agriculture prepares annually a reference book [START_REF]Bulgarian Ministry of Agriculture: List of the permitted products for plant protection and fertilizers in Bulgaria[END_REF] presenting pesticides permitted for use in the country (figure 3). The book content is based on the state laws and knowledge of national experts from the field.

The conception from the previous chapter is applied to transform the reference book into information system "Crop protection". The relationships between basic biological (crops, pests) and chemical (pesticides) terms are implemented. The information model for crop protection (figure 4) consists of three hierarchical structures. The nodes of the model are the sets "Crops", "Pests" and "Pesticides". Each node is built by class objects corresponding to the biological and chemical classification. Each class contains text data related with the text data from other class.

Key words and phrases belonging to different classes and subclasses are extracted from the reference book and coded by natural numbers. Then the codes are used as primary keys of table schemes in the relational database. Figure 5 illustrates data access and visualization through relationships in the sequence "crops-pests (pathogens) -pesticides". The quantitative and qualitative characteristics of each pesticide -active ingredient, dose and minimum lethal dose (LD) are also presented.

Probably the easy access to data is enough for farmers and agronomists, but scientists and experts in biology, chemistry and phytopharmacy usually have to solve more complex tasks which require deep analysis of related text data. The complexity of data analysis descends from the close properties and at the same time variations of subjects from definite class, as well as variations among classes. That is the main reason to create flexible data models by using of object oriented approach. The coding of key words which is corresponding to the subjects from definite class gives opportunity for transition from relational to object oriented data structures. Each class object contains key words field and procedure for implementation of relationships based on their codes. The data models can include two or more related class objects. The process of information extraction, analysis and finally decision making through object oriented modelling has sequential character in spite of the hierarchical subjects' classification of the model (figure 4).

The presented model aims at analyzing similar properties of the objects from definite class objects as well as differences toward treatment of crops against one or more pests. The analysis of these variations supports decision making. The logical sequence "crops-pests-pesticides" is implemented. This model can be applied for each subclass of objects and instances belonging to classes "Crops" and "Pests". Let's present an example. Two crops {"cucumber", "tomato"} are object instances of class objects "Vegetables" while pest {"mildew"} is instance of class objects "Fungi". Table 1 presents the final result of data processingcommon pesticides for treatment the both crops {"cucumber", "tomato"} against {"mildew"}. The modelling based on reverse relationships "pesticides-pests-crops" is useful because of extraction information on available pesticides and variances for their practical use. The object oriented approach provides extending the information model (figure 4), e.g. to add new class objects in hierarchical structures. The model extension can be done in the sense of cognitive and application aims of the IS including biological, geographical and other factors. The flexibility of the model allows the development of application data models focused on different users groups:

• Agronomists and farmers responsible for crop protection measures. Instance level modelling allows working with real data on cultivated crops. The agronomists need to know the variations for the use of different pesticides against identified pests;

• Scientists and experts in the fields of biology, chemistry and phytopharmacy. They would be provoked by the instance level modelling and real data analysis in two directions: research and development of more effective chemicals for crop protection and improvement of the governmental rules, regulations and control mechanisms;

• Specialists who manage pesticides business and related technical and financial resources. The expert analytical information for needed pesticides is important for applying economical models: managing inventories, cost benefit and risk assessment.

The analogy between classes and subclasses in biology and chemistry and class objects and instances of object oriented approach is a base for flexible data modelling. The modern trends and problems coming from the field of crop protection require extending of the models through adding data and new class objects referring to the variations of pest resistance to a pesticide [13], changes in the nature (soil and climatic) etc. The object oriented models can be developed not only on the base of new classes of chemicals, but also by classes of natural products for crop protection. This paper presents a conception for building and exploring of IS based on related text data through integration of two basic approaches -relational for data structuring and object oriented for data analysis. This conception is successfully applied for the creation of Bulgarian information system in the field of crop protection. The potential of the object oriented modelling consists of creating agile models based on related class objects. The developed solution provides working with easy retrieval database, flexible data models and object instances for data analysis. The extracted information will enhance expertise of the specialists and will facilitate decision-making process. Observing specific regulations referring to the pesticides use strategy, it can be concluded that data in the field of crop protection are different in different countries, but the relational database structuring and the software for object oriented modeling will be very similar. In this sense the presented ideas and experience can be useful.

Figure 2 :

 2 Figure 2: Information model for treatment of subjects

Figure 1 :

 1 Figure 1: Conception of building and exploring of information system based on related text objects Users

Figure 4 :Figure 3 :

 43 Figure 4: Information model for crop protection

Figure 5 :

 5 Figure 5: Relational database -data access and visualization

  Let's define: A: subclass of class "Crops"; B: subclass of class "Pests"; C: class objects "Pesticides". The data modelling can be presented as follows: a) Input data: Choose N object instances of A; Choose M object instances of B. b) Apply operations: (A B) C. These two operations indicate a code application for implementing relationships between instances of the defined subclasses A, B and class C. For each instance of A and each instance of B will be found corresponding subset of C. The result is a matrix with NxM sets: D 11 D 12 … D 1M D = ………………… D N1 D N2 … D NMThe set D ij (i=1, 2, … N; j=1, 2, … M) contains pesticides which are proper for use in treatment i -th crop against j -th pest. All sets of the matrix D are subsets of the set C. c) Section (set E) and disjunction (set F) of the chosen sets of the matrix D. Set E shows the common pesticides for treatment of the chosen crops and pests. Set F refers to all pesticides.

Table 1

 1 Common pesticides for treatment "Cucumber" and "Tomato" against "mildew" (set E)

	№	Code Pesticides_Company	Active Ingredient	Dose
	1	23	Bravo 500 Syngenta 500 g/l chlorothalonil	0.3%
				225 g/kg famoxadone +	0.04%
	2	51	Equation DuPont	300 g/kg simoxanile	(40 g/da)
	…	…	…	…	…
	8	196 Champion Nufarm	77% cupric hydroxide	0.15%


Sarra Jlassi
email: sarra.jlassi@mines-paristech.fr

Simon Tamayo

Arthur Gaudron

Arnaud De

L A Fortelle

Simulating impacts of regulatory policies on urban freight: application to the catering setting

Keywords: urban logistics, simulation, regulation, time access restrictions, vehicle weight restrictions. I. Businesses Distributors Demand generation and Customer-Supplier assignments

Regulatory policies aim at reducing the negative effects of urban freight transportation, especially those related to traffic, emissions and noise. Nonetheless, stakeholders in city logistics often have divergent objectives, which lead to difficulties upon defining the best possible choices regarding regulation. This paper presents a multi-agent and discrete-event based simulation of urban deliveries that aims at evaluating the impacts of regulatory policies. Restrictions regarding vehicle weights and time windows are considered in order to measure the impacts on deliveries based on total distances, number of vehicles, loading rates and air pollutant emissions. The simulation framework is applied to the delivery services for restaurants, in which 4 scenarios of regulation are evaluated in the city of Paris. One originality of the proposed approach is to use real data for the instantiation of agents and the GIS in the simulation.

INTRODUCTION

Nowadays urban freight draws a lot of attention due to its costs and environmental impacts. The situation leads to the willingness for the governments, communities, industrial companies and businesses to take action towards a more efficient city logistics. In Europe, freight transit and urban freight transport account for 31 % of the energy use and 31 % of the CO2 emissions in urban areas [START_REF] Herzog | Urban Freight in Developing Cities: SUTP Sourcebook Module 1g[END_REF]. Although delivery vehicles represent only 10% of the traffic in urban zones (expressed in vehicles-kilometres), they are responsible for 20% to 60% of the air pollution and noise created by such traffic [START_REF] Dablanc | Freight transport for development toolkit: Urban freight[END_REF].

In order to improve quality of life in urban areas, cities implement various regulations regarding vehicles (size, weight, load factor and/or engine type) and restrictions of access (restricted areas and/or time windows). Public authorities mostly focus the regulations on trucks as they are considered to be the main cause of slowdowns and traffic congestion particularly during peak hours [START_REF] Castro | Impacts of large truck restrictions in freight carrier operations in metro manila[END_REF].

Numerous initiatives have been carried-out (Bangkok [START_REF]Strategic Urban Transport Policy Directions for Bangkok[END_REF], Seoul [START_REF] Castro | Impacts of large truck restrictions in freight carrier operations in metro manila[END_REF], [START_REF] Smith | Assessing the effects of Trucking Regulation in Korea[END_REF] , NY [START_REF] Jim Labelle | Off-Peak Delivery A Pilot Project for the Chicago Region[END_REF]) in order to shift movements of trucks from peak hours to off-peak hours. The foremost expected impacts relate to congestion, travel time, safety and pollution. NY off-peak deliveries are considered to have saved between $100 and $200 million/year in terms of travel times and pollution reductions [START_REF] Jim Labelle | Off-Peak Delivery A Pilot Project for the Chicago Region[END_REF]. Moreover, other road users perceived an improvement in their quality of life. Pedestrians and cyclist felt safer in the city. Additionally, the project estimated travel time savings of 3 to 5 min per trip for the non-freight travellers and about 48 minutes in travel time per delivery tour and 1 to 3 hours in total service time per delivery tour for freight carriers.

However, industrials, researchers and trade associations have claimed that these type of restrictions can be economically and/or environmentally detrimental (Castro and Kuse [START_REF] Castro | Impacts of large truck restrictions in freight carrier operations in metro manila[END_REF], NEDA [START_REF]The truck ban in Metro Manila's major thoroughfares: A policy analysis[END_REF], Quak and Koster [START_REF] Quak | Delivering Goods in Urban Areas: How to Deal with Urban Policy Restrictions and the Environment[END_REF]). On the one hand, the extra costs generated by the regulation would be paid by urban freight actors (shippers, carriers, etc.), resulting in operational changes and elevated overheads. On the other hand, the difficulty to keep the same level of service while complying with regulations would lead to logistic systems with higher environmental impacts [START_REF]The truck ban in Metro Manila's major thoroughfares: A policy analysis[END_REF]. This conjuncture points out the complexity of city logistics as each stakeholder has a different perspective and regulations have direct and indirect impacts that imply costs and benefits unevenly. As a result, it is particularly difficult to formalize and measure the impacts of regulation actions implemented by public authorities.

A holistic approach to regulation in city logistics seems mandatory. Although the multiplicity of actors and the heterogeneity of information related to urban freight, a formal description of the relations within such system would be hardly obtained. However, simulation appears to be a pertinent approach to study such relations, while avoiding the issue of formally describing the interactions between actors.

After exploring the literature referring to simulation in urban logistics, it was observed that a limited number of publications used real datasets on simulations. To date, there are few simulation works that study the impacts of public regulations in urban logistics [START_REF] Jlassi | Simulation applied to urban logistics: a state of the art[END_REF]. This paper presents a simulation framework of urban deliveries that aims at evaluating the relations between regulatory policies and performance indicators. Restrictions regarding vehicle weights and time windows access are considered in order to simulate deliveries of goods in urban areas. The impacts of each regulation are measured in terms of total distances, emissions, lead-times, fleet sizes and loading rates.

II. PROBLEM STATEMENT

The proposed simulation model aims at evaluating the relations between regulatory policies (vehicle weights and time windows) and performance indicators relevant to professionals and public authorities. Figure 1 presents the different urban entities considered in the proposed approach, as well as their main relationships and interactions. Each of these entities has its own behaviour and it influences the unwinding loop.

In the system, a group of businesses located in an urban area order products from a distributor. The distributor groups the orders, prepares them and then delivers the products with the help of a carrier that performs the deliveries in tours. These tours generate traffic and emissions as they involve a certain number of vehicles on the roads. The residents of the area perceive the effects of these deliveries and the public authorities establish regulations that constrain the organisation of the tours. This paper will focus on the two regulatory policies described in [START_REF] Bhuiyan | Traffic Management in Urban Areas under Freight Regulatory Initiatives[END_REF]:

• Vehicle size restrictions: which consist in banning the circulation in the city of certain types of vehicles based on their size, weight and/or loading factor.

• Time window restrictions: which consist in allowing freight vehicles to travel inside the restricted zones only during specific time windows. For instance, offpeak delivery regulations [START_REF] Jim Labelle | Off-Peak Delivery A Pilot Project for the Chicago Region[END_REF] intend to shift deliveries to the off-peak period.

This paper focuses on the city of Paris, which has undertaken important steps in order to become a "low-emission zone". Since 1991, the city approved acts to reduce the number of trucks entering the city [START_REF] Castro | Impacts of large truck restrictions in freight carrier operations in metro manila[END_REF]. In November 2014, a plan to combat air pollution was been launched. In September 2015, a decree introducing traffic restrictions for freight vehicles carrying more than 3.5 tonnes was issued. In January 2017, Paris became the first area in France to restrict the access to polluting vehicles by using a sticker-based regulation.

Although these measures are driven by the ambition of reducing the environmental impacts of urban freight, the studies of Manila [START_REF]The truck ban in Metro Manila's major thoroughfares: A policy analysis[END_REF], New York [START_REF] Jim Labelle | Off-Peak Delivery A Pilot Project for the Chicago Region[END_REF], and The Netherlands [START_REF] Quak | Delivering Goods in Urban Areas: How to Deal with Urban Policy Restrictions and the Environment[END_REF] revealed that they also yield important influences on the economic actors of the logistic setting. As a result, this research addresses three major questions:

• How can "Vehicle Size" and "Time Period" restrictions be related to measures of emissions, distances and lead times in a particular setting?

• What is the pertinence of replacing "heavy goods vehicles" by "light duty vehicles" in order to reduce emissions?

• What is the pertinence of changing the delivery timewindows in order to reduce the number of vehicles in an urban zone?

III. SIMULATION MODEL Simulation allows understanding how systems behave over time when different parameters and configurations are applied. In the proposed system (cf. figure 1), a simulation can evaluate scenarios in which "what if" questions are considered in order to better understand the behaviour of the system over time.

A. Agent-based and discrete event logic

This paper proposes agent-based and discrete-event simulation model. This choice was based on a thorough literature review on the different simulation approaches applied to urban logistics [START_REF] Jlassi | Simulation applied to urban logistics: a state of the art[END_REF].

On the one hand, discrete-event simulation (DES) is known to be useful for problems that consist of queuing networks [START_REF] Siebers | Discrete-event simulation is dead, long live agent-based simulation![END_REF] and is capable of representing complex stochastic systems [START_REF] Motraghi | Analysis of urban freight by rail using event based simulation[END_REF]. On the other hand, agent-based simulation (ABS) allows the representation of different stakeholders (shipper, transport service provider, carrier and driver) to act as independent decision-makers or behave as single entities [START_REF] Schroeder | Towards a Multi-Agent Logistics and Commercial Transport Model: The Transport Service Provider's View[END_REF], [START_REF] Tamagawa | Evaluating city logistics measures using a multi-agent model[END_REF], and [START_REF] Joubert | Large-Scale Agent-Based Combined Traffic Simulation of Private Cars and Commercial Vehicles[END_REF].

For the purpose of this paper, the idea of using a hybrid simulation model is appealing as it allows combining the advantages of both DES and ABS. The presented simulation model was developed using the Anylogic simulation software, a java-based multi-logic commercial simulation platform that has already proven its capabilities to model and simulate complex systems [START_REF] Fatnassi | Discrete Event Simulation of Loading Unloading Operations in a Specific Intermodal Transportation Context[END_REF].

B. Structure of the model

The proposed simulation model includes different agents (i.e. businesses, distributors, vehicles, etc.) that interact with each other in the same urban zone.

The entry point of the simulation is related to the demand generation, in which businesses generate orders following a given probability distribution. Each order contains information about the distributor (address) and the requested merchandise (type, amount, etc.). If there is more than one distributor, orders are allocated to the closest.

During daytime, businesses place orders to the distributors. The model considers only next day deliveries with a cut-off hour of the distributor set at midnight. Therefore every night, the distributor will optimize the vehicles' tours and the loading layout based on the constraints of each scenario. The carriers will load the vehicles depending on the assignments of the distributor. Finally, the vehicles will perform their deliveries in the city. These values are obtained from the work of Van Heeswijk et al. [START_REF] Van Heeswijk | An agent-based simulation framework to evaluate urban logistics scheme An agentbased simulation framework to evaluate urban logistics schemes[END_REF] and Boer et al. [START_REF] Boer | Comparison of various transport modes on a EU scale with the STREAM database[END_REF], which consider circulation in urban areas for 2020 engine standards. It is to note that the emission factors considered in Table I, are consistent with those given by the HBEFA (Handbook Emission Factors for Road Transport, http://www.hbefa.net/Tools/).

C. Stakeholders and performance indicators

A large number of stakeholders are associated with urban freight transport. The simulation proposed here, intends to evaluate the requirements of 4 stakeholders, namely: freight carriers; residents; distributors and local authorities.

The simulation considers the following objectives for each stakeholder:

• Freight carriers aim at increasing transport profits while ensuring good customer service levels: this is done by reducing the operating costs of vehicles, that are proportional to the travelled times and distances.

• Distributors aim at selling their goods to customers while offering good service levels, particularly in terms of lead-time.

• Residents aim at improving quality of life by reducing emissions of (CO 2 , NO x , SO 2 ). At the same time, they want restaurants and stores selling products at reasonable prices in their urban areas.

• Local authorities are responsible of health and safety of the residents. They aim at reducing emissions and traffic. At the same time, they are accountable for the economic dynamism of cities. As a result, they aim at implementing regulations that can reduce negative impacts, while avoiding elevated operating costs that would lead to higher cost of living.

Six performance indicators have been chosen to evaluate the objectives these stakeholders: It is to note that in this work, special attention is paid to the emissions. Indeed, during the last decade peaks of pollution invade the city of Paris and even all the Ile-de-France region.

D. Hypotheses

In this application three main hypotheses are considered:

1) The service level is assumed to remain constant regardless of the scenario. That is to say, even if a certain regulation is applied, the distributor will adapt its capacity in order to guarantee the same quality level to the final customers. This means that the number of total delivered orders should remain constant and these orders should all respect the nextday delivery lead-time.

2) The fleet size is considered to be variable and it will adapt to the demand. As a result, the distributor will use more vehicles in order to fulfil the customer orders on time. This hypothesis is close to reality, as real fleets are dimensioned with previous knowledge of the consumption, and they can fluctuate on the grounds of subcontracting.

3) Two types of vehicles are considered, and the fleet is considered as homogenous (i.e. only one type of vehicle is composing the entire fleet). The fleet in the model is an average representation of a fleet in reality.

E. Methodology

Data collection is the first step to build the model. Indeed, in order to improve efficiency and provide long term plans it is crucial to have relevant data on what is being moved (type of goods), where (origins and destinations), when (time windows and frequencies) and by what means (transportation modes). A challenge in the freight distribution setting is that competitiveness is intense, and thus, information sharing is often perceived as a potential threat. This induces an important handicap when collecting data. In the proposed framework, the model is built upon a geographic information system (GIS) based on OpenStreetMap, which contains the roads and the addresses of entities.

The second step is the parametric modelling, which consists in defining the appropriate probability distributions of the entities in model. That is, the parameters defining the probabilities for: 1) demand generation (in terms of frequency and quantity); 2) supply-demand assignments and 3) vehicle routing.

Fig. 3. Methodology of the proposed approach

The third step consists in creating the agents and the discrete event logic. In this step are defined the states and transitions for every agent as well as the overall communication rules that define the interactions between them.

The last step is simulation based scenario analysis. This step is used to analyse the impacts of a given evolution in one or more parameters of the system. In the presented case, this consists on evaluating and measuring the impacts of regulatory policies on deliveries based on total distances and emissions.

V. APPLICATION TO THE CATERING SETTING IN PARIS

This section illustrates the proposed framework by considering the deliveries from the Rungis market to a set of Restaurants in the city of Paris. The Rungis International Market is the world's biggest and leading fresh products market. It is located in the southern suburbs of Paris (48.761890, 2.361019), 11 km from the border of the city and 18 km from the centre of the city. Its clients are professionals, distributors and restaurants. The Rungis market starts its operation each day at 1:00 am and ends around 11:00 am. In the presented application, only restaurants will be considered. The client's locations used in this simulation were provided by a geo-referenced customer's database. The total number of clients (restaurants) is 100, that is 0.95 clients per square kilometre. Each restaurant issues an average of 6.5 replenishment orders per week ( [START_REF] Allen | Review of UK Urban Freight Studies[END_REF], [START_REF] Certu | Aménagement des aires de livraison -Guide pour leur quantification, leur localisation et leur dimensionnement[END_REF]). These orders follow a uniform discrete distribution.

The delivery corresponding to every order is expected the next day (AxB). A distributor in the Rungis market, processes the orders, performs the picking operation and then appoints a carrier to deliver the goods.

In our simulation, the orders are sent from the "business" agents (restaurants) to the "distributor" agent in Rungis. At the end of each day, the distributor agent performs an optimization of its deliveries in order to schedule the next day's tours. The optimization problem takes into account the loads of the current orders, the capacities of the available vehicles and the allowed time windows for delivery. The optimization aims at minimising the total distance and it is solved using Jsprit, a java-based open source toolkit for vehicle routing. The next day, the "vehicle" agents deliver the goods to the clients by taking the best-adapted roads to their itineraries using a GIS based on OpenStreetMap. The drop-off time follows a uniform distribution between 10 and 20 minutes per delivery. After finishing its tour each vehicle comes back to Rungis market. Additional delivery tours are done if time allows it. 4 presents a snapshot of the simulation in which the agents "distributor", "business" and "vehicle" can be distinguished". Four scenarios of simulation are hereafter analysed.

A. Scenario 0 -Heavy trucks are authorized in an unconstrained time window

The scenario 0 is used as a reference to study the impacts of the different regulations. In this first experiment, weight restrictions are not considered. Only trucks perform the deliveries. The public authorities do not regulate the timewindow of access. Nevertheless, deliveries must respect the timeslots indicated by the customers. As a matter of fact, in the catering setting, deliveries are completed from 8:00 am to 12:00 am.

B. Scenario 1 -Only light duty vehicles are authorized in an unconstrained time window

This scenario simulates a weight restriction preventing trucks from entering the city. As a result, the trucks are replaced by vans. The time window for delivery remains identical (i.e. deliveries are done from 8:00 am to 12:00 am). Since the vans have a lower payload (1.2 ton against 8 ton), more vehicles will be needed in order to fulfil the customer orders in the same time window.

C. Scenario 2 -Heavy trucks are authorized but the time window is constrained by the public authority

In this scenario, time windows are constrained by the public authority. The deliveries are only allowed between 9:00 am to 11:30 am. Only trucks perform the deliveries.

D. Scenario 3 -Only light vehicles authorized and the time window is constrained

This last scenario combines both regulations: weight restriction and time windows restriction. As a result, vans perform the deliveries, and they are allowed in the city between 9:00 am to 11:30 am.

F. Results

In this practical application 4 experiments were run. Each simulation scenario corresponds to the deliveries of a week of virtual time. It is important to recall that the service level is assumed to remain constant regardless of the scenario. This means that for each case the total delivered amount of goods is equivalent. Additionally, in all scenarios the lead-time of deliveries respects the next-day constraint (i.e. all orders taken today are delivered tomorrow). Consequently, in each scenario, the fleet size adapts in order to carry the goods during the available time-window.

Table II presents the main results of the 4 simulated scenarios. The performance indicator "Driven kilometres per Ton of goods" represents how many kilometres are travelled in order to deliver one ton of goods. Scenario 0 corresponds to the best configuration in terms of "Driven kilometres per Ton of goods", "Kilograms of CO 2 per Ton of goods" and "Milligrams of SO 2 per Ton of goods". Scenario 1 and 2 return the best results in terms of "Grams of NO X per Ton of goods" and represent the second-best solutions in terms of the other emissions.

The time window regulation has a significant impact on the loading rate of the trucks (from 56% to 33%) and consequently on the number of vehicles needed to complete the deliveries (from 9 to 16 trucks). Scenarios 0 and 2 show that if the time for delivery is reduced, the distributor will send partiallyloaded trucks so the delivery tours can end at the requested time. This impact is less significant on Vans (from 95% to 94%), as they have over 6 times less payload capacity than trucks, they are easier to fill even with fewer clients.

As shown in table II, there is significant difference in terms of driven distance between the scenarios S0-S2 and S1-S3, in other words, between trucks and vans. However, this difference is less substantial in the measures related to emissions. Although trucks are capable of carrying more goods, they generate more emissions (see table I) and there tends to be a compensation effect.

Figure 5 presents the results of "Total driven kilometres" (top) and "Driven kilometres per Ton of goods" (bottom) for the four scenarios for a week of simulation time (i.e. 168 hours). Since the model considers a next-day delivery rule (AxB), the first day of the simulation is devoted to orders registration. This explains the evolution of the distance indicators in Figure 5; in which deliveries begin at h=33 (i.e. 9:00 am of the 2 nd day).

Figure 6 presents the results in terms of "Driven kilometres per ton of goods", "Loading rate" and "Number of vehicles" for the four scenarios. Total driven kilometres Fig. 6. Results of distance, number of vehicles and loading rates for the 4 scenarios

Figure 7 presents the "Kilograms of CO 2 per ton of goods", "Grams of NOx per ton of goods" and "Milligrams of SO 2 per ton of goods" for the four scenarios. The proposed model returns very interesting results; however, these are subject to significant assumptions and should be read with attention. One of the limits of the model corresponds to the indicators that were used to estimate the emissions of the two types of vehicles. Despite basing this data on a rigorous study [START_REF] Boer | Comparison of various transport modes on a EU scale with the STREAM database[END_REF], motorisation technologies and environmental standards evolve rapidly and these results may no longer be representative in a short time. It is important to note that the emission factors considered can add a certain bias to the results. Another limit could be the simplification that the model makes of traffic. A matter of fact, this is modelled by assuming an average speed for vehicles in the urban area, but it is clear that such speed should vary according to the hour of the day.

IV. CONCLUSION AND PERSPECTIVES

The results show that in order to deliver a given amount of goods (and while respecting a certain rule of lead time), highcapacity vehicles generate a lower total distance than low capacity vehicles (in both cases all the goods are delivered and all time constraints are respected). Undeniably, to deliver the same amount of goods, fewer high-capacity vehicles are needed.

It has been found that in the catering sector, delivery tours are strongly limited by the allowed time windows. This means that vehicles could carry more goods, but they would not be able to deliver such products in the slots demanded by the customers (generally restaurants request to be delivered in the morning). Actually, if the same simulations were carried out with later deliveries authorized, for example until 6:00 pm, the load rates of the trucks would reach the same levels as those of the vans.

It is important to note that although trucks have a lower filling rate than vans (56% versus 95% in our scenarios S0 and S1), they generate less CO 2 and SO 2 emissions (8.16 km/ton compared to 12.39 km/ton, that is over 3 times less). This is a result of several factors. An important one is the density of clients; which if increased, can reduce the commuting between drop-off points and furthermore allow higher loading rates for the same time window. The current model instantiates 100 restaurants in Paris, that correspond to a very small market share of the 13900 restaurants in the city [START_REF] Apur | L'évolution des commerces à Paris: Inventaire des commerces 2014 et évolutions 2011-2014[END_REF]. In fact, distributors could have greater market shares, implying higher customer densities. Therefore, as the density increases, the performance in terms of total distance and emissions is expected to improve.

The pertinence of "replacing heavy goods vehicles by light duty vehicles in order to reduce emissions" is a paradoxical subject. Undeniably, smaller vehicles generate fewer emissions, but because of their lower capacity, more vehicles are needed and more kilometres are driven in order to deliver the same amount of goods. The simulation considers the scenarios S0 (trucks) and S1 (vans) in order to estimate the impacts of a truck ban. The vans travel over three times more kilometres than the trucks to deliver the same quantity of goods at the same level of service. Although the vans are traveling more kilometres, they produce equivalent emissions. Nonetheless, there is a significant increase in the number of vehicles needed to perform the deliveries (9 against 35), which has a direct influence in traffic. It can be concluded that in this example, replacing trucks by vans does not necessarily reduces emissions but it does increase the vehicles in the city.

The notion of changing the delivery time-windows in order to reduce the number of vehicles in an urban zone has proven to be erroneous for the example considered here. The simulation shows that time restriction will have a stronger effect on heavyduty vehicles. When comparing scenarios 1 and 3, it is revealed that these regulations do not significantly influence the performance of light-duty vehicles. However scenarios 0 and 2 show that time-windows have a substantial impact on heavy- Based on the hypothesis that all the vehicles are fully loaded, in the case of regulations on weight and/or time window, more vehicles will be needed to perform at the same level of service. The new vehicles will entail extra costs that will eventually be paid by the final customers. Moreover, work carried out in [START_REF] Carrabs | An exact approach for the grocery delivery problem in urban areas[END_REF] shows that an extra cost is already being paid by the citizens in terms of negative externalities (e.g. diseases caused by pollution have social and financial costs). As a perspective, the simulation model should take into account social and economy-related metrics (particularly costs, manpower and other externalities).

In conclusion, the simulations carried-out in this study reveal that implementing regulations of vehicle sizes and timewindows increases the number of vehicles entering urban areas and does not necessarily reduce emissions. Nonetheless, the vehicle sizes, average speeds, and other factors should be considered in order to evaluate the effects on traffic. This is still to be investigated much further with appropriate tools. In the future, the simulation model has to be calibrated with real data (specially in terms of demand) from the catering industry in order to grow closer to reality.

Fig. 1 .

 1 Fig. 1. Freight delivery system for the proposed simulation

Fig. 2 .

 2 Fig. 2. Structure of the simulation model Two types of vehicles are considered in this work: light duty vehicles commonly called vans, and heavy goods vehicles commonly called trucks. Table1shows the properties of each type of vehicle:

1 .

 1 Driven kilometres per tons of goods 2. Loading rate of the vehicles entering the city (%) 3. Average delivery time (hr) 4. Emission of NO X (g of NO X / kg of goods) 5. Emission of CO 2 (kg of CO 2 / kg of goods) 6. Emission of SO 2 (mg of SO 2 / kg of goods)

Fig. 4 .

 4 Fig. 4. APPLICATION TO THE CATERING SETTING IN PARIS

Figure

  Figure4presents a snapshot of the simulation in which the agents "distributor", "business" and "vehicle" can be distinguished". Four scenarios of simulation are hereafter analysed.

  Definition of: • Goods, quantities and times • Origins and destinations • Transporters Definition of probability behaviours for: • Demand generation • Supply-demand assignments • Routing Definition of agents and states using: • Collected data and collaborative GIS • Rules of behaviour • Interactions between agents Simulate scenarios in order to:

Fig. 5 .

 5 Fig. 5. Evolution of the distance indicators during the simulated week

Fig. 7 .

 7 Fig. 7. Results of emissions for the 4 scenarios

  8:00-12:00) S1 (Vans 8:00-12:00) S2 (Trucks 9:00-11:30) S3 (Vans 9:00-11:30)Milligrams of SO 2 / Ton of goodsduty vehicles as the number of trucks almost doubles while the performance on emissions is decreased.

  Table 1 shows the properties of each type of vehicle:

TABLE I .

 I MAIN FEATURES OF THE SIMULATED VEHICLES

	Vehicle type	Van	Truck
	Capacity (ton)	1.2	8
	Speed urban area (km/hour)	25	25
	Costs urban area (€/km)	1.35	2.03
	CO2 (g/km)	299.5	943
	SO2 (mg/km)	2.3	7.2
	NOx (g/km)	0.55	3.1

TABLE II .

 II RESULTS OVERVIEW FOR THE 4 SIMULATION SCENARIOS

	Scenario 0
	Trucks
	8:

00 -12:00 Scenario 1 Vans 8:00 -12:00 Scenario 2 Trucks 9:00 -11:30 Scenario 3 Vans 9:00 -11:30

	Driven
	kilometres per	8,16	27,70	12,45	27,96
	Ton of goods
	Grams of NOX
	per Ton of	25,29	15,24	38,60	15,38
	goods
	Kilograms of
	CO2 per Ton	7,69	8,30	11,74	8,37
	of goods
	Milligrams of
	SO2 per Ton	58,74	63,71	89,64	64,30
	of goods
	Loading rate	56%	95%	33%	94%
	Number of vehicles	9	35	16	36

V. ACKNOWLEDGMENTS

This work is supported by ADEME (Agency for the Environment and Energy Management), La Poste Group, Mairie de Paris (Paris City Hall), Pomona Group and RENAULT through the Urban Logistics Chair at MINES ParisTech and by the IDB bank.