typically associated with one P2P overlay network connecting the users. This significantly enhances the user experience by relieving the source from dealing with all connections. Yet, the joining process resulting in a peer to be integrated in channel overlay usually requires a significant amount of time. As a consequence, switching from one channel to another is far to be as fast as in IPTV solutions provided by telco operators. In this paper, we tackle the issue of efficient channel switching in P2P IPTV system. This is to the best of our knowledge the first study on this topic. First, we conducted and analyzed a set of measurements of one of the most popular P2P systems (PPlive). These measurements reveal that the set of contacts that a joining peer receives from central server are of the utmost importance in the start-up process. On those neigbors, depends the speed to acquire the first video frames to play. We then formulate the switching problem, and propose a simple distributed algorithm, as an illustration of the concept, which aims at leveraging the presence of peers in the network to fasten the switch process. The principle is that each peer maintains as neighbors peers involved in other channels, providing peers with good contacts upon channel switching. Finally, simulations show that our approach leads to substantial improvements on the channel switching time. As our algorithmic solution does not have any prerequisite on the overlays, it appears to be an appealing add-on for existing P2P IPTV systems.

Key-words: IPTV, Peer-to-Peer video streaming, network measurements, channel switching

Surf sur IPTV pair-à-pair: Changement De Chaine En Distribué

Résumé : Il est maintenant courant pour les systèmes d'IPTV qui attirent des millions d'utilisateurs d'être basés sur des architectures pair-à-pair (P2P). Dans ces systèmes, à chaque chaîne est associée un réseau logique connectant les utilisateurs. Cela améliore significativement le rendu, en soulageant la source de la gestion de toutes les connexions client. Pourtant, la procédure d'arrivée d'un pair dans le réseau requière habituellement un temps substantiel. Une conséquence directe est que le changement de chaîne pour un pair est loin d'être aussi rapide que dans les solutions IPTV proposées par les opérateurs de télécommunications. Dans cet article, nous nous attaquons au problème du changement efficace dans les systèmes IPTV en pair-à-pair. Il s'agit, à notre connaissance, de la première étude sur le sujet. Tout d'abord, nous avons conduit et analysé un ensemble de mesures sur l'un des systèmes pair-à-pair les plus populaires (PPlive). Ces mesures révèlent que l'ensemble de contacts qu'un pair reçoit du serveur central en rejoignant un réseau est de la plus haute importance pour le lancement de l'application. De ces contacts dépend en effet la rapidité avec laquelle les premières images apparaîtront à l'écran. Nous formulons ensuite le problème du changement de chaîne, et proposons un algorithme distribué, comme illustration du concept; celui-ci a pour but de tirer parti de la présence des pairs dans un réseau pour accélérer la procédure de changement. Le principe est que chaque pair maintienne comme voisins des pairs impliqués dans d'autres chaînes, fournissant ainsi de bons contacts à un pair désirant changer de chaîne. Enfin, nos simulations montrent que l'approche conduit à de substantielles améliorations de ce temps de changement. Comme notre solution algorithmique ne comporte pas de pré-requis sur les réseaux logiques, elle constitue un ajout attractif pour les systèmes d'IPTV en pair-à-pair déjà existants.

Mots-clés :

IPTV, changement de chaîne, flux vidéo pair-à-pair, mesures réseau

Introduction

The diffusion of television over Internet, known as IPTV, has fostered a huge amount of works. Among the most studied architectures, P2P systems have produced not only theoretical proposals (see [START_REF] Sentinelli | Will IPTV Ride the Peer-to-Peer Stream[END_REF] for an overview of the main theoretical challenges) but also practical applications used by millions of users [1, 2, 3]. For instance, the number of visitors of PPlive [1] website reached 50 millions for the opening celebration of Olympics [START_REF]of China Internet[END_REF] while the dedicated Olympic channel attracted 221 millions of users in only two weeks. However, these implementations do not provide efficient channel switching features, while this is well-known as a natural TV watcher behavior. Typically, the time interval from when one new channel is selected until actual playback starts on the screen can be very prohibitively long in current P2P streaming systems. More specifically, the only work that has, to the best of our knowledge, evaluated this start-up delay reports that it requires from 10 to 20 seconds to switch to a popular channel and up to 2 minutes for less popular channels [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF]. Should these recent measurements highlighting the high frequency of switching in IPTV system be confirmed [START_REF] Cha | Watching television over an ip network[END_REF][START_REF] Cha | On next-generation telco-managed p2p tv architectures[END_REF], this could be a burden for the success of P2P IPTV systems.

In multicast-based IPTV (networks controlled by telco operators), a set of solutions has been designed to reduce the start-up delay [START_REF] Cho | Improvement of channel zapping time in iptv services using the adjacent groups join-leave method[END_REF] upon channel switching. They mostly consist in sending data of some adjacent channels along with the current channel data. Two channels C 1 and C 2 are called adjacent if when a user watches C 1 , if (s)he switches channels, the probability that C 2 is chosen is high. For example, it has been shown that a user watching a sport channel, has a high probability to switch to another sport channel. Thus, should the user switch from a channel to one in the adjacent channel set, the corresponding multicast traffic is received without suffering from any network delay. Several works have extended this technique in order to maximize the probability that the target channels are within the set of adjacent channels [START_REF] Lee | Advanced scheme to reduce iptv channel zapping time[END_REF][START_REF] Cha | Channel selection problem in live iptv systems[END_REF][START_REF] Lee | An effective channel control algorithm for integrated iptv services over docsis catv networks[END_REF].

Yet, in P2P IPTV systems, receiving simultaneously several multimedia flows, even degraded, remains too expensive (important overhead of applicative multicast over IP, compared to lower layer multicast). However, users switching patterns being similar, we leverage the fact that switching channels mostly involve adjacent channels. In this paper, we make an initial step to analyze and solve the channel switching issue in P2P IPTV with a simple approach that could be potentially implemented over all existing P2P systems. Our contributions are threefold.

First, in an attempt to characterize the criticity of joining a new channel for the playback delay, we measure and analyze the PPlive system [1] focusing on the so-called bootstrap time: the time between the reception of the P2P contacts, a peerlist (a list of supposedly active peers given by a central server for a given channel) and the time at which the first video packet is received. A joining peer is expected to be able to discover new peers from this initial contact lists through request propagation. However, our measures show that in PPlive, most of the initial video content is actually provided by those contacts given by the server. Our study demonstrates their importance as well as shows that the ratio of peers effectively active in the peerlist is particularly low.

