Algorithme de Dijkstra

Algorithme de Dijkstra

MÉTHODOLOGIE

Ce deuxième chapitre aborde les approches méthodologiques à la base du développement du modèle mathématique permettant la simulation d’un réseau intelligent dédiée à l’opération des véhicules PRT. La première partie présente la structure du modèle qui permet la simulation de déplacements de véhicules dans un réseau. Une fois le modèle présenté la deuxième partie présente les paramètres qui le composent ainsi que les indicateurs de performances à relever qui serviront aux analyses. Enfin le modèle sera étudié au travers de plusieurs scénarios qui seront exposés en troisième partie.

Modèle dynamique

Le modèle doit répondre à certaines spécifications de base qu’il est important d’expliciter ci après. Le raisonnement ainsi que la méthodologie permettant au modèle de réaliser les attentes du cahier des charges sera ainsi développé.

Structure du modèle dynamique des déplacements individuels en milieu urbain

Afin de s’intéresser aux déplacements et aux comportements de capsules au sein d’un réseau il faut établir un modèle. Ce modèle doit répondre à certaines exigences qui seront établies ci-après. Le modèle doit être capable de simuler les déplacements et la gestion de véhicules PRT dans un réseau définit tout en répondant au besoin de mobilité exprimé sous la forme d’une matrice Origine Destination (Matrice OD) tel qu’exprimé à la Figure 2.1.La structure du modèle permet ainsi de simuler par itérations l’état du système modélisé. La simulation se définit par une phase d’initiation suivie d’une boucle de n itérations tel qu’illustré à la Figure

Le modèle est développé sous Matlab (R2010b)

La Figure 2.1 correspond à un schéma bloc ou schéma fonctionnel, il permet de visualiser les entrées et les sorties ainsi que les paramètres qui peuvent influencer la réponse. La Figure 2.2 quant à elle décrit concrètement le déroulement d’une simulation. A chaque phase de ce schéma correspond une fonction mathématique, ce schéma reprend donc la logique du code du modèle. Le Tableau 2.1 présente la description de toutes ces phases.

Algorithmes

La 1ère phase de répartition correspond à la répartition instantanée, c’est-à-dire que si un utilisateur demande un véhicule et qu’il y en a un de libre à cette même station ce véhicule lui sera attribué automatiquement et instantanément. Cependant la 2ème phase de répartition correspond au cas où une capsule doit être amenée d’un autre nœud pour répondre à la demande de l’utilisateur. Deux façons de répartir les véhicules seront étudiées correspondants à deux algorithmes différents, l’une dite « répartition évidente » et l’autre basée sur l’algorithme de colonie de fourmis.
La répartition « évidente » envoie les véhicules les plus proches, les demandes ne sont pas considérées comme un ensemble mais individuellement. La 1ere demande recevra la capsule la plus proche, puis la 2ème etc. L’algorithme qui sera utilisé dans le modèle est une légère modification de l’algorithme de base de colonie de fourmis, cependant la seule différence provient dans la construction de la matrice des distances. L’algorithme est donc identique mais la matrice des distances, au lieu d’être la distance entre toutes les villes comme dans le problème du voyageur de commerce, il s’agit de la distance entre les capsules et les nœuds.
L’algorithme de colonie de fourmis permet quant à lui de considérer toutes les demandes en tant qu’ensemble. L’algorithme présenté dans la partie 1.3.3du mémoire est l’algorithme de base appliqué au problème du voyageur de commerce. Ici le problème est légèrement différent. En effet, lors du problème du voyageur de commerce la matrice des distances exprime celles qui séparent les villes les unes des autres, tandis que dans le cas qui nous occupe, cette matrice exprime la distance entre les capsules libres et les demandes individuelle, telle que :
Soit OD : l’ensemble des demandes
A : l’ensemble des capsules disponibles
D : la matrice distance ayant pour élément di,j
C’est cette matrice D qui est utilisée dans les simulations. De plus l’algorithme de colonie de fourmis est dépendant de plusieurs paramètres qui ont été définis dans l’état des connaissances (Tableau 2.2).Le nombre d’itérations dépend de la complexité du problème et doit être soumis à un calibrage. Cet algorithme étant un algorithme d’optimisation qui ne renvoie pas forcément la solution optimale mais une réponse qui s’en approche. Comme pour tout algorithme d’optimisation il est nécessaire de calibrer afin d’avoir un bon compromis entre la pertinence des résultats et le temps de calcul.
Pour une matrice de distance donnée, le minimum absolu est recherché. Pour cela l’algorithme est calibré plusieurs fois et avec de nombreuses itérations avant d’arriver à un consensus de résultats. Une fois le minimum trouvé, on garde la même matrice des distances et l’algorithme est calibré pour donner des résultats en moyenne à 10% de ce résultat minimum sans jamais donner un résultat aberrant c’est-à-dire un résultat dépassant les 20% du résultat minimum. Si pour un certain nombre d’itérations l’algorithme renvoi en moyenne des résultats en dessous de 10% mais que une des simulations renvoi un résultat aberrant dépassant les 20% alors l’algorithme ne sera pas considéré comme viable. Ces critères ont été définis de façon arbitraire. Enfin à chaque fois qu’un véhicule se déplace d’un nœud à l’autre l’algorithme de Dijkstra voir Figure-A I-18 en annexe est utilisé pour calculer le meilleur trajet.
Il existe plusieurs façons de redistribuer les capsules libres et à chaque type de redistribution, un algorithme qui exécute cette redistribution. La liste des différents types de redistribution possible ainsi que leur description est présentée au Tableau 2.3.
Plusieurs algorithmes ont été utilisés afin de créer le modèle dynamique de gestion et de déplacement des véhicules afin de répondre aux besoins individuels. Le Tableau 2.4 présente une synthèse de ces algorithmes ainsi que de la fonction à laquelle ils sont attribués

