Alejandro Gómez-Boix
email: alejandro.gomez-boix@inria.fr

Pierre Laperdrix
email: pierre.laperdrix@inria.fr

Benoit Baudry
email: baudry@kth.se

Hiding in the Crowd: an Analysis of the Effectiveness of Browser Fingerprinting at Large Scale

Keywords: browser fingerprinting, privacy, software diversity

Browser fingerprinting is a stateless technique, which consists in collecting a wide range of data about a device through browser APIs. Past studies have demonstrated that modern devices present so much diversity that fingerprints can be exploited to identify and track users online. With this work, we want to evaluate if browser fingerprinting is still effective at uniquely identifying a large group of users when analyzing millions of fingerprints over a few months.

We analyze 2,067,942 browser fingerprints collected from one of the top 15 French websites. The observations made on this novel dataset shed a new light on the ever-growing browser fingerprinting domain. The key insight is that the percentage of unique fingerprints in this dataset is much lower than what was reported in the past: only 33.6% of fingerprints are unique by opposition to over 80% in previous studies. We show that non-unique fingerprints tend to be fragile. If some features of the fingerprint change, it is very probable that the fingerprint will become unique. We also confirm that the current evolution of web technologies is benefiting users' privacy significantly as the removal of plugins brings down substantively the rate of unique desktop machines.

INTRODUCTION

Web browsers share device-specific information with servers to improve online user experience. When a web browser requests a webpage from a server, by knowing the platform or the screen resolution, the server can adapt its response to take full advantage of the capabilities of each device. In 2010, through the data collected by the Panopticlick website, Eckersley showed that this information is so diverse and stable that it can be used to build what is called a browser fingerprint to track users online [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF]. By collecting information from HTTP headers, JavaScript and installed plugins, he was able to uniquely identify most of the browsers. With the gathered data, Eckersley not only showed that there exists an incredible diversity of devices around the world but he highlighted that this very same diversity could be used as an identification mechanism on the web. Since this study, researchers have looked at new ways to collect even more information [13, 14, 18, 24-26, 32, 34, 36], measure the adoption of these techniques on the Internet [START_REF] Acar | The Web Never Forgets: Persistent Tracking Mechanisms in the Wild[END_REF][START_REF] Acar | FPDetective: dusting the web for fingerprinters[END_REF][START_REF] Englehardt | Online Tracking: A 1-million-site Measurement and Analysis[END_REF][START_REF] Nikiforakis | Cookieless Monster: Exploring the Ecosystem of Web-Based Device Fingerprinting[END_REF], propose defense mechanisms [START_REF] Baumann | Disguised Chromium Browser: Robust Browser, Flash and Canvas Fingerprinting Protection[END_REF]17,[START_REF] Fiore | Countering Browser Fingerprinting Techniques: Constructing a Fake Profile with Google Chrome[END_REF][START_REF] Laperdrix | FPRandom: Randomizing core browser objects to break advanced device fingerprinting techniques[END_REF][START_REF] Laperdrix | Mitigating browser fingerprint tracking: multi-level reconfiguration and diversification[END_REF][START_REF] Nikiforakis | PriVaricator: Deceiving Fingerprinters with Little White Lies[END_REF], and track devices over long periods of time [START_REF] Vastel | FP-STALKER: Tracking Browser Fingerprint Evolutions[END_REF]. In 2016, a study conducted by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] with the AmIUnique website confirmed Eckersley's findings. The authors noted a shift in the most discriminating attributes with the addition of new APIs like Canvas and the progressive removal of browser plugins. They also demonstrated that fingerprinting mobile devices is possible, but with a lower degree of success.

Tracking users with fingerprinting is a reality. If a device presents the slightest difference compared to other ones, it can be identified and followed on different websites. While Panopticlick and AmIUnique proved that tracking is possible, one problem arises when looking at both datasets: their bias. First, both websites are dedicated to fingerprinting, people who visited them are interested in the topic of online tracking. It limits the scope of their studies. Then, looking at the general statistics page of the AmIUnique website from July 2017, we can clearly see a bias as 57% of visitors are on Windows, 15% on Linux, 13% on Mac, 5% on Android and 4% on iOS. The latest statistics from StatCounter for the month of July 2017 reveal that the OS market share is dominated by Android with a percentage around 40%, followed by Windows at 36%, iOS at 13%, Mac at 5% and Linux under 1% [START_REF]Operating System Market Share Worldwide -StatCounter[END_REF]. One can then ponder about the impact of such a big difference on the effectiveness of browser fingerprinting.

In this paper, we investigate whether tracking can be extended to websites that target a broad audience. We analyze 2,067,942 fingerprints collected from one of the top 15 French websites, and we investigate whether browser fingerprinting techniques are still effective in identifying users by collecting the same attributes reported in the literature. Our first two research questions are related to this issue: RQ 1. How uniquely identifiable are the fingerprints in our data? RQ 2. Can non-unique fingerprints become unique if some value changes? The other questions are related to the characteristics of the dataset and the possible impact of the evolution of web technologies: RQ 3. Can the circumstances under which fingerprints are collected affect the obtained results? RQ 4. Does the evolution of web technologies limit the effectiveness of browser fingerprinting? Where previous studies reported having above 80% of unique fingerprints, we obtained a surprising number: 33.6% of unique fingerprints. This gap can be explained by the targeted audience as our study looks at fingerprints collected from the global population and not necessarily biased towards users interested in online privacy. The difference is even more noticeable when looking at the 251,166 fingerprints coming from mobile devices. [START_REF] Fifield | Fingerprinting web users through font metrics[END_REF].5% of them are unique which is in direct contradiction with the 81% that has been observed by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]. These results show another aspect of browser fingerprinting and its tracking capabilities with the current evolution of web technologies. Here, we extend the analyses carried out by Eckersley [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF] and Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] by putting the browser fingerprinting domain under a different light.

Our key contributions are:

• We explore the current state of browser fingerprinting with the analysis of 2,067,942 fingerprints composed of 17 different attributes. We also provide the first large-scale study of JavaScript font probing and we measure its real-life effectiveness. • We show that by collecting these attributes and targeting a much broader audience, browser fingerprinting is not as effective as it was reported in the literature. While previous studies reported having above 80% of unique fingerprints, we obtained 33.6%. • We compare our dataset with the ones from Panopticlick and AmIUnique and we explain in details the numerous differences that can be observed. • We provide a discussion on the future of browser fingerprinting and what these results mean for the domain and for future applications of this technique. The paper is organized as follows. Section 2 introduces our new dataset along with the ones from Panopticlick and AmIUnique. Section 3 analyzes the diversity of browser fingerprints in our data and compares the three datasets by providing detailed statistics to help explain the differences. Section 4 discusses the impact of our results on the domain and we simulate possible technical evolutions to have an insight on future applications of this technique. Finally, Section 5 concludes this paper.

DATASET

This section introduces the three different datasets that form the basis of the comparison in the next section. First, we give a short description of the two available sets of browser fingerprint statistics conducted on a large scale. Then, we describe the attributes collected to form the browser fingerprints analyzed here.

Previous studies

2.1.1 Panopticlick. In 2010, Peter Eckersley launched the Panopticlick website with the goal of collecting device-specific information via a script that runs in the browser [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF]. The script collected values for 10 different web browser features and its execution platform. Features were collected from three different sources: HTTP protocol, JavaScript and Flash API. Eckersley collected 470,161 fingerprints from January 27th to February 15th, 2010. Data obtained by Panopticlick is "representative of the population of Internet users who pay enough attention to privacy" [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF], so in this sense the data is quite biased. In the study performed by Eckersley, the list of fonts (collected through the Flash API) and the list of plugins (collected via JavaScript) were the most distinguishable attributes.

2.1.2 AmIUnique. With the aim of performing an in-depth analysis of web browser fingerprints, the AmIUnique website was launched in November 2014. Collected fingerprints are composed of 17 features (among them, those proposed by Eckersley [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF]). These fingerprints include recent technologies, such as the HTML5 canvas element and the WebGL API. In the study conducted by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF], 118,934 fingerprints collected between November 2014 and February 2015 were analyzed. The authors validated Eckersley's findings with Panopticlick and provided the first extensive analysis of fingerprints collected from mobile devices. Data collected on this website is biased towards users who care about privacy and their digital footprint.

The dataset

The fingerprints used in this study have been collected through a script deployed in collaboration with the b<>com Institute of Research and Technology (IRT) on one of the top 15 French websites (according to the Alexa traffic rank) on two specific web pages: a weather forecast page and a political news page. The script ran for a six month period, from December 7th, 2016 to June 7th, 2017. To be compliant with the European directives 2002/58/CE and 2009/136/CE, and with the French data protection authority (CNIL), only visitors who consented to the use of cookies, and thus the use of fingerprinting techniques, were fingerprinted. When users first connect to one of these two pages, we set up a 6-months long cookie in their browser. This supports the identification of returning visitors.

Compared to the other two detailed studies, the website used to collect this dataset covers a wide range of topics and it is not dedicated to browser fingerprinting. According to the Hawthorne effect [START_REF] Mccarney | The Hawthorne Effect: a randomised, controlled trial[END_REF], if individuals are aware that they are being studied, a type of reaction occurs, in which individuals modify an aspect of their behavior in response to their awareness of being observed. In our case, this means that the fingerprints in this dataset are more representative of those found in the wild, since users are not enticed to play with their browsers to change their configuration and produce different fingerprints.

Fingerprinted attributes.

