Les methodes de modification de l’algorithme de dijkstra

Définition des termes importants

Dans le cadre de notre recherche, les notions d’intermodalité et de multimodalité sont centrales. Souvent confondues, il parait nécessaire de rappeler leur distinction. L’intermodalité se définit comme « L’utilisation flexible et la combinaison de différents modes de transport en un seul voyage » . Il s’agit, par exemple, d’emprunter un bus puis un métro lors d’un seul et même trajet. Néanmoins, l’utilisation de deux métros différents lors d’un même voyage est également considéré comme de l’intermodal. Le transport multimodal, lui, correspond à l’existence de plusieurs moyens de transport pour déplacer des usagers d’une origine à une destination. Par exemple, à Paris, pour aller de Bastille à Gare de Lyon, il est possible de prendre le métro ou le bus qui desservent, tous les deux, ces deux stations.

La notion de latence est elle aussi centrale dans ce projet. Ce mot provient du latin “latens“ qui signifie caché ou secret. Communément, la durée de latence désigne l’intervalle de temps entre une action et la réponse à cette action. Dans le domaine des transports, ce temps de latence est également appelé temps de correspondance. En d’autres termes, c’est la durée qui s’écoule lorsque l’on passe d’un mode de transport à un autre au cours d’un voyage. Enfin, il parait important de rappeler que notre étude porte sur les déplacements domicile-travail. Ces derniers constituent un type de mobilité regroupant des déplacements quotidiens liés à l’exercice d’une activité professionnelle. Néanmoins, les résultats de cette étude seront applicables à plusieurs types de déplacement.

Les graphes : une représentation des réseaux

Très souvent, on formalise les réseaux de transport sous forme de graphe. D’après Dr Jean-Paul Rodrigue « Un graphe est une représentation symbolique d’un réseau. Il s’agit d’une abstraction de la réalité de sorte à permettre sa modélisation. ». Un graphe est un ensemble fini de points, appelés nœud (ou sommet), qui peuvent être reliés entre eux par des arcs (ou arrête). Des poids, aussi appelés coûts, peuvent être affectés aux arcs. Cela permet de matérialiser un phénomène comme la durée de trajet entre deux sommets, la distance, ou encore la vitesse par exemple.

L’algorithme de Dijkstra

Comme nous l’avons précédemment mentionné, l’algorithme de Dijkstra permet de répondre au problème de plus court chemin. Celui-ci repose dur « le prince d’exploration à partir du meilleur prédécesseur visité » et permet de calculer le plus court chemin depuis un sommet de départ vers tous les autres sommets du graphe. Pour cela, il s’appuie sur le principe que si le plus court chemin reliant le sommet de départ S0 à un autre sommet Sn passe par les sommets S1, S2, S3 … Sk, alors, ce même chemin est également le plus court chemin entre le S0et les sommets S1, S2, S3 … Sk . Pour cela, on part d’un sommet et on enregistre la valeur du successeur le plus proche. On réitère l’opération en comparant la valeur enregistrée avec celle du prochain sommet augmenté de la longueur de l’arc qui les relie. Si celle-ci est inferieure à la valeur enregistrée, alors elle devient à son tours la valeur stockée. Dans ce cas, on note le nom du sommet dit « père », pour pouvoir reconstituer le chemin dans le sens inverse.

Les méthodes de modification

Plusieurs études ont été développé dans le but de modéliser un réseau de transport multimodal dépendant du temps en utilisant l’algorithme de Dijkstra. Comme c’est le cas pour notre étude, certaines d’entre elles ont uniquement changé les données d’entrées. Néanmoins, après avoir analysé plusieurs articles, on se rend compte qu’il existe principalement deux grandes méthodes qui reposent sur le même principe de transfert. Ainsi, il nous a paru plus judicieux de confronter et comparer ces deux méthodes qui sont les suivantes :
– La méthode des graphes de transfert
– La méthode du super-réseau

L’approche du graphe de transfert est une manière de résoudre le problème de plus court chemin dans un réseau multimodal dépendant du temps. Dans leurs recherches, les auteurs (Ayed and al) ont mentionné ce graphe comme un résumé de réseau multimodal de transport. Dans un premier temps, cette méthode consiste à diviser le réseau multimodal en plusieurs réseaux monomodaux. Dans un second temps, il s’agit de relier ces différents réseaux entre eux pour atteindre un simple réseau unimodal qui peut donc être résolu grâce au problème de plus cours chemin. Le modèle est constitué d’un ensemble de nœuds, d’un ensemble d’arcs, d’un ensemble d’intervalles de temps et d’un ensemble de modes (métro, train, bus … ). Deux nœuds sont reliés par un arc si et seulement si il existe un mode de transport qui lesrelie. On appelle alors graphe de transfert un ensemble fini de graphes monomodaux reliés entre eux par un ensemble fini d’arcs virtuels. Dans ce cas, les nœuds des arcs virtuels sont appelés nœuds de transfert. En résumé, un graphe de transfert est donc composé de plusieurs graphes de réseaux monomodaux reliés entre eux par des arcs. On définit alors un transfert comme un arc connectant deux composants entre eux. Une fois le graphe mis en place, il suffit d’utiliser l’algorithme de Dijkstra , que nous avons précédemment détaillé, pour trouver le plus court chemin.

La méthode d’Ayed et al présente un avantage particulier. En effet,s’il y a des perturbations tel que des embouteillages ou des travaux pour un mode de transport, la représentation ne sera pas impactée globalement mais localement car tous les modes de transport sont séparés dans desréseaux unimodaux. Cette méthode permet donc de mettre à jours les données de chaque réseau de transport sans modifier le modèle. Néanmoins, les informations concernant les transferts et les intervalles de temps possibles étant stockés dans des structures de données, ce modèle nécessite le stockage d’une grande quantité d’informations. Par ailleurs, plus le réseau est grand, plusle graphe sera important. On peut donc imaginer que, selon sa taille, représenter un système de transport existant peut s’avérer relativement compliqué.

On retrouve cette notion de distinction des graphes dans la méthode de ‘super-réseau . Cette approche distingue les réseaux privés des réseaux publics. Elle propose une représentation et une notation spécifique qui se divise en deux types de nœud : les nœuds physique qui représentent les stations et les nœuds d’évènements qui, eux,représentent les évènements de départ et d’arrivée (horaires).

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela chatpfe.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

INTRODUCTION
I. LES METHODES DE MODIFICATION DE L’ALGORITHME DE DIJKSTRA
1. Définition des termes importants
2. Les graphes : une representation des réseaux
3. L’algorithme de Dijkstra
4. Les méthodes de modification
5. Discussion
II. PROBLEMATIQUE ET HYPOTHESE
III. METHODE
1. Conversion du graphe
2. Les éléments permettant la conversion
3. Le choix des chemins à comparer
IV. APPLICATION ET RESULTATS
1. Modèle théorique
2. Modèle théorique : les durées de déplacement
3. Modèle théorique : les changements de plus courts chemins
4. Les premières conclusions
5. Application sur un reseau existant
a) Choix d’un cas d’étude
b) Application au réseau parisien : Les durées de déplacement
c) Application au réseau parisien : Les plus courts chemins
V. CONCLUSION
VI. BIBLIOGRAPHIE
VII. ANNEXES