Second, we define the distributed channel switching problem and describe a simple yet efficient solution in which a peer watching a given channel also keeps some links to few peers in specific channels, typically adjacent channels. The peers with which a peer exchanges video content related with its channel are called overlay neighbors. The peers maintained from other channels are called contact peers. When a peer x has a contact peer in the channel c, we say that x is a switcher for c. Obviously a peer cannot be a switcher for all channels as the traffic generated for the maintaining of contact peers can not be neglected. Instead, peers may leverage their overlay neighbors to find switchers for more channels. Our goal is to ensure that, in a given overlay neighborhood, the number of adjacent channels covered by switchers is maximized. We show that an implementation solution of the switching responsibility distribution over a given overlay network is closely related with a (r, k)-configuration problem [START_REF] Haynes | Fundamentals of domination graphs[END_REF], a NPhard problem. From a theoretical side, no exact solution can be computed in a reasonable time, even if one could have a global view of the system. Therefore, we provide a practical solution approximating the optimal solution. Our algorithm is simple, local, efficient and able to cope with dynamic behavior of P2P systems.

Although, this algorithm has been designed for channel switching, its applicability goes beyond. More generally, the problem addressed in this paper consists of switching from a highly connected clusters of peers to another highly connected clusters within a giant overlay network. Typically, switching from one chapter to another chapter in a P2P VoD streaming system admits a very close problem formulation, and solutions are unsurprisingly related with prefetching of most probable seeking positions [START_REF] Zheng | Distributed prefetching scheme for random seek support in peer-to-peer streaming applications[END_REF][START_REF] He | Optimal prefetching scheme in p2p vod applications with guided seeks[END_REF].

Finally, we provide a comprehensive set of simulations. Actually, it is difficult to compare our proposal to other existing implemented solutions because, to the best of our knowledge, only centralized algorithms are used by current systems. Yet, we show that our proposal significantly improves the quality of peers that are given to a joining peer in a channel, and then time for this peer to get stabilized in that new channel.

To sum up, the main contributions are the following: (i) we measure and analyze the bootstrapping process of PPlive, motivating the need for a faster process; (ii) we formulate the problem associated with distributed channel switching, and (iii) we propose and simulate a greedy algorithm to the distributed channel switching problem.

The rest of this paper is organized as follows. Section 2 details our measurements of start-up delays of PPlive. Section 3 formulates the channel switching problem. Section 4 presents our algorithm proposal. Section 5 reports simulation results, and Section 6 finally concludes the paper.

On the importance of given peer sets in PPlive

To understand the bootstrap process, and assess its importance for current popular P2P streaming systems, we conducted a measurement study of PPlive in July and August 2008. Application source code is not provided by PPlive, justifying a reverse-engineering by practical measurements (active crawling and passive sniffing [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF]), to understand this critical phase. We focus on the bootstrapping procedure, i.e. the first two minutes of connections. Depending on channel popularity estimated by the PPlive website, we define five classes of channels: from 1-star popularity grade (the less popular channels) to 5-star popularity grade. In most of experiments (more than 95%), the residential peer 1 (first 4 columns). We focus here on the overlay neighbors providing at least one video packet during the first two minutes. These peers are known either through the initial peerlist, or through subsequent requests from the joining peers to their neighbors. We observe that the ratio of peers that belong to the initial peerlist and actually send eventually a packet (second column) is low. This shows the low quality of peers provided through the bootstrap process. Less than 17% of peers that have been provided by servers for the bootstrap are delivering video content. For the less popular channels, this ratio is even worse (2.1%). This can be explained by the fact that peers are active during a smaller duration in non popular channels, so servers' knowledge of active peers is unperfect. This low ratio is an issue that motivates the need for a dedicated strategy for improving the discovery of trustworthy peers for the bootstrap process. It can be done by contacting less peers, but preferably good and active ones for efficiency. Then, we enumerate the number of peers that deliver at least one packet during the first two minutes (third column); we observe that more peers are forwarding content in most popular channels, thus virtually providing an increased quality of service. Finally, the fourth column shows that approximately one third of peers that are actively providing content (protocol neighbors) are peers that were not given by servers in peerlists. Those results teach us that the initial lists of peers given to a joining peer are crucial. If they are not good enough, an additional process for requesting new peers to participate is needed, therefore adding some delay for video start. Note that this need is even more stringent for low popularity channels.