In order to compare ourselves with previous studies, we rely on the same attributes found in the study conducted by Laperdrix et al. in 2016 [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]. The complete list of attributes is given in the 'Attribute' column of Table 2. However, to reflect recent technological trends, we made the following modifications to our script: List of fonts. Fonts are usually collected through the Flash plugin. With a few lines of code, one can get access to the entire list of fonts installed on the user's system. However, because of security and stability reasons, plugins are being deprecated in modern browsers in favor of a feature-rich HTML5 environment [START_REF] Schuh | Saying Goodbye to Our Old Friend NPAPI[END_REF]. Flash is expected to disappear definitely as Adobe announced the end-of-life of its solution for 2020 [START_REF]Flash & The Future of Interactive Content -Adobe[END_REF]. All major web browsers like Chrome, Firefox, Edge and Safari already block Flash content or have removed support for it. This means that fingerprinting scripts must turn to another mechanism to get access to the list of fonts.

Nikiforakis et al. revealed that it is possible to probe for the existence of fonts through JavaScript [START_REF] Nikiforakis | Cookieless Monster: Exploring the Ecosystem of Web-Based Device Fingerprinting[END_REF]. A script can ask to render a string with a specific font in a div element. If the font is present on the device, the browser will use it. If not, the browser will use what is called a fallback font. By measuring the dimensions of the div element, one can know if the demanded font is used or if the fallback font took its place. The biggest difference between these two gathering methods is that fonts through JavaScript must be checked individually whereas Flash gives all the installed fonts in a single instruction. This means that testing a large number of fonts is time consuming and can delay the loading of a web page. For this reason, we chose to test 66 different fonts, some among the most popular 'web-safe fonts' which are found in most operating systems and other less common ones. Appendix A reports on the complete list of fonts we tested in our script.

Before deploying our script in production, we identified a limitation in how JavaScript font probing operates. We found out that some fonts can have the exact same dimensions as the ones from the fallback font. Figure 1 illustrates this problem. In the example, the two tested fonts are metrically comparable and have the exact same width and height. However, they are not identical as it can be seen in the shapes of some of the letters (especially "e", "a" and "w"). This means that font probing here will report incorrect results if one were to ask Times New Roman on a system with the Tinos font installed (or vice versa). To fix this problem, we measured the dimensions of a div against three font style variants. There are different typefaces that can be used by a web browser with the most popular ones being serif, sans-serif, monospace, cursive and fantasy. We chose the first three and we tested each font against the three of them, resulting in 66 * 3 = 198 different tests. This way, we avoid reporting false negatives as the three fallback fonts have different dimensions.

Canvas. The Canvas API allows for scriptable rendering of 2D shapes and texts in the browser. Discovered by Mowery et al. [START_REF] Mowery | Pixel Perfect: Fingerprinting Canvas in HTML5[END_REF], investigated by Acar et al. [START_REF] Acar | The Web Never Forgets: Persistent Tracking Mechanisms in the Wild[END_REF], and then collected on a large scale by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF], canvas fingerprinting can be used to differentiate devices with pixel precision by rendering a specific picture following a set of instructions. In order to see how far we can go with this technique, we took as a basis the canvas test performed by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] and we made a more complex canvas element by combining new elements of different natures. First, the script asks the browser to render the two following strings: "Yxskaftbud, ge vår WC-zonmö IQ-hjälp" and "Gud hjälpe Zorns mö qvickt få byxa". Both strings are pangrams (a string with all the letters of the alphabet) of the Swedish alphabet. For the first string, we force the browser to use one of its fallback fonts by asking for a font with a fake name. Depending on the OS and the fonts installed on the device, fallback fonts may differ from one user to another. For the second line, the browser is asked to use the Arial font that is common in many operating systems. Then, we ask for additional strings with symbols and emojis. All strings, with the addition of a rectangle are drawn with a specific rotation. A second set of elements is rendered with four mathematical functions: a sine, a cosine and two linear functions. These functions are plotted on a specific interval and using the PI value of the JavaScript Math library as a parameter. The third set of elements consists in drawing a set of ellipsis. These figures are drawn with different colors and with different levels of transparency. Since filters for opacity change among browsers, it creates differences between them. The last element is a centered shadow that overlaps the canvas element. Figure 2 displays an example of a canvas rendering following the instructions of our script. Cookies. Since we only have fingerprints from users who accepted the use of cookies, all fingerprints have the exact same value for this attribute.

Descriptive statistics.

We distinguish two different kinds of fingerprints: those belonging to mobile devices and those belonging to desktop and laptop machines (we will refer to desktop and laptop machines as personal computers). To prevent collecting multiple copies of the same fingerprint from the same user, we store a cookie on the user's device with a unique ID for six months. Among the 2,067,942 fingerprints, the distinction is as follows: 1,816,764 come from personal computers (87.9% of the data), and the rest, 251,190 fingerprints come from mobile devices (12.1% of the data). 1 reports on the distribution of operating systems in both our dataset and the one from the AmIUnique website. Statistics gathered from StatCounter for the month of July 2017 have also been added to give an idea how close they are from the global population. First, by looking at the differences between our newly collected data and AmIUnique, we can see that there is a significant difference in terms of distribution. Notably, we can see a clear bias in the demographic that AmIUnique attracted since the percentage of Linux desktop machines is much higher than the reported by StatCounter. Then, if we compare our numbers with the ones from StatCounter, we can see that we provide a closer representation of the global population as the percentages for both distributions are close to each other.

Table 2 summarizes the essential descriptive statistics of our dataset. The 'Distinct values' column provides the number of different values that we observed for each attribute, while the 'Unique values' column provides the number of values that occurred a single time in our dataset. For example, the Use of local/session storage attribute has no unique values since it is limited to "yes" and "no". Moreover, in our data, all users accepted the use of cookies, so all the fingerprints have "yes" for this attribute. Other attributes can take a high number of values. For example, we observed 6,618 unique values for the list of fonts. In fact, we also know the higher bound for the number of distinct values for this attribute. We perform in total 66 * 3 tests and each one can take the value 'true' or 'false'. These results in 2 66 * 3 possible combinations even if, in practice, many of them will not be found.

ANALYSIS AND COMPARISON

In this section, we first analyze how diverse browser fingerprints are in our dataset. Then, we analyze the level of identifying information of each attribute that makes up the fingerprint. Finally, we compare our dataset with the two available sets of fingerprint statistics, provided by Eckersley in 2010 [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF] and Laperdrix et al. in 2016 [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF].

Browser fingerprint diversity

Our data was collected on a much larger scale than previous studies and targeting a much broader audience, which leads to the RQ 1. How uniquely identifiable are fingerprints in our data? This question aims at determining how diverse the browser fingerprints are in this novel dataset. Using attributes from Table 2, we succeeded in uniquely identifying 33.6% of fingerprints in our dataset. On personal computers, 35.7% of fingerprints are unique while this number is lower on mobile devices with 18.5%. On personal computers, the threat is less important than reported in other studies. On mobile devices, the number is much smaller but the threat comes from elsewhere: closed platforms with integrated tracking applications.

Figure 3 represents the distribution of the anonymity sets. A set represents a group of fingerprints with identical values for all the collected attributes. If a fingerprint is in a set of size 1, it means that this fingerprint is unique and it can be identified. On mobile devices, the percentages of fingerprints belonging to sets of size larger than 50 is around 59%, while on personal computers this percentage is around 8%. It means that the number of devices sharing equal fingerprints on mobile devices is larger than on personal computers. This can be explained by the fact that the software and hardware environments of these devices are much more constrained than on desktop and laptop machines. Users buy very specific models of smartphones that are shared by many. The largest set of mobile devices contains 13,241 fingerprints, while for personal computers it contains 1,394 fingerprints. Low rates of success at uniquely identifying browser fingerprints in our data reveal that, by collecting more than two million browser fingerprints on a commercial website, it is very unlikely that a fingerprint is unique and hence exploitable for tracking. Possibilities for a fingerprint to be unique are three times lower than in the previous datasets collected for research purposes (Panopticlick and AmIUnique).

Unique fingerprints.

There are 46,459 unique fingerprints on mobile devices and 647,741 on personal computers. A fingerprint is unique due to one of the following reasons:

• It has an attribute whose value is only present once in the whole dataset. • The combination of all its attributes is unique in the whole dataset. On mobile devices, 73 % of fingerprints are unique because they contain a unique value, while this percentage is around 35% for personal computers.

While mobile fingerprints tend to be unique because of their unique values, laptop/desktop fingerprints tend to have combinations of values so diverse that they create unique fingerprints. The most distinctive attributes are canvas on mobile devices and plugins on personal computers. Fingerprints with unique canvas values represent 62% of unique fingerprints on mobile devices, while on personal computers, fingerprints with unique combinations of plugins represent 30% of unique fingerprints.

Investigating changes on browser fingerprints.

Over the course of its lifetime, a device exhibits different fingerprints. This comes from the fact web technologies are constantly evolving and thus, web browser components are continually updated. From the operating system to the browser and its components, one single update can change the exhibited browser fingerprint. For instance, a new browser version is directly reflected by a change in the user-agent. A plugin update is noticeable by a change in the list of plugins. When web browsers evolve naturally, changes happen automatically without any user intervention and this affects all users.

Natural evolution of web technologies is not the only reason why fingerprints evolve. There are some parameters that usually are the choice of the users, such as the use of cookies, the presence of the "Do Not Track" header, or the activation of specific plugins. Users are allowed to change these values at anytime. Besides, some attributes such as timezone or fonts are indirectly impacted by a Let us take as an example of a user with a non-unique fingerprint. Running Chrome 55 on Windows 10, the browser displays the following value for the Content language header: fr-FR,fr;q=0.8,en-US;q=0.6,en;q=0.4 For some reason, the user decides to add the Spanish language. The browser then displays the following value:

fr-FR,fr;q=0.8,en-US;q=0.6,en;q=0.4,es;q=0.2 By changing the language settings, does the fingerprint become unique?

In order to answer this type of question and to study how resilient non-unique fingerprints are in the face of evolution, we conducted an experiment. We looked at analyzing the impact made by the user's choice on the uniqueness of their fingerprints. There is a set of attributes whose values cannot be changed such as attributes related to the hardware and software environment on which the browser is running. The Platform attribute is linked to the operating system, while WebGLVendor and WebGLRenderer reveal information about the GPU. Attributes such as User-agent, List of HTTP headers or Content encoding are beyond the control of the user because they are related to the HTTP protocol. However, attributes such as Cookies enabled, Do Not Track, Content language and List of plugins are a direct reflection of the user's choice. Nevertheless, Cookies enabled, Do Not Track, Use of local/session storage are limited to "yes" and "no", so they do not offer a very discriminant information. This leaves the Content language, List of plugins, Available fonts and Timezone under the scope of our analysis.

For the experiment, we chose fingerprints belonging to sets larger than 50 fingerprints. New values were chosen randomly from nonunique fingerprints that had the same operating system and web browser (including versions). This was made to ensure that the new values are consistent with fingerprints that can be found in the wild. This way, we avoid choosing values that are not characteristic of the fingerprint environment. For example, two browsers can have the same language configuration, but the encoding is different depending on the web browser. Example: Windows 8.1, Chrome, fr-FR,fr;q=0.8,en-US;q=0.6,en;q=0.4 Windows 8.1, Firefox, fr-FR,fr;q=0.8,en-US;q=0.5,en;q=0.3 Both browsers are running on the same operating system and have the same language configuration: French/France[fr-FR], French[fr], English/United States[en-US] and English [en]. But, depending on the web browser, the final language headers are different.

Results. The experiment was repeated ten times and results were averaged. Figure 4 represents the distribution of the anonymity sets resulting of randomly changed values for the Content language, List of plugins, Available fonts and Timezone on mobile devices and desktop/laptop machines. First, we can clearly notice an important difference between devices. For desktop/laptop machines, more than 85% of fingerprints turned into unique fingerprints. This is due to the fact that combinations of values tend to be so diverse on personal computers that they make up unique fingerprints. On mobile devices, when changing the Available fonts and the List of plugins, over 80% of fingerprints remained in large sets. These results are explained by the absence of diversity in these attributes on mobile devices. Results are very different for Content language and Timezone: over 60% of fingerprints turned into unique fingerprints. This can be explained by the lack of diversity in these attributes. As most users share the same timezone and languages, a single change on one of these two attributes dramatically increases the likelihood of the fingerprint to become unique.

By looking at the results of the experiment, we can conclude that if one single feature of a fingerprint changes, it is very probable that this fingerprint becomes unique. In the end, desktop/laptop fingerprints tend to be much more fragile than their mobile counterparts.

Comparison of attributes

Mathematical treatment. We used entropy to quantify the level of identifying information in a fingerprint. The higher the entropy is, the more unique and identifiable a fingerprint will be. Let H be the entropy, X a discrete random variable with possible values x 1 ; ...; x n and P(X ) a probability mass function. The entropy follows this equation:

H (X ) = - n i=0 P(x i )loд b P(x i ) (1)
We use the entropy of Shannon where b = 2 and the result is expressed in bits. One bit of entropy reduces by half the probability of an event occurring. In order to compare all three datasets which are of different sizes, we applied the Normalized Shannon's entropy:

H (X ) H M (2)
H M represents the worst case scenario where the entropy is maximum and all values of an attribute are unique (H M = loд 2 (N ) with N being the number of fingerprints in our dataset).

The advantage of this measure is that it does not depend on the size of the anonymity set but on the distribution of probabilities. We are quantifying the quality of our dataset with respect to an attribute uniqueness independently from the number of fingerprints in our database. This way, we can qualitatively compare the datasets despite their different sizes.

Table 3 lists the Shannon's entropy for all attributes from both the Panopticlick and AmIUnique studies, and our dataset. Column 'Entropy' shows the bits of entropy and column 'Norm. ' shows the normalized Shannon's entropy. The last two rows of Table 3 show the worst case scenario where the entropy is maximum (i.e. all the values are unique) and the total number of fingerprints. In the novel dataset analyzed here, the most distinctive attributes are the List of plugins, the Canvas, the User-agent and the Available fonts.

Due to differences in software and hardware architecture between mobile devices and personal computers, we computed entropy values separately. By comparing entropy values between mobile devices and personal computers, we observed three attributes where the difference is significant.

The largest difference is for the List of plugins with a difference of 0.485 for the normalized entropy. It can be explained by the lack of plugins on mobile devices as web browsers on mobile devices take full advantage of functionalities offered by HTML5 and JavaScript. On personal computers, the List of plugins is the most discriminant attribute while it is almost insignificant for mobile devices. We can observe in Table 2 that among 251,166 fingerprints coming from mobile devices, there are only 81 distinct values for plugins. The second significant difference is 0.214 for the Available fonts. Installing fonts on mobile devices is much more restrained than on personal computers. Even if we test a very limited set of fonts through JavaScript compared to what could be collected through Flash, we can see that there is clearly more diversity on personal computers. The last significant difference is for the User-agent attribute, with a difference of 0.182. On mobile devices, the user-agent has the highest entropy value. This is because phone manufacturers include the model of their phone and even sometimes the version of firmware directly in the user-agent as revealed by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF].

Attributes Use of an ad blocker and Use of local/session storage have very low entropy values because their values are either "yes" or "no".

We also tested the impact of compressing a canvas rendering to the JPEG format. It should be noted that the JPEG compression comes directly from the Canvas API and is not applied after collection. Due to the lossy compression, it should come as no surprise that the entropy from JPEG images is lower than the PNG one usually used by canvas fingerprinting tests (from 0.407 to 0.391).

In the study realized by Eckersley [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF], the analysis of browser fingerprints was performed without differentiating between mobile and desktop fingerprints. Later, some researchers conducted studies about browser tracking mechanisms either on desktop machines [START_REF] Acar | The Web Never Forgets: Persistent Tracking Mechanisms in the Wild[END_REF][START_REF] Boda | User Tracking on the Web via Cross-Browser Fingerprinting[END_REF] or on mobile devices [START_REF] Spooren | Mobile Device Fingerprinting Considered Harmful for Risk-based Authentication[END_REF][START_REF] Wu | Efficient Fingerprinting-Based Android Device Identification With Zero-Permission Identifiers[END_REF] but not on both. In 2016, Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] provided the first extensive study about browser fingerprinting on mobile devices, they proved that both kind of devices presented different discriminating attributes. If the analysis of browser fingerprinting is not carried out by differentiating mobile devices from personal computers, results obtained will not be representative of both kinds of devices. In our data, 12.1% of fingerprints belong to mobile devices so mobile fingerprints represent a small part of the entire data. If we take a look at Table 3, entropy values for attributes like List of plugins or Available fonts are largely influenced by the group that contains the majority of fingerprints which, in our case, is the one with personal computers. For future work, it is strongly recommended to differentiate mobile devices from personal computers (laptops and desktop machines) to obtain more accurate results.

Comparison with Panopticlick and AmIunique

In the data collected by Panopticlick, Eckersley observed that 83% of visitors had instantaneously recognizable fingerprints. This number reached 94% for devices with Flash or Java installed. With the AmIUnique website, Laperdrix and colleagues observed that 89.4% of fingerprints from their dataset were unique. Thanks to the high percentages of unique browser fingerprints, browser fingerprinting established itself as an effective stateless tracking technique on the web. However, with our study, we provide an additional layer of understanding in the fingerprinting domain. By having 33.6% of unique fingerprints compared to the 80+% of the other two studies, we show that browser fingerprinting may not be effective at a very large scale and that the targeted audience plays an important role in its effectiveness.

Comparing data size.

When analyzing the percentages of unique fingerprints, the amount of fingerprints is an important element that influences the results. As discussed by Eckersley in [START_REF] Eckersley | How Unique is Your Web Browser?[END_REF], the probability of any fingerprint to be unique in a sample of size N is 1/N . It is clear that probabilities of being unique in our dataset are much lower than the probabilities of being unique in the AmIUnique one.

With the aim of establishing a more equitable comparison, we took some samples with the same number of fingerprints as the AmIUnique data and we then calculated the percentage of unique fingerprints. We perform a comparison with the AmIUnique data because the amount of fingerprints is four times smaller than the one collected by Panopticlick. Because our dataset spans a six month period, we divided the data into six parts, each part containing data for one month. We kept the same proportion between mobile devices and desktop machines as the AmIUnique data, so we randomly took 105,829 desktop/laptop fingerprints and 13,105 mobile fingerprints from each month. Results were averaged.

On average, 56% of personal computers are unique, while 29% of mobile devices are unique. These percentages show that low ratios of unique fingerprints are influenced by the number of fingerprints.

Even so, results obtained on the sample are significantly distant from those obtained by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]. These results show that performing tracking with fingerprinting is possible, yet difficult.

Comparing entropy values.

Comparison with Panopticlick can be established by taking into account only six attributes. We observe that entropy values for our dataset and Panopticlick differ significantly for all attributes, except for the Screen resolution. Entropy values for the Screen resolution attribute hardly change for the three datasets.

Regarding Timezone and Cookies enabled, drops occur in entropy values due to the characteristics of our dataset. As we explained in Section 2, we analyze fingerprints from users who accepted cookies, and most of them live in the same geographic region. The difference in the entropy value for Content language is due to the fact that most users are located in the same geographic region, which implies that most of them share the same language. In fact, 98% of users present the same value for timezone, which corresponds to Central European Time Zone UTC+01:00 and as a direct consequence of this, 97.7% of fingerprints present French as their first language.