Matrice Origine Destination (Matrice OD)

La matrice OD exprime une demande qui est caractérisée par un nœud « Origine » et un nœud « Destination ». Ces matrices OD sont générées aléatoirement suivant un scénario de profils des demandes. Le scénario détermine si un nœud peut être « Origine » et/ou « Destination » mais il n’y a pas de pondérations quant à la probabilité pour un nœud d’être origine ou destination. Chaque nœud, s’il est défini comme « Origine » possible, a autant de chance qu’un autre nœud d’être « Origine ». Un nœud aura un nombre différent de demandes à chaque simulation due au caractère aléatoire de la simulation. Évidemment, si un seul nœud est défini comme « Origine » possible ou « Destination » possible ce nœud le sera pour toutes les demandes. Une demande ne peut avoir la même origine que sa destination. Le modèle introduit volontairement une dimension aléatoire. C’est-à-dire qu’entre deux simulations qui ont comme même variable, même scénario et mêmes conditions initiales, la matrice OD sera différente et donc la réaction du modèle aussi. Par exemple, dans les Figure 2.3 et Figure 2.4, la répartition des nœuds origines entre deux simulations pour le scénario 4 est différente.

Table des matières

INTRODUCTION
CHAPITRE 1 ÉTAT DES CONNAISSANCES
1.1 Mobilité urbaine
1.1.1 Histoire des transports de l’après-guerre à de nos jours
1.1.2 Limites et problèmes des transports en commun et individuels
1.1.3 La situation canadienne et montréalaise
1.2 Nouvelles approches de la mobilité
1.2.1 La naissance des transports cybernétiques (ou PRT)
1.2.2 L’héritage des PRT : les projets actuels et futurs
1.3 Modèle de conception
1.3.1 Matrice Origine-Destination
1.3.2 Algorithme de Dijkstra
1.3.3 Algorithme de colonie de fourmis
CHAPITRE 2 MÉTHODOLOGIE
2.1 Modèle dynamique
2.1.1 Structure du modèle dynamique des déplacements individuels en milieu urbain
2.1.2 Algorithmes
2.1.3 Matrice Origine Destination (Matrice OD)
2.2 Paramètres, variables et critères de performance associés
2.2.1 Structure du réseau
2.2.2 Paramètres des scénarios de simulation
2.2.3 Indicateurs de performance
2.3 Scénarios
2.3.1 Profil des demandes
2.3.2 Analyse de la performance des modes opératoires
de la flotte de véhicules
CHAPITRE 3 RÉSULTATS
3.1 Construction de la matrice des distances
3.2 Calibrage de l’algorithme de colonie de fourmis
3.3 Analyse des modes de gestion des véhicules
3.3.1 Capacité
3.3.2 Intérêt d’un réseau intelligent
3.3.3 Comportement du système face à différents types de redistribution
3.4 Comparaison entre les scénarios
CHAPITRE 4 DISCUSSION
4.1 L’influence entre les capsules
4.2 Les scénarios
4.3 Application dans la réalité
4.3.1 Comparaison entre la capacité d’un PRT et d’une rame de métro
4.3.2 Possibilité d’application d’un tel système
4.3.3 Efficacité énergétique
CONCLUSION
ANNEXE I Présentation des algorithmes de utilisés dans le modèle dynamique
ANNEXE II Résultats de tous les scénarios
BIBLIOGRAPHIE

Télécharger le rapport complet