A second set of results is depicted in Table 1 (last two columns). We measure the time T start which is the average interval between getting the initial peerlist from servers and receiving the first packet. In all cases, the first packet is received from a peer in the peerlist. The results show that the peers that are contacted are not immediately responding, but the required time for them to send the packet is approximately constant, around 10 seconds. The last column shows the time at which the first packet is received from a peer obtained by an additional search process (not in the initial peerlist). The results are very different depending on the popularity of channels (time increases with popu- . This shows that the additional process is more critical for unpopular channels. Effectively, [START_REF] Hei | A measurement study of a large-scale p2p iptv system[END_REF] shows that playback starts up to 2 minutes after a join for unpopular channels; here the first packet is received at best 25 seconds after the reception of peerlists, highlighting this process criticity. Contrariwise, for popular channels, first packets arrive after playback has started; they help for improvement of quality of service instead of initial playback. The last measurement is depicted in Figure 1. We present the time interval between the first packet and the last packet received from a peer. As we measure only the first two minutes of bootstrap, peers still sending packets after this delay are not shown here. We show the results under a Cumulative Distribution Function (CDF) where a point at (0.4,45) means that 40% of transient peers have sent video packets during less than 45 seconds. This measurement shows how long a peer is expected to be transient in delivery to send video packets. Obviously, the longer that time, the easiest for the joining peer is to predict the filling of its video buffer. The main observation is that the curves are almost linear. Therefore, there is absolutely no guarantee on the expected video delivery duration for transient peers (time during which a peer will send video packets can not be predicted). The only curve we can analyze more easily is for the most unpopular channel: its reveals three typical durations about 10 seconds for 40% of peers, then about 50 seconds for 40% of peers and almost two minutes for others. As the video delivery for this channel is mostly ensured by peers provided through the additional process, we may argue those peers have a behavior that can be more easily predicted (probably due to a particular choice, according to their importance for the application quality).

The distributed switching problem and our proposal

As previously shown, a centralized management of the bootstrap procedure, in particular the delivery of peerlists, leads to a very long playback delay. Our study also shows that active peers in a peerlist are randomly chosen. However, it has been shown in current mesh-based streaming systems [START_REF] Li | Inside the new coolstreaming: Principles, measurements and performance implications[END_REF] that some characteristics such as upload capacity for example may have a great impact on INRIA the quality of the dissemination . Therefore there is a tendency in such systems, to connect peers having close characteristics (upload capacity, latency, activity, etc.). We call such peers matching peers in the sequel.

In order for an overlay to connect peers regarding such characteristics, gossipbased topology management systems (see e.g. [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF]) consist in ensuring that all peers are eventually connected to matching peers, through an epidemic and iterative protocol. With a randomly chosen peerlist, a joining peer has low chance to be connected directly to matching peers, and thus should quickly try to improve neighborhood. Actually, despite some recent works in this direction [START_REF] Simon | A quicker way to discover nearby peers[END_REF], a central server can hardly provide peers with matching peers in a very short time. This calls for a new strategy. We describe our approach in the following.

Multi-channel IPTV modelization. We assume an IPTV system consisting of α channels, each channel being modeled as an overlay graph. The set of all overlay graphs is noted G. A peer x is involved in exactly one P2P channel g(x) ∈ G among the α channels simultaneously offered by the IPTV service. In the P2P system, x cooperates with some other peers, called overlay neighbors, with the excusive goal of exchanging content related to the channel g(x). This small set of neighbors is noted Γ prot (x). Note that we focus in this paper on the topology problem, and do not address the higher level policies of packet exchanges between peers. Furthermore, let d(x, y) denote the hop-distance of the shortest path between a peer x and another peer y in the overlay graph

(d(x, y) = ∞ if g(x) = g(y)). For any integer k > 1, let the k-neighborhood of x be (Γ prot (x)) k = {y|0 < d(x, y) ≤ k}, where y is called k-neighbor of x.
Distributed channel switching definition. We define the distributed channel switching problem has, for any peer, (i) the overlay change from a channel to another one, on a fully distributed fashion (i.e. without request to a central entity), and (ii) the quick matching with accurate peers in the new overlay, in order to shorten playback delay. These are the two metrics we promote and evaluate in this paper.

Our proposal. Considering the fact that the number of available channels is not likely to grow indefinitely in practice, and that channels have a unequal distribution of popularity in reality (Pareto in [START_REF] Cha | Watching television over an ip network[END_REF]), approaches that may want to create a structured overlay (distributed hash table, skiplist ) connecting peers in all channels does not seem justified at the moment. Instead, we propose a light and simple mechanism, that aims at giving access to the most probable channels, thus capturing distributedly a fair amount of potential switches. To do so, besides the neighborhood that is used directly for the aim of the P2P protocol, a peer also maintains connections to peers belonging to other overlays, for channel switching purposes. We note Γ inter (x) c the set of contact peers of x, for the channel c. Formally, a peer y is a contact peer of x means that y is not in the same overlay (g(y) = g(x)), but x → y relation exists. A peer x is asked to maintain fresh lists of contacts (dead nodes or nodes that switched are removed from contact lists), and to try to match with those contacts.

We associate with a peer x a set C(x) of overlays in G such that an overlay graph G belongs to C(x) if and only if there exists a peer y such that both g(y) = G and y ∈ Γ inter (x) G . We say that x is a switcher to a channel if the overlay graph associated with this channel is in C(x). Because the number of channels α is expected to be large, a peer can not be a switcher to all other channels, for scalability issues (we bound by δ this maximal number). This forms a P2P overlay switching system depicted in Figure 3. System In a Nutshell. An overlay switch for a node x is the process leading to a complete change of its neighborhood Γ prot (x), to another one reflecting its move to a new chosen channel in G. Say that a peer x in G i wants to switch to a channel G j ; we describe now the two ways to switch overlays.

First, a peer x, has a switcher peer y (thus y has a Γ inter (y) Gj ) in its (Γ prot (x)) k neighborhood. Search could be implemented through basic expanding ring search technique, at k hops, from the requesting peer. It then only has to ask y for its contact list from G j , to replace its protocol neighborhood, and join the targeted channel. Note that, if both overlays G i and G j are based on a same matching preference system (say upload capacity), this is immediately leveraged in the new overlay (as few handshakes are necessary until x discovers matching neighbors in G j ) and will speed up the convergence process.

The second scenario is simply a failure in searching distributedly a contact peer for the targeted overlay. It can either occur because of the dynamics of the overlays (switchers are not accessible at k hops), or because the chosen channel is not in the most probable ones. In such a case, the traditional centralized approach is used to get a set of random contacts. Note that in IPTV, servers are still mandatory, as they are in charge of pushing the content into overlays.

Main Challenges. Allocating Contact Peers. In IPTV systems, some channels are far more popular than others [START_REF] Cha | Watching television over an ip network[END_REF]. Moreover, channels exhibit content similarities such that a participant to a given overlay is more likely to switch to an overlay having similar content or dealing with close activities than the one it is currently enjoying. That is, from one channel, the probability to switch to another channel is not equal for all channels. For example, paper [START_REF] Cha | Watching television over an ip network[END_REF] shows that 76% of switches are done in the same channel genre (e.g. sport, music or news). We would like every overlay to contain switchers having few contact peers in most probable channels, so that a peer that wants to switch is likely to find a switcher in its k-neighborhood.

Ensuring Matching Contact Peers. As we have seen through measurements in PPlive, the initial set of peers given to a joining peer in the channel is crucial for a quick start-up. We use the matching property in an overlay to directly give matching (or at least close) peers in the target overlay. As previously said, our assumption is that the neighborhood reflects the matching, in other words,

INRIA

for two integers k 1 and k 2 with k 1 < k 2 , if y 1 is a k 1 -neighbor of x and y 2 is a k 2 -neighbor of x, then it means that y 1 matches better with x than y 2 . The challenge is here to maintain an accurate matching between peers, despite the overlay dynamics.

Protocol description

We now describe the implementation of our proposal, summarized on Figure 1.

Switcher creation. In order for nodes to distributedly choose for which channels they should be switchers, we refer to the notion of domination, well known in graph theory. A set D ⊆ V of vertices in a graph G = (V, E) is called a dominating set if, for every vertex x in V , x is either an element of D or is adjacent to an element of D. More generally, a k-dominating set extends this adjacency notion at k hops, at most, from a given peer x [START_REF] Haynes | Fundamentals of domination graphs[END_REF]. Consider that at most δ resources (here channels to be switcher for) can be allocated to a node. A δ-configuration is an allocation of a set of resources such that, for every resource, the vertices associated with this resource form a dominating set. The same extension as in previous definitions can state for a δ-configuration. That is, a (δ, k)-configuration is to allocate resources to vertices, such that no more than δ different resources are allocated to any vertex, and each vertex can access a resource associated with another vertex in less than k hops. Back to our switcher creation problem, nodes in the dominating set are responsible for keeping contacts in specific channels, and the resources are the overlays one peer has to keep in touch with.

The purpose of (δ, k)-configuration is to determine a configuration; unfortunately this decision problem has been proved to be NP-complete. That is, all optimization problems that are directly related with this decision problems are NP-hard. Thus, maximizing the number of channels that can be allocated, with a given δ and a given k is NP-hard, as well as minimizing the maximal distance and the number of switcher peers δ for a given k and a given most probable channels to cover. Therefore, an optimal implementation of our algorithm can not reasonably be computed in a dynamic large-scale system. Instead, we propose a heuristic which enables to provide a practical and realistic alternative.

We assume that each peer joining a channel is provided by the central server or neighbors with the list of most probable channels for switching in the same channel genre. It then checks at k hops from itself if a switcher is missing, sorted by order of importance; if so, it become a switcher for this channel (an initial peerlist is acquired from the server), with a limit of δ channels. If switchers to all most probable channels have been found, the furthest ones are chosen (l. 4-6).

Matching through gossip. In order for peers to get connected to matching peers, according to some application predefined metric (as e.g. proximity, latency or bandwidth), we use a gossip based topology management similar to T-Man [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF]. In this paradigm, each peer owns a value reflecting this metric. To end up with neighbors close from this value (l. 3 & 13), each peer periodically chooses its neighbor with the closest value, and exchanges with it a list of current closest neighbors and some nodes chosen randomly amongst the channel population. After each exchange, closest nodes are kept as neighbors, while furthest ones are discarded. It turns out that only a few steps are needed to Initially: upon IPTV join of a node x in channel ci 1: Arbitrarily fixed input: k (depth of switcher search), t (awaited T-Man convergence for Γ prot (x)) 2: Request server ci that returns a peerlist Γ prot (x)

Matching for x in current channel: 3: T-Man resulting in matched Γ prot (x) 4: After t cycles, then periodically search for switchers at k hops:

5:
Request switchers in `Γprot (x) ´k 6:

Pick a channel cj in missing most probable, or choose the furthest one 7: Transform x into a switcher for cj 8:

Request server cj that returns a peer list Γ inter (x) C j

9:

T-Man resulting in a matched Γ inter (x) Upon switch to channel cj: 10: Find a switcher y for cj among `Γprot (x) ´κ with increasing κ (κ ≤ k) 11:

Γ inter (y) C j becomes Γ prot (x) in cj 12: Else, request server cj that returns a peerlist Γ prot (x) 13: Goto line 3 Algorithm 1: A simple protocol for probabilistic switching reach a near optimal peer matching, even in presence of churn [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF]. The random peers needed by this protocol are provided by peer sampling protocols, that are also based on the gossip paradigm (see e.g. Cyclon [START_REF] Voulgaris | Cyclon: Inexpensive membership management for unstructured p2p overlays[END_REF] or the Peer Sampling Service [START_REF] Jelasity | The peer sampling service: Experimental evaluation of unstructured gossipbased implementations[END_REF]).

The same matching technique as for overlay neighbors Γ prot is used by switchers for contacts they keep in touch with in Γ inter , except that the procedure there is not bidirectional (the switcher tries to match with peers in target overlay, but the reverse case is not true). With this matching process, once a peer wants to switch, and is able to find a switcher in its k-neighborhood, the peer contacts given by the switcher have relatively a high chance to be close from its future position in the new channel (l. 10-11).

Multi-channel system simulation

We evaluated our proposal using the PeerSim [4] simulator targeting large-scale and dynamic overlays. The multi-channel system we implemented as an input is based on recent application measurements conducted in [START_REF] Cha | Watching television over an ip network[END_REF].

Simulation Configuration. The system is composed of 150 channels, classified in 13 genres (e.g. cine, sports, kids, docu). Channel popularity in each genre follows a Zipf distribution, that decays fast for non-popular channels; the probability to stay in the same genre during a switch is set to 76% [START_REF] Cha | Watching television over an ip network[END_REF][START_REF] Cha | On next-generation telco-managed p2p tv architectures[END_REF]. Otherwise, a peer picks uniformly at random first the genre it switches to (probabilities are exposed in [START_REF] Cha | Watching television over an ip network[END_REF]), and then the channel in that genre. Furthermore, according to the time peers watch channels, peers get assigned a role: surfer (watches the channel from 0 to 45 seconds), viewer (46 to 3600) or leaver (3601 to 36000); joining and departing peers create the dynamism (or churn) in the system. Note that a second corresponds to one Peersim cycle execution in our Simulation parameters are set as follow: 10 5 peers in the system, an average channel-neighborhood Γ prot per peer of 15 (consistent with observations made in Section 2). A peer could be a switcher for simply 1 channel (δ = 1), and keeps in touch with 5 peers in this channel for Γ inter (note that PPlive returns not less that three peerlists of 50 peers each). The gossip protocols (matching and sampling), for both Γ prot and Γ inter are executed at each cycle. After a switch, a peer waits for t = 3 cycles before looking for switchers, and this action is performed again every 3 cycles (to prevent a flood for search at every cycle).

Simulation Results. We run simulation 86400 cycles for an equivalent of one day of simulation. Key statistics, collected from 100 randomly selected peers, are presented on Figure 3. Our implementation leads to 58% of distributed switches. Note that this percentage cannot be greater to the probability of switching in the same genre (here 76%), as we only provide switchers for channels in the same genre group (difference between 58% and 76% is due to churn and to the fact that only the 5 most probable channels are linked in each genre, and not all of them). The average distance between a switching peer and a switcher to the target overlay was 0.67 hops. This is due to the fact that a majority of peers are switchers themselves or could find one among their 1-neighbors.

The neighborhood perfection ratio (NPR) is a simple measure for the correctness of the matching of peers in our simulator: for a peer x, it is the number of best matches for x that are currently its neighbors, divided by the number of neighbors of x (1 then expresses that all neighbors of x are its best matches, and no better one exists in the overlay). We now observe the number of matching peers that are given to a switching peer, by the server or by our system. In the centralized case, random selection provides only 5.8% of peerlists containing at least one matching neighbor (20% of matched contacts on average). When switches are executed distributedly, one third of the provided peerlists contains at least one good contact (with a high value of NPR of 73%), thus highlighting the improvement in providing neighbors with close characteristics.

We now look (Figure 4) at the number of cycles needed, after a switch, to reach a given NPR. As expected, the distributed process in every case helps switching peers to reach more quickly a given ratio, as the given peerlist is closer from the switching peer than random list given by the server. We also observe that centralized switches perform relatively well: this is due to the efficiency of gossip-based topology management which converges quickly in many scenarios [START_REF] Jelasity | T-man: Gossip-based overlay topology management[END_REF]. This motivates current streaming applications to consider gossipbased protocols for the efficiency of neighborhood management. Finally, as an important part of switching peers (33%) is immediately provided with a high quality peerlist with respect to the matching criterion (NPR of 73%), we also plot convergence time for those peers (called "Distr. improved" on Fig. 4). We observe that the time required to reach a perfect neighborhood is very short. In this case, as nearly all given neighbors are matching, the missing ones could be found in very few cycles.

This simulation study shows that a simple implementation can improve in a substantial number of cases (i) the quality of the initial sets provided to switching peers, thus allowing (ii) a fastest convergence towards matching neighborhoods. Finally (iii), gossip-based mechanisms appear to be an elegant and reliable solution to tackle this self-organization issue. Increased values for parameters δ, k and the number of channels linked in same genres obviously improve results. Based on observations from Section 2, this could potentially reduce significantly video start-up delays at the application level.

Conclusion

In this paper, we address the problem of switching from one channel to another in P2P IPTV systems, in a distributed fashion. To the best of our knowledge, no previous studies have dealt with this crucial issue for the next generation of multimedia delivery mechanisms over Internet. This approach shows the interest of leveraging peers' belonging to an overlay, in order to improve forthcoming switches. We believe that the simple proposed algorithm represent a first step toward the design of distributed and efficient switching mechanisms.

5 Fig. 1 :

 51 Fig. 1: CDF of the duration of video packet delivering for transient neighbors

Figure 2 :

 2 Figure 2: An example of a resulting system G. Node x has 4 neighbors in its current overlay G i (dashed lines) and 2 contacts in other overlays, δ = 2 (plain lines).

Figure 4 :

 4 Figure 4: Convergence to matched neighbors

Table 1 :

 1 Measurement results for bootstrap procedure in PPlive receives the peerlists from three servers, each peerlist consisting of 50 peers that are assumed to watch the same channel, in order for the joining peer to bootstrap. 20 channels are selected per class, except for the 5-star class for which 8 channels only were available.A first set of results is reported in Table

	INRIA

RR n 6857


N Zandi Atashbar

A Baboli

A MULTI-OBJECTIVE ROUTING PROBLEM FOR PERISHABLE ITEMS IN A DISASTER RELIEF

Keywords: Supply Chain Management, Disaster, Dynamic routing problem, Perishable Items, Multi-objective optimization, satisfaction level

Researches and information available shows that the number of natural disasters is increasing dramatically; hence disaster management is become as one of the most important topics. In this study, in order to manage effectively the logistics activities in cases of natural disaster, a comprehensive study of a multi-objective vehicle routing problem model for perishable items are proposed. The expiration date of goods and time windows have to be also taken into account. In this case, respecting short life shelf of highly perishable items, as blood or blood derivative products, and some pharmaceutical products, as well as disaster situation change the classical routing problem form, principally based on cost optimization, in to service level maximization and time optimization. With this aim, a multi-objective routing problem has been developed. The first objective in this situation is to maximize satisfaction and covering their demands and the second objective is to minimize the total time needed to transfer perishable goods. Finally, proposed resolution approach and a numerical example solved by using CPLEX 12.6, illustrate the procedure of the presented model.

INTRODUCTION

Natural disasters such as earthquake are complicated, in which it is so difficult to predict the time and location of the earthquakes, despite using the net of thousand seismographs and continual analysis of data, using powerful computers, all around the world. Accidental and unpredictable nature of Natural disasters leads to existence of comprehensive plans in order to reduce the danger of the probable events.

According to the previous experiences, although logistical actions and evacuation operations are important procedures, in order to reduce the fatality after an earthquake, the determination of good logistical plan remain difficult.

The occurrence of unexpected events and natural disasters and effects of them, requires contemporary societies to do necessary planning to face and minimize the deleterious effects. Although in minor incidents, doing it empirically is possible and there is no need for special tools, during bigger disasters and natural calamities such as earthquakes, because of the size and complexity of the factors involved, it is not possible to do it empirically. Despite great scientific progress and reduced concerns about big crisis, yet, during crisis, most of the aid responses require the skills of involved and responsible organizations. Regardless of the type of special operations by these organizations, all of them follow an important and shared purpose which is the fast delivery of right amount of goods, energy and financial resources to affected areas. In order to achieve this goal, improvement in the logistics area can have effective results. Another key role of logistics and routing problem in crisis is in comprehensive planning to respond quickly and save the victims of the crisis, because over time, the likelihood of their survival decreases rapidly.

After a crisis, routing problem is one of the main activities for responding, since it is a complex subject. Routing problem and logistics are part of the supply chain management that include planning, implementing and controlling the forward and reverse flow, storage of goods, services and related information between the point of origin and point of consumption efficiently to satisfy customer requirements.

Thus, the question of interest in this study is providing a suitable planning, based on which, perishable items could be transferred to medical centers on the lowest time during the crisis. Obviously, it is very difficult and complex task; because, in spite of the huge mass of activities, and limited resources at hand, no precise information on the needs in the affected areas is available.

LITERATURE REVIEW

Since one of the important parts of crisis management is routing problem, determining an overall system for logistics management, while coping with the crisis and minimizing its damages is vital. In fact, with better forethought and planning, the extent of damage and injuries caused by the crisis can be reduced effectively. With this view, many studies have been done in the area of Crisis Management, Routing problem and Relief Logistics.

Ray [START_REF] Ray | A Multi-Period Linear Programming Model for Optimally Scheduling the Distribution of Food-Aid in West Africa[END_REF] presented a single commodity network flow model with multi-mode, taking into account the limited capacity of the network. In this model, planning horizons is considered as multi-periodic and the objective is to minimize the sum of all costs that are achieved during the transportation and storage of food aid to the victims. Crainic et al. [START_REF] Crainic | Multicommodity, Multimode Freight Transportation: A General Modeling and Algorithmic Framework for the Service Network Design Problem[END_REF] proposed an optimization algorithm based on decomposition and column generation in order to minimize the total operation cost and delay, for a transportation network with multiple modes and multiple types of products .In 1990, Haghani and Oh [START_REF] Haghani | Formulation and Solution of a Multi-Commodity, Multi-Modal Network Flow Model for Disaster Relief Operations[END_REF] proposed a network of multi-mode and multi-type commodity allocation model for the purpose of strategic planning in order to predict the flow of goods in the network. The objective function of this model is to minimize the total cost of routing and transmission .In order to transport vital supplies to areas that has been affected by the crisis, Barbarosoilu et al. [START_REF] Barbarosoglu | A Two-Stage Stochastic Programming Framework for Transportation Planning in Disaster Response[END_REF] proposed a two-stage stochastic programming model for transferring vital aid items in crisis where a network with multiple modes of transportation and several kinds of commodity are considered. In the context of vehicle routing, operational scheduling of helicopter activities during relief after the crisis is considered by the authors. For example, Barbarosoglu et al. [START_REF] Barbarosoglu | An Interactive Approach for Hierarchical Analysis of Helicopter Logistics in Disaster Relief Operations[END_REF] proposed a model for staff allocation, routing and transportation .Yi and Ozdamar [START_REF] Ozdamar | Emergency Logistics Planning in Natural Disasters[END_REF] presented a model which is a mixed integer programming model that combines the vehicle routing problem with the problem of locating facilities and considers the network flow as multi-commodity. In one recent study, Balcik and Beamon [START_REF] Balcik | Facility Location in Humanitarian Logistics[END_REF] presented to determine the number and location of distribution centers that should be used in rescue operations. In this study, the positioning problem is formulated as a kind of Maximum Covering Problem, where estimates are available on demand for a range of possible scenarios. In 2004, Ozdamar et al. [START_REF] Ozdamar | A Dynamic Logistics Coordination Model for Evacuation and Support in Disaster Response Activities[END_REF] proposed a programming model integrated with decision support systems have been in the context of natural disasters. This model presents time-dependent dynamic transportation planning problem that needs to be repeated at relief intervals .In the context of perishable items, Sazvar et al. [START_REF] Sazvar | A replenishment policy for perishable products with non-linear holding cost under stochastic supply lead time[END_REF] developed an inventory model for perishable products under stochastic lead time assumption. Sazvar et al. [START_REF] Sazvar | A bi-objective stochastic programming model for a centralized green supply chain with deteriorating products[END_REF] proposed a new replenishment policy in a centralized supply chain for deteriorating items. In this model, inventory and transportation costs, as well as the environmental impacts under uncertain demand were considered. The literature does not lack approaches on Relief logistics problem solving methods, innovative and ultra-innovative solutions. For example, in 2007 for the aid logistical problem, Yi and Kumar [START_REF] Yi | Ant Colony Optimization for Disaster Relief Operations[END_REF] applied ant colony algorithm method. The model is divided into two phases of decision making. The first phase makes possible routes under the guidance of the of pheromone traces, while in the second phase the solution developed to assign different types of vehicles and goods.

PROBLEM DISCRIPTION

Studying the issue of crisis management has started so many years ago. The need for logistics management in relief efforts after crisis such as the earthquake has been in researchers' interest for the recent years. In this context, the first objective in this situation is to maximize satisfaction and covering their demands and the second objective is to minimize the total time needed to transfer perishable goods.

Details of the constraints are given as follows.

1-There are some source points and each source point has a determined inventory of each perishable item. In source points we have the conditions of keeping the items.

2-There are some destination points in which there are determined demands in various times for each item.

3-There are some intermediate points (likes squares or crossroads) that connect the edges of the routs (city distance method).

4-In all points there is the possibility of passing vehicles.

5-There are some different types of vehicles with different capacity for transporting items. The vehicles don't have the possibility of keeping the perishable items for a long time.

The problem can be formulated as an integer programming. We assume all parameters are non-negative numbers, and the number of customers and number of vehicles are integers. If there is a vehicle goes from source to destination in time 𝑡, it will be one and otherwise zero 𝐹𝐹 𝑡

Model Formulation

An integer linear programming (ILP) model is proposed to minimize the total time needed to transfer perishable goods and to maximize satisfaction and covering their demands. The formulation (objective function and constraints) of the proposed model are explained below.

Objective Function:

𝑚𝑖𝑛 𝐹 1 = ∑ ∑ ∑ max (0, ∑ 𝑑 𝑝,𝑢 𝑣 𝑡 𝑢=1 -∑ 𝑥𝑑 𝑝,𝑢 𝑛 𝑡 𝑢=1 ∑ 𝑑 𝑝,𝑢 𝑣 𝑡 𝑢=1 ) 𝑡 𝑝 𝑛 (1) 𝑚𝑖𝑛 𝐹 2 = ∑ ∑ ∑ ∑ ∑ 𝐿 𝑢-𝑡 𝑛 𝐹 𝑚,𝑝,𝑡,𝑢 𝑛 𝑢≥𝑡 𝑡 𝑝 𝑚 𝑛 (2)
Objective function (1) maximize the satisfaction and covering the demands of destination points. In other words, this equation subtracts the accumulated amount of satisfied demands (the accumulated amount of demands in a destination point for a period and all of previous periods that are satisfied by sending the products) from the total accumulated amount of demands (the total accumulated amount of predicted demands in a destination point for a period and all of previous periods) divided by the total accumulated amount of demands. It gives us a fraction that shows the percentage of accumulated unsatisfied demands in a destination point and by adding these fractions for all of periods, destination points and product types. The final result expresses the total accumulated amount of unsatisfied demand which we obviously want to minimize. (Note that in order to avoid the negative amounts for that fraction, we maximize the value of that fraction and value of zero.)

Objective function [START_REF] Crainic | Multicommodity, Multimode Freight Transportation: A General Modeling and Algorithmic Framework for the Service Network Design Problem[END_REF], multiplies the number of product 𝑛, sent from source 𝑚 in time 𝑡 and arrived to destination 𝑝 in time 𝑢, by the amount of penalty. The amount of penalty for product type 𝑛 depends directly on the amount of 𝑢 -𝑡 (the time between source and destination). In fact, the increase in 𝑢 -𝑡 causes an increasing of penalty, and after the expiration date of items the amount of penalty will be multiplied. Finally, we minimize the summation of these results in order to reduce the total amount of penalties. Therefore, the model is looking for transferring items in shorter times. Knowing that the Hierarchical Method is used to solve this model, we can be assured that there will be no disturbance in the satisfaction of demands.

Notice that in the first objective function, we want to increase the total satisfaction of demands. Hence, it tends to increase the number of transferred products. Unlike this one, the second objective function wants to reduce the total amount of penalties, and conversely, it tends to decrease the number of transferred products. Therefore, we can clearly see the conflict for the desired amount of transferred products in these two objective functions.

Constraints: [START_REF] Barbarosoglu | An Interactive Approach for Hierarchical Analysis of Helicopter Logistics in Disaster Relief Operations[END_REF] expresses that the number of product 𝑛 that leaves source 𝑚 at time 𝑡 is equal to the number of product 𝑛 that reach destinations at times 𝑢 ≥ 𝑡. Constraint [START_REF] Ozdamar | Emergency Logistics Planning in Natural Disasters[END_REF] indicates that the number of products that goes from source 𝑚 to destination 𝑝 at the end of the time 𝑡 have to be equal to the number of product 𝑛 that reaches destination 𝑝 at time 𝑡 minus the number of product 𝑛, sent from destination 𝑝 to other destination points at time 𝑡. Constraint ( 7) respects the capacity of vehicle. Constraints [START_REF] Ozdamar | A Dynamic Logistics Coordination Model for Evacuation and Support in Disaster Response Activities[END_REF] expresses that the number of products, sent from sources is less or equal to the inventory of that source. Constraint ( 9) respects the number of vehicles that can be passed in each route. Constraint [START_REF] Sazvar | A bi-objective stochastic programming model for a centralized green supply chain with deteriorating products[END_REF] expresses that the number of products, enter to each intermediate point at time t, is equal to the number of products that leaves this point at the same period. Constraint [START_REF] Yi | Ant Colony Optimization for Disaster Relief Operations[END_REF] indicates that if passing the rout is allowed, the variable z can take values, otherwise, z will be zero. Constraint [START_REF] Ding | Discussions on normalization and other topics in multi-objective optimization[END_REF] expresses that if passing the route of source to destination in 𝑢 -𝑡 time will be allowed, the variable 𝐹 can get the value of more than zero, otherwise it must be zero.

∑ ∑ ∑ ∑ 𝑥 𝑦,

NUMERICAL EXAMPLE

An illustrative example is used to show the application of the proposed model. We solved an example which has 13 nodes, 32 edges and 1 type of vehicle as you see in Fig 1. The node N1 and N2 are warehouses (source nodes). The nodes N3, N4 and N5 are medical centers (destination nodes) and others nodes are intermediate nodes. There are some oneway and two-way roads. For example N1 to N6 is two-way road and N1 to N4 is one-way road. We assume that the penalty function is as below.

𝐿 𝑢-𝑡 𝑛 = { 𝑢 -𝑡 𝑢 -𝑡 ≤ 5 2 * (𝑢 -𝑡) 𝑢 -𝑡 > 5 (13)
It means that if the travel time between source node and destination node is equal or less than 5, which is our assumed expiration date, the penalty will be equal to travel time. Since it is less than the expiration date of the product, we assumed a lower penalty, but if the travel time is more than 5, the probability of spoilage is more, thus, the slope of penalty will be more. Here, we assumed that after the expiration date, the slope of penalty is double of the travel time. This example considers that there is just one type of perishable item. We added 3, 2, 1, 1, 2 and 1 vehicles in node N2, N1, N1, N12, N6 and N10 at time 0, 0, 4, 0, 0 and 3, respectively. There are 250 and 1200 initial goods in inventory respectively in source N1 and N2. The demands of the medical centers (destination nodes) are as below.

Results

The proposed model (Eq. ( 1)-( 11)) were solved by CPLEX 12.6 with 4 GB of RAM. The model has 12,112 constraints, 104,159 variables. Using an Intel 2.1 GHz processor, the global optimal solution is reached after 11.36 seconds of runtime (and 69,023 iterations). For the solution procedure, the Hierarchical Method is used [START_REF] Ding | Discussions on normalization and other topics in multi-objective optimization[END_REF]. This method gives us the capability of ranking the objective functions, and then the lower ranked function will be minimized, subject to the new set of constraints that won't allow the values of the higher ranked objective function, to surpass a predetermined fraction of their optimal values. The main idea of the Hierarchical Method in multi objective problem is to transform one or some of them as constraints instead of objective functions. In proposed model, since there are two objective functions, first one is considered as main objective function and the model is solved without considering the second objective function. Then, the first objective function converts into a constraint and finally, by solving the model with objective function (2) subjected to the new set of constraints, the final results can be reached. In the Hierarchical Method, in order to convert the objective function into a constraint, a parameter called 𝜀, should be considered, which can be interpreted as the distance from optimality in percent [START_REF] Ding | Discussions on normalization and other topics in multi-objective optimization[END_REF]. We considered 𝜀 as a fraction of optimum amount of first objective function (𝛼𝐹 1 * ). Here, we assumed 𝛼 to be 0.1. The new constraint is as below: To provide the demands of N4 (destination node), 80 and 3 products must be sent from N1 at time 0 and 18, respectively. 37, 39 and 21 products must be sent from N2 at time 9, 10 and 18, respectively, as it's shown in Fig 3. In this case, the obtained optimum value of objective function ( 1) is 3.411, which is between the minimum 3.101 (𝐹 1 * ) and maximum 75 (𝑛 * 𝑝 * 𝑡). This value indicates that the total accumulated amount of unsatisfied demand is not too much (4.5%). The obtained optimum value of second objective function is 5753. This value expresses the amount of penalty which is multiplied by the number of transferred products. The maximum amount for this objective function is 8899. By increasing the value of 𝛼 from 0.1 to 0.2, the obtained optimum amount of objective function (1) will be 3.721 (9% increase), and the obtained optimum amount of second objective function will be 5321 (8% decrease). By continuing to increase the amount of 𝛼, we will face an increase in the amount of unsatisfied demands and a decrease in the amount of incurred penalty. The increase in the first objective function and the decrease in the second objective function, shows the tradeoff between the two objective functions.

𝐹 1 (𝑥) ≤ 𝐹 1 * + 𝜀 (

CONCLUSION

According to previous experiences, although logistical actions and evacuation operations are important procedures, during an earthquake and other disasters, the determination of good logistical plan remains difficult. In this situation, it is obvious that people's requirements have to be met by stored commodities from related suppliers. Moreover, knowing that some commodities have limited life times, in order to transfer them to their destinations, this limitation must be taken into consideration. Therefore, according to these conditions, a multi objective model for routing problem has been proposed. The first objective is to maximize satisfaction and covering their demands, and the second one is to minimize the total time needed to transfer perishable goods. Proposed resolution approach has been presented, along with an example that illustrates the procedure of this model. The results of solving this example by CPLEX 12.6 based on the Hierarchical Method are analyzed and showed a good trade-off between the two objectives. Finally, it should be noted that the future plans of the authors include multi delivery point network designing by considering one-way and two-way

Figure 1 :

 1 Figure 1: Network schema for numerical example

  In this case, to provide the demands of N3 (destination node), 40, 40, 40, 40 and 7 products must be sent at time 1, 3, 4, 11 and 16, respectively. 34 products must be sent from N2 at time 10, as it's shown inFig 2.

Figure 2 :

 2 Figure 2: Providing routs for the demands of N3

4 Figure 3 :

 43 Figure 3: Providing routs for demands of N4 120 and 60 products are sent to the destination node (N5) at time 0 and 12, respectively, as it's shown in Fig 4.

Figure 4 :

 4 Figure 4: Providing routs for demands of N5

  Is equal to 1, if the vehicle type 𝒗 leaves point 𝒐 in the direction of point 𝒈 at time 𝒕 and reaches point 𝒈 at time 𝒖, otherwise zero. Penalty, if the product 𝒏 moved from source at time 𝒕 and arrives to destination at time 𝒖. (More distance between 𝒕 and 𝒖, generate greater amount of penalty.) Amount of space occupied by each unit of product. 𝑣𝑛 𝑛 Initial inventory of product 𝒏 in source 𝒎. 𝐼𝑁 𝑛,𝑚 The maximum number of vehicles that can be crossed at the edge of 𝒐 to 𝒈. 𝑟𝑐 𝑜,𝑔 If the pass from 𝒐 to 𝒈 is allowed, is equal to 1 and otherwise zero. (the output of the algorithm) 𝑟 𝑜,𝑔 The number of product 𝑛 that goes from point 𝑜 to point 𝑔 with vehicle 𝑣 at time𝑡. 𝑥 𝑜,𝑔,𝑡 𝑛,𝑣 The number of product 𝑛 that reached destination 𝑝 at time 𝑡 in order to be consumed in destination 𝑝. 𝑥𝑑 𝑝,𝑡 𝑛 The number of vehicles of type 𝑣 goes from 𝑜 to 𝑔 at time 𝑡. 𝑧 𝑜,𝑔,𝑡 𝑣 The number of product 𝑛 that vehicles of type 𝑣 left source 𝑚 at time 𝑡 and reach destination 𝑝 at time 𝑢. 𝐹 𝑚,𝑝,𝑡,𝑢 𝑣

	Variables:
	Indices and Sets:
	𝒎	Set of source points
	𝑝	Set of destination points
	𝑘	Set of intermediate points
	𝑜, 𝑔	Total points
	𝑣	Index for type of vehicles
	𝑡, 𝑢	Time index
	𝑛	type of product Index
	Parameters:
	𝑯 𝒐,𝒈,𝒕,𝒖 𝒗
	𝑎𝑣 𝑜,𝑡 𝑣	The number of vehicle type 𝒗 added to point 𝒐 at time 𝒕.
	𝑑 𝑝,𝑡 𝑛	Demand prediction of product 𝒏 in point 𝒑, at time 𝒕
	𝑐𝑣 𝑣	Capacity of vehicle type 𝒗.
	𝐿 𝑢-𝑡 𝑛

  Constraint (3) controls the products equality in destination points. The amount of product 𝑛 that reaches the destination 𝑝 at the time 𝑡 in order to be consumed in 𝑝 is equal to the

	𝑡					𝑢		𝑡
								𝑜,𝑝,𝑢 𝑛,𝑣	𝐻 𝑜,𝑝,𝑢,𝑡 𝑣	-∑ ∑ ∑ 𝑥 𝑦,𝑝,𝑔,𝑡 𝑛,𝑣	= 𝑥𝑑 𝑝,𝑡 𝑛	∀𝑝, 𝑛, 𝑡	(3)
	𝑢=1		𝑣	𝑜	𝑦=1	𝑦=1	𝑣	𝑔
								𝑡
	∑ 𝑧 𝑜,𝑔,𝑡 𝑣	= 𝑎𝑣 𝑜,𝑡 𝑣 + ∑ ∑ 𝑧 𝑔,𝑜,𝑢 𝑣	𝐻 𝑔,𝑜,𝑢,𝑡 𝑣	∀𝑣, 𝑜, 𝑡	(4)
	𝑔							𝑔	𝑢=1
	∑ ∑ 𝑥 𝑦,𝑚,𝑔,𝑡 𝑛,𝑣 𝑔 𝑣	= ∑ ∑ 𝐹 𝑚,𝑝,𝑡,𝑢 𝑛 𝑢≥𝑡 𝑝	∀𝑚, 𝑛, 𝑡	(5)
				𝑡
	∑ ∑ ∑ 𝑥 𝑦,𝑜,𝑝,𝑢 𝑛,𝑣	𝐻 𝑜,𝑝,𝑢,𝑡 𝑣	-∑ ∑ 𝑥 𝑦,𝑝,𝑔,𝑡 𝑛,𝑣	= ∑ 𝐹 𝑚,𝑝,𝑦,𝑡 𝑛	∀𝑝, 𝑛, 𝑡, 𝑦	(6)
	𝑣	𝑜	𝑢=1			𝑣	𝑔	𝑚
	𝑡
	∑ ∑ 𝑥 𝑦,𝑜,𝑔,𝑡 𝑛,𝑣	𝑣𝑛 𝑛	≤ 𝑧 𝑜,𝑔,𝑡 𝑣	𝑐𝑣 𝑣	∀𝑣, 𝑜, 𝑔, 𝑡	(7)
	𝑦=1	𝑛
	∑ ∑ ∑ 𝑥 𝑡,𝑚,𝑜,𝑡 𝑛,𝑣	≤ 𝐼𝑁 𝑛,𝑚	∀𝑛, 𝑚	(8)
	𝑣	𝑜	𝑡
	𝑧 𝑜,𝑔,𝑡 𝑣	≤ 𝑟𝑐 𝑜,𝑔		∀𝑣, 𝑜, 𝑔, 𝑡	(9)
			𝑡	𝑢			𝑡
	∑ ∑ ∑ 𝑥 𝑦,𝑜,𝑘,𝑢 𝑛,𝑣	𝐻 𝑜,𝑘,𝑢,𝑡 𝑣	= ∑ ∑ 𝑥 𝑦,𝑘,𝑔,𝑡 𝑛,𝑣	∀𝑘, 𝑛, 𝑡, 𝑣	(10)
	𝑜	𝑢=1	𝑦=1			𝑦=1	𝑔
	𝑧 𝑜,𝑔,𝑡 𝑣	≤ 𝑟 𝑜,𝑔 𝑀	∀𝑣, 𝑜, 𝑔, 𝑡	(11)
	∑ ∑ ∑ 𝐹 𝑚,𝑝,𝑡,𝑢 𝑣	≤ 𝐹𝐹 𝑢-𝑡 . 𝑀	∀𝑡, 𝑢 ≥ 𝑡	(12)
	𝑣	𝑚	𝑝

number of product 𝑛 that reaches 𝑝 at the time 𝑡 minus the number of product n that are sent from 𝑝 to other destination points at time 𝑡. Constraint (4) verifies vehicle equality in point 𝑜. The number of added vehicles in this point at time 𝑡 in addition to the number of vehicles that reach this point from previous points at time 𝑡 is equal to the number of vehicles that leave point 𝑜 at time 𝑡. Constraint

Table 1 : The demands of the medical centers Destination point (medical center ) In time t Demand

 1

	N5	3	10
	N5	7	30
	N5	19	56
	N5	11	60
	N5	20	22
	N5	4	30
	N4	10	22
	N4	12	30
	N4	15	45
	N4	18	30
	N4	24	25
	N3	9	50
	N3	12	50
	N3	15	20
	N3	18	30
	N3	21	50
	N3	23	32
	N3	24	35

CIE44 & IMSS'14 Proceedings, 14-16 October 2014, Istanbul / Turkey

roads. Currently, we assumed that demand is deterministic, so in the future works it can be considered under the uncertainty to be closer to the real world.

ACKNOWLEDGMENT

The authors gratefully acknowledge the scientific and financial supports of ARC 8 of Region Rhône-Alpes, France in developing this paper.