The noticeable drop in the entropy values for the Timezone and Content language affects the fingerprint diversity. To a great extent, the lack of diversity in any attribute has a direct impact on the fingerprint diversity. By decreasing the amount of values that an attributes can take, the identifying value of the attribute is reduced and therefore the identifying value of the browser fingerprint decreases. It means that the diversity surface is reduced, which reduces the diversity among the browser fingerprints giving as result less identifiable browser fingerprints.

For the List of plugins, it is still the most discriminating attribute but a gradual decrease can be observed. From Panopticlick to AmI-Unique, a difference of 0.24 is present. From AmIUnique to our dataset, the difference is 0.126 resulting in a decrease of 0.365 from Panopticlick to our data. This gradual decrease in the entropy value for the List of plugins is explained by the absence of plugins on mobile devices and by the removal of plugins from modern browsers. Over time, features have been added in HTML5 to replace plugins as they were considered a source of many security problems. Chrome stopped supporting the old NPAPI plugin architecture on Chrome in 2015 (topic discussed in [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]). Mozilla dropped support in version 52 of the Firefox browser released in March 2017. Safari has never supported plugins, Flash is long discontinued for Android, and MS Edge for Windows 10 does not support most plugins. Anything else reliant on the Netscape Plugin API (NPAPI) is now dropped which means Silverlight, Java and Acrobat are gone [START_REF]Mozilla Developer Network and individual contributors[END_REF].

The difference in the entropy value for Available fonts between Panopticlick and AmIUnique is explained by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]. Half of the fingerprints in the AmIUnique dataset were collected on browsers that do not have the Flash plugin installed or activated. Between AmIUnique and our data, the difference for the entropy value of fonts is 0.117. Even if collecting fonts through JavaScript is not as effective as with Flash, we observe that the entropy of fonts is still high, keeping its place as one of the top distinctive attributes. For the other attributes, we observe that the entropy values for both our dataset and AmIUnique are similar.

DISCUSSION

In this section, we discuss our results along with the potential implications on the browser fingerprinting domain.

The impact of different demographics

In Section 3, we compared our dataset with the two available sets of fingerprint statistics. There are two key elements that can influence the results of this analysis: the targeted audience and the evolution of web technologies. Previous datasets were collected through websites dedicated to browser fingerprint collection. Both websites amiunique.org and panopticlick.eff.org inform users about online fingerprint tracking, so users who visit these websites are aware of online privacy, interested in the topic or might be more cautious than the average web user. Our dataset is much different as it was collected by targeting a general audience through a commercial website. We believe that this difference in the fingerprint collection process is key to explain the differences between datasets, giving rise to RQ 3. Can the circumstances under which fingerprints are collected affect the obtained results?

Web technologies affect browser fingerprinting. The fact that some technologies are no longer used leads to the evolution of fingerprinting techniques. In some cases, it leads to a decrease in the identifying value of certain features, as we noticed in the attributes List of plugins and Available fonts. As a result of the progressive disappearance of plugins, the List of plugins is rapidly losing its identifying value.

In addition to the effects produced by the evolution of technologies, there are some issues resulting from the collection process. Some of them are caused by targeting a specific demographic group. For instance, the market share distribution across the planet is not uniform. According to StatCounter [START_REF]Operating System Market Share Worldwide -StatCounter[END_REF] in 2017, the European mobile market was led by Apple and Samsung, with similar participation percentages above 30%. Although the mobile market in North America is also led by Apple and Samsung, Apple represents about 50% of the market, while Samsung about 24%. If we collect a sample of mobile fingerprints from North America, there is a good chance that the sample will have a greater presence of Apple devices. So, the distribution of some features like the Platform, WebGL Vendor or User-agent will be more representative of Apple devices.

In the end, depending on the website, the use case or the targeted demographic, the results can greatly vary and the effectiveness of browser fingerprinting can change. Moreover, if we were to perform a similar study targeted at different countries, can we expect the same diversity of fingerprints? Do more developed countries have access to a wider range of devices and, as a consequence, present a larger set of fingerprints? Do more educated users have a tendency to specialize and configure more their devices which, as a result, would make their fingerprints more unique? From data that we gathered, it is impossible to answer these questions as we do not collect information beyond what is presented by the user's device. Yet, considering these different facets may be the key to understand the extent to which browser fingerprinting can work for tracking and identification. Its actual effectiveness is much more nuanced that what was reported in the past and it is far from being an answer to a simple yes or no question.

Towards a potential privacy-aware fingerprinting

An arms race is currently developing between users and thirdparties. As people are getting educated on the questions of tracking and privacy on the web, more and more users are installing browser extensions to protect their daily browsing activities. At the end of 2016, 11% of the global Internet population is blocking ads on the web [START_REF]The state of the blocked web -2017 Global Adblock[END_REF]. This represents 615 million devices with an observed 30% growth in a single year. With regards to browser fingerprinting, several browsers already include protection to defend against it.

Pale Moon [START_REF]Pale Moon browser -Version 25[END_REF], Brave [START_REF]Fingerprinting Protection Mode -Brave browser[END_REF] and the Tor Browser [START_REF]The Design and Implementation of the Tor Browser [DRAFT] "Cross-Origin Fingerprinting Unlinkability[END_REF] were the very first ones to add barriers against techniques like Canvas or WebGL fingerprinting. Mozilla is also currently adding its own fingerprinting protection in Firefox [START_REF]Fingerprinting protection in Firefox as part of the Tor Uplift Project -Mozilla Wiki[END_REF] as part of the Tor Uplift program [START_REF]Tor Uplift Project -Mozilla Wiki[END_REF]. With our study, we show that we do not know yet the full extent of what is possible with browser fingerprinting and as so, modern browsers are getting equipped with mitigation techniques that require a lot of development to integrate and maintain. But, Does the evolution of web technologies limit the effectiveness of browser fingerprinting?

In order to answer the RQ 4, we follow the idea proposed by Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF]. The authors simulated the effectiveness of browser fingerprinting against possible technical evolutions. We recreated some of their scenarios on our dataset. Scenario n°1 -The end of browser plugins. Web browsers are evolving to an architecture not based on plugins. Despite the progressive disappearance of plugins, the list of plugins is still the most distinctive attribute for personal computers in our data. A glimpse of the impact of this scenario is observed on mobile devices, although some plugins still remain. To estimate the impact of the disappearance of plugins, we simulate the fact that they are all the same in our dataset, but only on personal computers and thus taking mobile devices as reference. The improvement is significant with a decrease of exactly 19.2% from 35.7% to 16.5%, taking slightly lower value than on mobile devices, which is 18.5%. Disappearance of plugins for personal computers reduces significantly the effectiveness of browser fingerprinting at uniquely identifying users, as we observed first on mobile web browsers. Scenario n°2 -Adherence to the standard HTTP headers. Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] simulated this scenario assuming that the HTTP header fields had the same value for all fingerprints. We followed this idea, and in addition to that, we reduced the identifying information of the user-agent, just by keeping the name and version of the operating system and the web browser. On personal computers, the improvement is moderate with a decrease of 4.7% from 35.7% to 31% in overall uniqueness. However, on mobile fingerprints, we can observe a drop less significant of 2.3% from 18.5% to 16.2%. In the simulation of this scenario, Laperdrix et al. [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] obtained significant results compared with our results. The small drop is due to the low entropy value of the HTTP headers in our data of 0.085 compared with the value obtained by [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF] of 0.249. Another element to consider is that we included a piece of information contained in the user-agent, illustrating that the combination of operating system and web browser still includes some diversity.

Scenario n°3 -The end of JavaScript. By using only features collected through JavaScript (equivalent to remove HTTP features), it is possible to uniquely identify 28.3% of personal computers and 14.3% of mobile devices. By removing all features collected through JavaScript, fingerprint uniqueness drastically drops. On mobile devices, the percentage drops by 14.2% from 18.5% to 4.3%. On personal computers, the drop is abrupt from 35.7% to 0.7%. The improvement in privacy by removing JavaScript is highly visible, but the cost to the ease and comfort of using web services could be overly high.

These findings show that the evolution of web technologies can benefit privacy with a limited impact. While some of them are becoming a reality, others are more improbable.

Yet, it is possible to envision a future where a "privacy-aware" form of fingerprinting is possible, i.e. one that does not enable identification but that can still provide the security benefits touched upon in the literature. First, the W3C has put privacy at the forefront of discussions when designing new APIs. In 2015, Olejnik et al. performed a privacy analysis of the Battery Status API [30]. They found out that the level of charge of the battery could be used as a short-term identifier across websites. Because of this study, this API has been removed from browsers several years after its inclusion [START_REF] Olejnik | Battery Status Not Included: Assessing Privacy in Web Standards[END_REF] and it changed the way new APIs are making their way inside our browsers. A W3C draft has even been written on how to mitigate browser fingerprinting directly in web specifications [START_REF]Mitigating Browser Fingerprinting in Web Specifications -W3C Draft[END_REF]. This shows how important privacy is going forward and we can expect in the future that new APIs will not reveal any identifying information on the user's device. Then, looking at our own dataset, a privacy-aware fingerprinting seems achievable thanks to the low percentages of unique fingerprints we present in this study.

CONCLUSION

In this work, we analyzed 2,067,942 browser fingerprints collected through a script that was launched on one of the top 15 French websites. Our work focuses on determining if fingerprinting is still possible at a large scale. Our findings show that current fingerprinting techniques do not provide effective mechanisms to uniquely identify users belonging to a specific demographic region as 33.6% of collected fingerprints were unique in our dataset. Compared to other large scale studies on browser fingerprinting, this number is two to three times lower. This difference is even larger when only considering mobile devices as 18.5% of mobile fingerprints are unique compared to the 81% from [START_REF] Laperdrix | Beauty and the Beast: Diverting modern web browsers to build unique browser fingerprints[END_REF].

The other key elements from our study are as follows. Personal computers and mobile devices have unique fingerprints that are composed differently. While desktop/laptop fingerprints are unique mostly because of their unique combinations of attributes, mobile devices present attributes that have unique values across our whole dataset. We show that by changing some features of the fingerprint, such as Content language or Timezone, it is very probable that the fingerprint will become unique. We also show that User-agent and HTML5 canvas fingerprinting play an essential role in identifying browsers on mobile devices, meanwhile the List of plugins is the most distinctive elements on personal computers, followed by the HTML5 canvas element. Furthermore, in the absence of the Flash plugin to provide the list of fonts, we used an alternative for collecting fonts through JavaScript. Even if the list of tested fonts is much smaller compared to what could be captured through Flash, collecting fonts through JavaScript still presents some good results to distinguish two devices from each other.

We also discussed some of the elements that can change the effectiveness of browser fingerprinting, such as the targeted demographic and the existing web technologies. Finally, we analyze the impact of current trends in web technologies. We show that the latest changes in fingerprinting techniques have benefited users' privacy significantly, i.e. the end of browser plugins is bringing down substantively the rate of uniqueness among desktop/laptop fingerprints.

Figure 1 :

 1 Figure 1: Difference between Tinos (top) and Times New Roman (bottom).

Figure 2 :

 2 Figure 2: Example of a rendered picture following the canvas fingerprinting test instructions.

Figure 3 :

 3 Figure 3: Comparison of anonymity set sizes between mobile devices and desktop/laptop machines.

Figure 4 :

 4 Figure 4: Anonymity sets resulting of changing values randomly in sets larger than 50 fingerprints on mobile devices (a) and Personal computers (b).

Table 1 :

 1 OS market share distribution.

	OS	Our data	AmIUnique	StatCounter
			Nov'14-Jul'17 [22]	Jul'17 [6]
	Windows	93.5%	63.7%	84%
	MacOS	5.5%	14.9%	11%
	Linux	0.9%	16.9%	1.8%
	Android	72%	55.6%	70%
	iOS	18.8%	42.3%	22%
	Windows Phone	7.6%	<1%	1%

Table

Table 2 :

 2 Browser measurements for the data. change in the environment, such as to a different timezone or adding fonts (fonts can be added intentionally or come as a side effect of installing new software on a device). Which gives rise to the RQ 2. Can non-unique fingerprints become unique if some value changes? and specifically, do non-unique fingerprints become unique if only one value changes?

		Dataset	Mobile devices	Personal computers
	Attribute	Distinct Unique Distinct Unique Distinct Unique
		values	values	values	values	values	values
	User-agent	19,775	8,702	10,949	5,424	8,826	3,278
	Header-accept	24	9	9	2	19	8
	Content encoding	30	8	19	5	25	4
	Content language	2,739	1,313	961	529	2,128	958
	List of plugins	288,740	196,898	81	33	288,715	196,882
	Cookies enabled	1	0	1	0	1	0
	Use of local/session storage	2	0	2	0	2	0
	Timezone	60	16	39	1	58	18
	Screen resolution and color depth 2,971	1,015	434	159	2675	897
	Available fonts	17,372	6,618	94	36	17,326	6,603
	List of HTTP headers	610	229	158	78	491	164
	Platform	32	5	21	2	26	3
	Do Not Track	3	0	3	0	3	0
	Canvas	78,037	65,787	30,884	28,768	47,492	37,194
	WebGL Vendor	27	1	20	2	26	3
	WebGL Renderer	3,691	657	95	10	3,656	661
	Use of an ad blocker	2	0	2	0	2	0

Table 3 :

 3 Shannon's entropy for all attributes from Panopticlick, AmIUnique and our data.

		Panopticlick	AmIUnique	Dataset		Mobile devices	Desktop/laptop machines
	Attribute	Entropy Norm. Entropy Norm. Entropy Norm.	Entropy Norm. Entropy	Norm.
	Platform	-	-	2.310	0.137	1.200	0.057	2.274	0.127	0.489	0.024
	Do Not Track	-	-	0.944	0.056	1.919	0.091	1.102	0.061	1.922	0.092
	Timezone	3.040	0.161	3.338	0.198	0.164	0.008	0.551	0.031	0.096	0.005
	List of plugins	15.400	0.817	11.060	0.656	9.485	0.452	0.206	0.011	10.281	0.494
	Use of local/session storage	-	-	0.405	0.024	0.043	0.002	0.056	0.003	0.042	0.002
	Use of an ad blocker	-	-	0.995	0.059	0.045	0.002	0.067	0.004	0.042	0.002
	WebGL Vendor	-	-	2.141	0.127	2.282	0.109	2.423	0.135	1.820	0.088
	WebGL Renderer	-	-	3.406	0.202	5.541	0.264	4.172	0.233	5.278	0.254
	Available fonts	13.900	0.738	8.379	0.497	6.904	0.329	2.192	0.122	6.967	0.335
	Canvas	-	-	8.278	0.491	8.546	0.407	7.930	0.442	8.043	0.387
	Header Accept	-	-	1.383	0.082	0.729	0.035	0.111	0.006	0.776	0.037
	Content encoding	-	-	1.534	0.091	0.382	0.018	1.168	0.065	0.153	0.007
	Content language	-	-	5.918	0.351	2.716	0.129	2.291	0.128	2.559	0.123
	User-agent	10.000	0.531	9.779	0.580	7.150	0.341	8.740	0.487	6.323	0.304
	Screen resolution	4.830	0.256	4.889	0.290	4.847	0.231	3.603	0.201	4.437	0.213
	List of HTTP headers	-	-	4.198	0.249	1.783	0.085	1.941	0.108	1.521	0.073
	Cookies enabled	0.353	0.019	0.253	0.015	0.000	0.000	0.000	0.000	0.000	0.000
	H M (worst scenario)	18.843		16.860		20.980		17.938		20.793
	Number of FPs	470,161		118,934		2,067,942		251,166		1,816,776

ACKNOWLEDGMENT

We thank the b<>com Institute of Research and Technology (IRT) for their support and we are particularly grateful to Alexandre Garel for his collaboration in setting up the script on the commercial website and collecting the data. This work is partially supported by the CominLabs-PROFILE project and by the Wallenberg Autonomous Systems Program (WASP).

APPENDIX A. LIST OF TESTED FONTS

Andale Mono, AppleGothic, Arial, Arial Black, Arial Hebrew, Arial MT,Arial Narrow, Arial Rounded MT Bold, Arial Unicode MS,


Nicolas Cristal

Benoît Cristal

Optimisation de tournée de véhicule dans un environnement portuaire 1 st Danloup

Keywords: Optimisation, Cplex, AGV

Dans un contexte portuaire, le but du projet de recherche est de prouver l'efficacité d'un système complétement automatisé avec guidage sans infrastructure pour le transfert de conteneurs dans les terminaux portuaires. Le moyen de transfert utilisé est une flotte d'AGV (pour Automotated Guided Vehicles). Le but est l'automatisation des ports, qui est devenue une priorité pour les plus grands acteurs du secteur portuaire contraints de s'adapter à la croissance du volume de containers transportés liée à la globalisation de l'économie mondiale et aux capacités des nouvelles générations de bateaux. La concurrence entre terminaux et la nécessité de réduire les délais de chargement et déchargement des bateaux nécessitent de la part des opérateurs portuaires une augmentation de la productivité globale, une réduction des co ûts d'exploitation tout en garantissant une sécurité maximale. Cet article concerne le verrou scientifique de la gestion automatique et optimisée de la flotte d'AGV. Il s'agit de proposer un routage de la flotte d'AGVs sans blocages qui permette de réaliser des missions soumises régulièrement.

I. INTRODUCTION

Durant les dernières décennies, le commerce à distance s'est très fortement développé. La réduction des coûts de transport, liée à la massification des biens transportés, a engendré une forte augmentation des volumes transportés. En effet, c'est un moyen de transfert adapté aux matières de poids transportées sur de longues distances par des gros navires. Le transport maritime est un moyen de transport à moindre frais ; il est trente fois moins cher que le transport terrestre. L'augmentation du volume à trasnsporter à vue l'augmentation de la taille des navires et, en conséquence, des capacités d'accueil des lieux portuaires pour l'amarrage des navires mais aussi en terme de chargement et/ou déchargement.

L'idée actuelle est de proposer des solutions automatisées de chargement/déchargement des cargos. Ce qui est motivé par le développement de véhicule automatisé sur le marché : les AGV (pour Automotated Intelligent Vehicles) et des conteneurs de taille standard (équivalents 20 ou 40 pieds). Le but est de minimiser le temps opérationnel et de garantir une efficacité de fonctionnement. Ainsi, l'automatisation vise à permettre l'accélération du transfert des conteneurs du navire vers les clients et inversement.

L'article est organisé suivant trois parties. Nous commencerons par décrire le problème étudié. Dans la partie suivante, le problème est formalisé vers une abstraction mathématique. Il en découle les premiers résultats dans la quatrième section. La partie finale est dédiée à la conclusion de cet étude.

II. DESCRIPTION DU PROBL ÈME

Les problèmes de gestion des opérations dans les terminaux à conteneurs est une thématique très importante dans la littérature scientifique en recherche opérationnelle et logistique. Il existe des synthèses de résultats dans les articles suivants : [START_REF] Steenken | Container terminal operation and operations research -a classification and literature review[END_REF]- [START_REF] Vis | Transshipment of containers at a container terminal : An overview[END_REF]. Il existe de nombreux problèmes au sein des activités portuaires. On trouve, par exemple, des études d'allocation de quai aux bateaux, d'ordonnancement des grues de quai, celui de l'allocation de stockage aux conteneurs. . . Notre étude porte sur la problématique de routage des AGV dans une zone portuaire. L'envirronement est constitué de bateaux à décharger, les grues de quai sont en place. L'opérateur d'exploitation du port (Terminal Operating System) donne des ordes de déchargement au fil de l'eau. L'exécution est confiée à un prestataire qui est chargé d'envoyer un véhicule pour transporter les conteneurs de la grue de quai vers un emplacement de stockage et inversement. Nous devons donc gérer une flotte d'AGV pour honorer les ordres rec ¸us. Plus précisement, il faut affecter un AGV à chaque mission et lui trouver une route qui permette l'exécution de la mission dans le temps imparti.

III. FORMALISATION DU PROBL ÈME

A. Moteur d'affectation

Cette couche se base sur un algorithme d'affectation de type glouton, c'est à dire que l'on procède par itérations en faisant des choix localement optimaux, ce qui ne garantit toutefois pas l'optimalité globale de la solution.

Elle fait l'hypothèse que le nombre d'AGVs disponibles en circulation est supérieur ou égal au nombre de missions à réaliser. Si ce n'est pas le cas, la couche agrégation devra limiter le nombre de missions à traiter par la couche macro.

Son principe est le suivant.

Soit M l'ensemble des missions à affecter.

B. Moteur de routage

Cette section décrit le modèle mathématique proposé pour traiter la problématique de routage des AGV vers les emplacements correspondants aux missions auxquelles ils ont été affectés.

1) Topologie: Les AGV peuvent se déplacer en suivant un réseau de transport virtuel, inspiré de l'organisation ferroviaire, défini par des cantons et des carrefours, qui permettent de représenter un graphe dans lequel les AGV évolueront.

a) Cantons (blocks b i , b j ).: Les AGV qui ne sont affectés à aucune mission ne font pas partie de cet ensemble. Leurs positions (dans des cantons longs, puisqu'ils sont stationnés) seront toutefois transmises par le moteur d'affectation au moteur de routage, afin que ce dernier puisse interdire l'utilisation des cantons correspondants. On dénote par B f (forbidden) 3 l'ensemble des cantons qui ne peuvent être utilisés dans la résolution courante.

On dénote par B = {b 1 , b 2 , . . . , b B } = {b i } i∈[[
Chaque mission est donc associée à un lieu de départ correspondant à la position courante de l'AGV au moment où cette mission est transmise. Chaque mission est également associée à un lieu d'arrivée, en fonction de son type (grues de quai ou grues de stock pour les missions de type 1 et 2, cantons pour les missions de type 3). Ces lieux doivent nécessairement être des cantons longs. Dans la topologie générale proposée dans la figure ??, comme nous ne considérons pas les missions de type 3 dans cette étude, il s'agira donc des cantons représentés sur fond vert.

Pour chaque AGV a m ∈ A, on dénotera par s m ∈ B l son canton de départ (source) et par t m ∈ B l son canton d'arrivée.

2) Variables de décision: De manière à pouvoir proposer une formulation linéaire du problème considéré, on introduit un certain nombre de constantes et variables en plus des termes introduits dans la formalisation précédente.

• R est une constante suffisamment grande.

• ω est une constante suffisamment petite.

• X i,j m ∈ B identifie le passage de l'AGV a m du canton b i au canton b j dans cet ordre. X i,j = δ(a m passe de b i à b j ) où la fonction δ(C) est l'indicateur δ(C) = 1 si la condition C est vérifiée, 0 sinon. • Y i m ∈ B identifie le passage de l'AGV a m par le canton b i . Y i m = δ(a m passe par b i ). • Z p m ∈ B identifie le passage de l'AGV a m par le carrefour c p . Z p m = δ(a m passe par c p ). • α i m ∈ N dénote la date d'arrivée de l'avant de l'AGV a m dans le canton b i . • β i m ∈ N dénote la date de sortie de l'avant de l'AGV a m du canton b i . • γ i m ∈ N dénote la date de sortie de l'arrière de l'AGV a m du canton b i . • φ p m ∈ N dénote la date d'arrivée de l'avant de l'AGV a m dans le carrefour c p .
• ψ p m ∈ N dénote la date de sortie de l'avant de l'AGV a m du carrefour c p .

• δ p m ∈ N dénote la date de sortie de l'arrière de l'AGV a m du carrefour c p .

• ε i m ∈ N dénote la durée de stationnement de l'AGV a m dans le canton long b i ∈ B l . • B i m,n ∈ B caractérise l'ordre chronologique de deux AGV s'ils utilisent le même canton b i ∈ B. B i m,n = δ(a m entre dans b i avant a n ). • C p m,n ∈ B caractérise l'ordre chronologique de deux AGV s'ils utilisent le même carrefour c p ∈ C. C p m,n = δ(a m entre dans c p avant a n ).
a) Notes: Utiliser une seule variable pour dénoter la présence d'un AGV dans un canton, ainsi que l'intervalle horaire de sa présence dans celui-ci, implique implicitement qu'un AGV ne pourra pas passer deux fois par le même canton sur son chemin entre son origine et sa destination. Cette particularité est classique pour les types de problèmes apparentés au voyageur de commerce.

Puisque nous utilisons également une seule variable pour dénoter la présence d'un AGV dans un carrefour, ainsi que l'intervalle horaire de sa présence dans celui-ci, un AGV ne pourra pas non plus effectuer de demi-tour pour s'écarter par exemple de la trajectoire d'un autre AGV dont il barrerait la route avant de reprendre son chemin.

3) Contraintes de routage: Cette section détaille les contraintes régissant le déplacement des AGV de leur origine à leur destination. Elle ne permet pas de garantir les contraintes de sécurité qui seront présentées dans la section suivante. a) Pré-calculs.: Les variables de décision X i,j m doivent être nulles si les cantons i et j ne sont pas accessibles entre eux. Les variables X i,i sont trivialement nulles également.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , X i,j m = 0 (1) ∀a m ∈ A, ∀b i ∈ B, X i,i m = 0 (2)
b) Origine et Destination: Chaque AGV doit sortir de son canton de départ. On contraint donc que parmi les variables X i,j m dénotant la sortie de l'AGV a m du canton s m , une et une seule soit non nulle.

∀a m ∈ A, bj ∈ A Bs m X sm,j m = 1 (3)
Par ailleurs, l'AGV considéré ne doit pas revenir dans son canton d'origine.

∀a m ∈ A, bi∈B X i,sm m = 0 (4)
De manière réciproque, chaque AGV doit entrer dans son canton de destination, et ne plus en ressortir.

∀a m ∈ A, bi∈B X i,tm m = 1
(5)

∀a m ∈ A, bj ∈ A Bt m X tm,j m = 0 (6)
c) Note: On pourrait utiliser dans l'équation (5) l'ensemble ← -A B j proposé dans la note en page 2. d) Respect de la topologie: Depuis un canton b i , un AGV a m ne peut se déplacer que vers un seul autre canton b j , à condition que ce dernier soit accessible depuis b i .

∀a m ∈ A, ∀b i ∈ B, bj ∈ A Bi X i,j m ≤ 1 (7)
L'opérateur d'inégalité permet d'autoriser la somme à être nulle. En effet, si l'AGV a m n'entre pas dans le canton b i considéré, toutes les variables X i,j m devront être nulles, ce que permet l'inégalité.

Au contraire, si la somme est égale à 1, c'est que l'AGV a m quitte le canton b i pour se rendre vers un seul autre canton b j .

e) Connexité des parcours des AGVs: Si un AGV a m entre dans un canton b j (sauf le canton de destination t m ), il doit en sortir. Inversement, si cet AGV sort du canton b i (sauf le canton de départ s m ), il doit y être entré.

∀a m ∈ A, ∀b j ∈ B -{s m , t m }, bi∈B X i,j m = b k ∈B X j,k m (8)
La première somme permet de caractériser si l'AGV a m entre dans le canton b j . En effet, lorsque cette somme vaut 1, c'est qu'il existe un canton b i pour lequel X i,j m = 1 : l'AGV passe de b i à b j . La seconde somme indique que l'AGV a m sort de b j .

La contrainte d'égalité permet d'imposer le comportement souhaité.

Au contraire, si l'une des sommes vaut 0, c'est que l'AGV ne passe pas par le canton b j : il ne doit ni y entrer, ni en sortir.

f) Interdiction des demi-tours: Un AGV ne doit pas pouvoir effectuer de demi-tour.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , X i,j m + X j,i m ≤ 1 (9)
g) Note: Cette contrainte agit comme une coupe, et n'est pas nécessaire pour assurer la correction des solutions renvoyées par le solveur dans la mesure où les contraintes de temps interdisent déjà ce phénomène. Cependant, cette équation est susceptible de guider le solveur dans sa résolution de manière plus efficace. Des jeux d'essais devront être menés pour en mesurer l'impact.

∀a m ∈ A, ∀b i ∈ B -{t m }, bj ∈ A Bi X i,j m = Y i m ( 12
)
∀a m ∈ A, ∀b j ∈ B -{s m }, bi∈B X i,j m = Y j m (13)
d) Note: On pourrait utiliser dans l'équation (13) l'ensemble ← -A B j proposé dans la note en page 2. e) Parcours des carrefours: Lorsqu'un AGV passe du canton b i au canton b j , il utilise l'unique carrefour i c j qui les relie.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , X i,j m ≤ Z i c j m (14)
L'inégalité est importante : elle permet d'imposer la valeur de la variable Z

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B j -{s m }, X i,j m = 1 ⇒ β j m = α j m + ε j m + d b ij (15) X i,j m = 1 ⇒ γ j m = β j m + t b ij (16)
Pour linéariser ces relations, nous utilisons cette fois un double encadrement.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B j -{s m }, β j m -α j m -ε j m -d b ij ≤ R • 1 -X ij m α j m + ε j m + d b ij -β j m ≤ R • 1 -X ij m ( 17
)
∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B j -{s m }, γ j m -β j m -t b ij ≤ R • 1 -X ij m β j m + t b ij -γ j m ≤ R • 1 -X ij m (18)
Pour les cantons d'origine, qui n'ont donc pas de canton qui les précède, nous utilisons la durée moyenne de traversée.

∀a m ∈ A, β sm m = α sm m + ε sm m + d b sm (19) ∀a m ∈ A, δ sm m = β sm m + t b sm (
∀a m ∈ A,∀b i ∈ B, ∀b j ∈ A B i , X i,j m = 1 ⇒ α j m = β i m + d c ij ( 22
)
Pour linéariser cette relation, nous utilisons un double encadrement.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , α j m -β i m -d c ij ≤ R • (1 -X i,j m ) β i m + d c ij -α j m ≤ R • (1 -X i,j m ) (23)
Lorsque X i,j m = 1, le double encadrement par 0 permet d'assurer la contrainte de séquencement recherchée. Au contraire, lorsque X i,j m = 0, les inégalités de l'équation (23) sont toujours vérifiées.

d) Intervalles horaires des cantons non utilisés: Les AGV ne passant pas par un canton b i voient leurs intervalles de temps être calés au temps zéro, afin de diminuer le nombre de variables non affectées du modèle mathématique à résoudre. Ainsi, il existe une relation entre les variables Y i m et les intervalles horaires d'occupation des cantons. Nous cherchons à imposer les relations :

∀a m ∈ A, ∀b i ∈ B c , Y i m = 0 ⇒ α i m = 0 (24) ∀a m ∈ A, ∀b i ∈ B l , Y i m = 0 ⇒ α i m = 0 ε i m = 0
∀a m ∈ A, ∀b i ∈ B c , α i m ≤ R • Y i m ( 26
)
∀a m ∈ A, ∀b i ∈ B l , α i m ≤ R • Y i m ε i m ≤ R • Y i m ( 27
)
Dans les contraintes précédentes, R est une constante suffisamment grande, ce qui assure que les inégalités ( 26

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , X i,j m = 1 ⇒ ψ i c j m = φ i c j m + d c ij (28) X i,j m = 1 ⇒ δ i c j m = ψ i c j m + t c ij (29)
Pour linéariser ces relations, nous utilisons un double encadrement.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , ψ i c j m -φ i c j m -d c ij ≤ R • 1 -X ij m φ i c j m + d c ij -ψ i c j m ≤ R • 1 -X ij m (30) δ i c j m -ψ i c j m -t c ij ≤ R • 1 -X ij m ψ i c j m + t c ij -δ i c j m ≤ R • 1 -X ij m (31)
g) Traversée des carrefours: Lors du passage d'un canton b i à un canton b j , l'AGV a m traverse le carrefour i c j . L'intervalle horaire correspondant à la traversée de ce carrefour dépend de sa date de sortie du canton b i . Nous souhaitons imposer la relation suivante :

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , X i,j m = 1 ⇒ φ i c j m = β i m
(32) Pour linéariser cette relation, nous utilisons un double encadrement.

∀a m ∈ A, ∀b i ∈ B, ∀b j ∈ A B i , φ i c j m -β i m ≤ R • (1 -X i,j m ) β i m -φ i c j m ≤ R • (1 -X i,j m ) (33)
h) Intervalle horaire des carrefours non utilisés: Les AGV ne passant pas par un carrefour c p voient leurs intervalles de temps être calés au temps zéro, afin de diminuer le nombre de variables non affectées du modèle mathématique à résoudre. Ainsi, il existe une relation entre les variables Z p m et les intervalles horaires d'occupation des carrefours. Nous cherchons à imposer la relation :

∀a m ∈ A, ∀c p ∈ C, (Z p m = 0) ⇒ φ p m = 0 (34)
Pour cela, nous devons linéariser l'opérateur d'implication afin d'exprimer la relation dans un format compatible avec le solveur utilisé. La variable φ p m étant positive, il suffit d'imposer une simple inégalité pour la forcer à la valeur nulle.

∀a m ∈ A, ∀b i ∈ B c , φ p m ≤ R • Z p m (35)
i) Note: Il devrait être possible de relâcher la contrainte (35) car elle n'est pas nécessaire pour assurer la correction des solutions renvoyées par le solveur. Des jeux d'essais devront être menés pour en mesurer l'impact.

6

∀a m = a n ∈ A, ∀b i ∈ B, B i m,n + B i n,m = 1 (36)
b) Note: Lorsque les AGV considérés n'empruntent pas le canton b i , les variables B i m,n et B i n,m peuvent prendre des valeurs arbitraires sans que cela impacte la correction de la solution générée par le solveur.

c) Occupation des cantons: Si les deux AGV considérés passent par le canton b i , on impose qu'ils utilisent cette ressource à des instants différents à l'aide de la contrainte suivante : g) Occupation des carrefours: Les même considérations que précédemment sont utilisées pour interdire la présence de deux AGV différents dans un même carrefour.

∀a m =a n ∈ A, ∀b i ∈ B, ∀c p ∈ C i γ i m +ω j∈ ← - A B p i X j,i n ≤ α i n + R •   4 -Y i m -Y i n -B i m,n - j∈ A B p i X i,j m   (
∀a m =a n ∈ A, ∀c p ∈ C, δ p m ≤ φ p n + R • 3 -Z p m -Z p n -C p m,n (39)
IV. R ÉSULTATS Différents jeux d'essai ont été créés pour tester la modélisation et vérifier que les contraintes du système sont respectées. Pour cela, deux réseaux simples qui illustrent des problématiques particulières à résoudre ont été créés. Le premier réseau est illustré par la figure 1. Il contient une grue de quai et une grue de stockage. Ce réseau est utilisé par trois jeux d'essai :

• jeu1 : une mission est gérée par un AGV. La mission est un transfert de la grue de quai (haut de la figure) vers la grue de stock (bas de la figure). Il permet de vérifier la capacité du modèle mathématique à fournir des solutions à la problématique du routage. • jeu2a : deux missions sont gérées par deux AGVs. La première mission est un transfert de la grue de quai vers la grue de stock. La deuxième mission est un transfert de la grue de stock vers la grue de quai. Il permet de vérifier la gestion de carrefour et des circulations verticales. • jeu2b : deux missions sont gérées par deux AGVs. Les deux missions sont un transfert de la grue de quai vers la grue de stock. Ces résultats permettent de voir que les contraintes physiques du système sont bien respectées, notamment au niveau des contraintes de sécurité. En effet, il est important que plusieurs AGVs ne peuvent pas se trouver dans le même canton ou carrefour au même moment. Ils permettent également de mettre en évidence la limite de résolution optimale rapidement atteinte par le solveur. A partir de quatre AGVs, le solveur n'est plus en mesure de trouver la solution optimale. Il faut cependant noter qu'une solution (non optimale) est tout de même trouvée par celui-ci en moins d'une seconde pur le jeu3. Malheureusement, le constat est que ce modèle souffre du passage à l'échelle. Les travaux à venir visent à contourner ce problème. Deux pistes sont poursuivies actuellement. La première consiste à proposer des heuristiques spécifiques ; l'intérêt reside dans l'obtention rapide d'une solution. Une autre piste consiste à affiner le modèle mathématique pour tenter de faire chuter la combinatoire.

4 )

 4 Variables auxiliaires Y et Z: Afin de pouvoir formuler plus facilement les contraintes de sécurité, nous définissions un ensemble de variables auxiliaires permettant d'en simplifier l'expression. a) Origine et destination: Les AGV doivent respecter les cantons de départ et d'arrivée qui leur sont affectés. ∀m ∈ A, Y sm m = 1 (10) ∀m ∈ A, Y tm m = 1 (11) b) Note: Ces contraintes sont redondantes puisqu'elles découlent des équations (3) et (5) et de celles du paragraphe suivant. En effet, l'AGV est toujours sur son parcours dans un canton de départ ou d'arrivée. Ainsi, il est toujours utile de fixer les variables dont on connait a priori la valeur dans un modèle mathématique. c) Parcours des cantons: De manière évidente, lorsqu'un AGV a m sort du canton b i pour entrer dans le canton b j (c'està-dire lorsque X i,j m = 1), il passe par b i et b j . Inversement, si l'AGV a m passe par b i , il doit y entrer et en sortir.

i c j m vaut 1 .

 1 i c j m lorsque X i,j m vaut 1, mais de ne pas imposer réciproquement le passage du canton b i au canton b j lorsque Z En effet, le carrefour i c j peut également être un point de raccordement entre deux autres cantons b k et b l différents de b i et b j , dans le cas de structures de carrefours en étoile par exemple. Dans ce cas, i c j représente le même carrefour que k c l . 5) Intervalles horaires d'occupation des cantons et carrefours: Nous introduisons dans cette section des contraintes permettant de définir les intervalles horaires de présence des AGV dans chacun de ces emplacements. Une fois ces intervalles de temps connu, il sera possible d'imposer les contraintes de sécurité permettant d'interdire à deux AGV de se trouver dans le même canton ou carrefour au même moment. a) Intervalle horaire d'occupation d'un canton: On rappelle que l'intervalle horaire d'occupation d'un canton b i par un AGV a m est dénoté par [α i m , γ i m ], où les bornes temporelles sont exprimées en secondes, à partir du temps zéro correspondant à la date de réception des missions par la couche macro. Celles-ci sont contraintes par la durée de traversée nominale d b i j et la durée de sortie du canton considéré en fonction du canton traversé précédemment.

  20) b) Origine: Les AGVs occupent leur canton d'origine dès le temps zéro. Le début de l'intervalle d'occupation de ces cantons doit donc être initialisé à zéro. ∀a m ∈ A, α sm m = 0 (21) c) Succession de cantons: Lorsqu'un AGV a m passe d'un canton b i à un canton b j , les intervalles horaires d'occupation des cantons b i et b j doivent se succéder, en prenant en compte la durée d c ij de traversée du carrefour i c j . Nous cherchons à imposer la relation :

  cela, nous devons linéariser l'opérateur d'implication afin d'exprimer la relation dans un format compatible avec le solveur utilisé. Les variables α i m et ε i m étant positives, il suffit d'imposer une simple inégalité pour les forcer à la valeur nulle.

  ) et (27) sont toujours vérifiées lorsque Y i m = 1. Au contraire, lorsque Y i m = 0, les variables α i m et ε i m sont contraintes à devenir nulles par un double encadrement par 0. e) Note: Il devrait être possible de relâcher les contraintes (26) et (27) car elles ne sont pas nécessaires pour assurer la correction des solutions renvoyées par le solveur. Des jeux d'essais devront être menés pour en mesurer l'impact. f) Intervalle horaire d'occupation d'un carrefour: On rappelle que l'intervalle horaire d'occupation d'un carrefour c p par un AGV a m est dénoté par [φ p m , δ p m ], où les bornes temporelles sont exprimées en secondes, à partir du temps zéro correspondant à la date de réception des missions par la couche macro. Celles-ci sont contraintes par la durée de traversée nominale d c ij et par la durée de sortie t c ij du carrefour i c j considéré en fonction du canton traversé précédemment et du canton de destination.

  37) L'équation (36) implique que si deux AGV a m et a n sont affectés au même canton b i , et que l'AGV a m se dirige vers le carrefour c p , le terme 4 -Y i m -Y i n -B i m,n -j∈ A B p i X i,j mest nul. Dans le cas où l'AGV a n se dirige également vers le carrefour c p , l'équation (37) implique ainsi que γ i m ≤ α i n et donc que l'AGV a m quitte le canton b i avant l'arrivée de l'AGV a n dans ce même canton. Dans le cas où l'AGV a n ne se dirige pas vers le carrefour c p , l'équation (37) implique que γ i m < α i n . L'ingélaité stricte dans ce cas empêche deux AGV de se croiser entre un carrefour et un canton (ce qui n'est pas possible). Si le terme est strictement positif (parce que l'un ou l'autre des AGV ne passe pas par le canton b i , ou parce que a m est séquencé après a n quand B i m,n = 0), la contrainte (37) est trivialement vérifiée compte tenu de la grande valeur de la constante R.d) Note: Il est connu que la valeur de R a un impact sur les performances du solveur utilisé. Des jeux d'essais devront être menés pour le mesurer. La valeur de ω a également un impact sur les performances du solveur. Une valeur trop petite peut fournir des solutions non réalisables, tandis qu'une valeur trop grande peut amener le solveur a écarter des bonnes solutions.e) Ordre d'occupation des carrefours: L'ordre d'occupation du carrefour c p par les AGV a m et a n est caractérisé par les variables C p m,n (qui vaut 1 lorsque a m se présente avant a n ) et C p n,m (inversement). Un des AGV doit obligatoirement être ordonnancé avant l'autre, ce qui s'exprime par la contrainte suivante :∀a m = a n ∈ A, ∀c p ∈ C, C p m,n + C p n,m = 1(38)f) Note: Lorsque les AGV considérés n'empruntent pas le carrefour c p , les variables C p m,n et C p n,m peuvent prendre des valeurs arbitraires sans que cela impacte la correction de la solution générée par le solveur.

Fig. 1 .

 1 Fig. 1. Topologie du premier réseau Le deuxième réseau est illustré par la figure 2. Il contient deux grues de quai et trois grues de stocks. Ce réseau est utilisé par un seul jeu d'essai (jeu3). Dans ce jeu, quatre missions sont gérées par quatre AGVs. Les détails des missions sont décrites

Fig. 2 .

 2 Fig. 2. Topologie du deuxième réseau

  la gestion d'une flotte d'AGV dans un envirronement portuaire. Lorsqu'un ordre de transport arrive des autorités portuaires (TOS), il convient de trouver une solution pour transporter le conteneur de son origine vers son lieu de stockage. C'est un problème classique de routage d'une flotte de véhicule. Il constitue un problème complexe et ouvert s'incrivant dans les problèmes d'optimisation combinatoire. Il s'agit de trouver les routes pour chaque mission et de respecter les contraintes horaires proposées. Le modèle proposé résout et optimise le flux de véhicule à partir d'une position initiale quelconque.

  + exprimées en secondes. De plus, chaque paire de cantons (b i , b j ) ∈ B × A B i est associé à la durée de parcours nominale de j lorsque l'AGV vient de i dénotée par d b ij ∈ N + , et une durée de sortie de j dénotée par t b ij ∈ N + exprimées en secondes. L'ensemble B est partitionné en cantons courts B c et longs B l tels que B = B c ∪ B l . On dénote B c et B l leurs cardinaux respectifs. b) Carrefours (crossroads c p ).: On dénote par C = {c 1 , c 2 , . . . , c C } = {c p } p∈[[1,C]] l'ensemble des cantons du système étudié. On note C son cardinal. D'après nos hypothèses, pour chaque paire de cantons (b i , b j ) ∈ B× A B i , une durée de parcours dénotée d c ij ∈ N + , et une durée de sortie dénotée t c ij ∈ N + , exprimées en secondes, sont associées à la traversée du carrefour lorsque l'AGV va du canton b i au canton b j . c) Relations entre cantons et carrefours.: La topologie considérée correspond à un enchaînement de cantons et carrefours, sous la forme d'un graphe biparti 1 .Pour tout canton b i ∈ B, on dénote par C i l'ensemble des carrefours accessibles 2 depuis b i .Pour tout canton b i ∈ B, on dénote par A B i l'ensemble des cantons accessibles depuis b i . A B i , il existe un unique carrefour c p tel que b j ∈ A B p i . On dénote cet unique carrefour entre les cantons b i et b j par l'expression i c j .

	d) Note.: Il pourrait être intéressant de définir également l'ensemble ← -A B j caractérisant les cantons depuis lesquels un
	AGV peut venir lorsqu'il entre dans le canton b j .
	Pour tout canton b i ∈ B, et tout carrefour c p ∈ C i accessible depuis ce canton, on dénote par A B p i l'ensemble des cantons accessibles depuis b i en passant par le carrefour c p , et ← -A B p j
	l'ensemble des cantons depuis lesquels un AGV peut venir
	lorsqu'il entre dans b j en passant par le carrefour p.
	La topologie est telle qu'il ne peut y avoir qu'un unique
	carrefour entre deux cantons accessibles entre-eux. Autrement
	dit, on ne peut passer d'un canton à un autre que par au plus
	un seul carrefour.
	Formellement, pour tout canton b i ∈ B, et tout canton
	b j ∈ Il faut noter que l'existence d'un carrefour i c j n'implique
	pas obligatoirement l'existence d'un carrefour j c i dans l'autre
	sens, compte-tenu de notre remarque précédente, puisque
	certains cantons ne peuvent être parcourus que dans un seul
	sens.
	e) Missions (AGV a m , a n ).: Nous faisons l'hypothèse
	que le moteur d'affectation a affecté à chaque mission un
	AGV. Nous unifions donc dans notre modélisation les vocab-
	ulaires de mission et d'AGV.
	On dénote par A = {a 1 , a 2 , . . . , a A } = {a m } m∈[[1,A]]
	l'ensemble des AGV du système étudié. On note A son
	cardinal.

1,B]] l'ensemble des cantons du système étudié. On note B son cardinal. D'après nos hypothèses, chaque canton b i ∈ B est associé à une durée de parcours nominale moyenne dénotée par d b i ∈ N + , et une durée moyenne de sortie dénotée par t b i ∈ N

  ) Contraintes de sécurité: Les contraintes de sécurité permettent d'interdire à deux AGV d'être présents au même moment dans le même canton ou le même carrefour. Pour les exprimer, nous utilisons les intervalles horaires définis précédemment, ainsi que des variables de séquencement permettant d'indiquer dans quel ordre deux AGV empruntant la même ressource doivent la réserver. du canton b i par les AGV a m et a n est caractérisé par les variables B i m,n (qui vaut 1 lorsque a m se présente avant a n ) et B i n,m (inversement). Un des AGV doit obligatoirement être ordonnancé avant l'autre, ce qui s'exprime par la contrainte suivante :

	a) Ordre	d'occupation	des	cantons:	L'ordre
	d'occupation

Il ne peut y avoir deux cantons successifs qui ne soient pas reliés par un carrefour et inversement.

Si l'on considère un canton b i qui ne puisse être parcouru que dans un seul sens, le carrefour en amont de ce canton ne sera pas considéré comme accessible.