Problème NP-Complet et algorithme de Dijkstra

Problème NP-Complet et algorithme de Dijkstra 

Il faut d’ores et déjà préciser que dans la littérature scientifique, l’algorithme de Dijkstra est critiqué pour sa complexité polynomiale, associée au fait qu’il résout un problème NP-Complet. Cela signifie que la vérification des solutions est assez efficace, mais que la recherche de solutions l’est bien moins ; l’efficacité correspondant à la rapidité d’exécution du calcul. Pour ce type de problème, le temps d’exécution de l’algorithme est exponentiel à la taille des données. Ainsi, Il peut vite devenir laborieux de résoudre des problèmes sur des graphes de grande taille avec Dijkstra (Dib et al., 2015).

Il existe plusieurs méthodes pour atténuer voire contourner cet inconvénient, mais elles ne constituent pas l’objet de ce projet. C’est pourquoi les modèles qui seront utilisés resteront simples.

Prise en compte de l’intermodalité

La question du plus court chemin pour des déplacements intermodaux est traitée par des articles scientifiques depuis les années 1990 (Dib et al., 2015). On distingue deux manières d’aborder le sujet : la première vise à minimiser le nombre de changements de mode, elle est surtout pertinente dans le transport de marchandises, sujets à des coûts et risques d’endommagement lors des transbordements. Cette approche peut tout de même être appliquée pour les transports collectifs, par exemple pour les personnes à mobilité réduite, pour lesquelles les changements peuvent s’avérer pénibles. La seconde manière vise à minimiser le temps de trajet, et est appliquée dans les transports collectifs.

Une grande partie des articles visent à proposer de nouveaux algorithmes de plus court chemin, pour résoudre le problème de l’intermodalité et celui de NP-Complexité de Dijkstra. Cependant, l’approche consiste à modifier les graphes utilisés, donc les données d’entrée, avant d’y appliquer ces nouveaux algorithmes. Il est ainsi possible d’appliquer Dijkstra dans la plupart de ces graphes modifiés.

Certaines méthodes introduisent des arcs de correspondance dans les graphes utilisés. Ces arcs relient des nœuds sur des modes de transport différents et leur coût d’emprunt correspond au temps de latence induit par l’intermodalité. Au niveau macroscopique, ces arcs relient les mêmes espaces par exemple pour un métro, la même station. Cependant à plus petite échelle, ils relient deux espaces distincts, dans le cas d’un métro, les quais d’une ligne et les quais d’une autre ligne dans une même station (Di Febbraro et al., 1997 ; López et Lozano, 2014).

Il est possible de représenter les arcs de correspondance dans un graphique en 3-D: Chaque mode de transport est représenté dans un plan parallèle aux autres, les arcs de correspondance les lient dans la 3e dimension, aux endroits où les correspondances sont possibles. Le métro est un bon exemple pour cette représentation : le niveau de la rue représente la marche et le niveau -1 le métro, les stations permettent de faire le lien entre les deux.

L’hypergraphe est une autre manière d’inclure les temps de latence. Celle-ci ne complexifie pas le graphe en y rajoutant d’autres arcs. Le graphe est divisé en soushypergraphes indépendants reprenant chacun une partie des nœuds. Certains nœuds peuvent appartenir à plusieurs soushypergraphes, permettant ainsi de les lier. Un coût est associé au changement de soushypergraphes.

Dans une application intermodale, les sous-hypergraphes représentent les différents modes de transports. Les nœuds communs à plusieurs sous-hypergraphes représentent les endroits où il est possible d’effectuer des correspondances d’un mode à un autre. Le coût de changement d’un soushypergraphe à un autre correspond au temps de latence (Dib et al., 2015).

Seule l’approche de Ziliaskopoulos et Wardell (2000) s’affranchit complètement de la notion d’arc de correspondance. Elle inclut les temps de correspondance dans les nœuds, en ajoutant le temps de latence au temps de trajet si le mode d’entrée du nœud est différent de celui de sortie (López et Lozano, 2014). Cette méthode demande un algorithme spécifique, Dijkstra n’étant pas applicable.

Les modélisations des problèmes d’intermodalité qui ajoutent des arcs de correspondance ou bien représentent les problèmes sous forme d’hypergraphe ne font que modifier les données d’entrée des algorithmes de plus court chemin, qu’il s’agisse ou pas de celui de Dijkstra. Dib et al. (2015) le démontre bien en utilisant Dijkstra, un algorithme génétique et un algorithme de variable neighborhood search (VNS) pour le même graphe. Les résultats montrent que les deux autres algorithmes sont plus performants que Dijkstra en termes de temps de calcul (d’un facteur 700 et 515, respectivement) mais que les résultats sont très similaires, ceux trouvés par Dijkstra étant légèrement plus exacts. L’approche de Ayed et al. (2011), basé exclusivement sur Dijkstra dans un graphe utilisant des arcs de correspondance, tire les mêmes conclusions : les résultats de l’algorithme sont exacts mais le temps de calcul particulièrement long (636 secondes pour un réseau composé de 4000 nœuds, 15 000 arcs et utilisant 5 modes de transport) (López et Lozano, 2014).

Cet état de l’art permet de conclure qu’il est possible d’utiliser l’algorithme de Dijkstra pour déterminer le plus court chemin intermodal, en modifiant les données d’entrée de cet algorithme. Le temps de calcul reste plus élevé que pour d’autres approches avec des algorithmes différents, cependant les résultats sont tout aussi exacts.

Prise en compte de réseaux dynamiques et de la dépendance au temps

Les algorithmes de plus court chemin ont été conçus pour des situations statiques et pour des modes de transport privés, non dépendants du temps. C’est-à-dire pour des trajets dont le coût d’emprunt d’un arc est constant, et dont les arcs peuvent être parcourus à n’importe quel instant. Cependant, les situations étudiées ne rentrent pas dans ce cadre, et demandent alors aux algorithmes de plus court chemin de s’affranchir de ces contraintes. Tout d’abord, les algorithmes de plus court chemin doivent tenir compte de temps de parcours dynamiques. Ceux-ci sont souvent plus importants en heure de pointe que le reste du temps, à cause de la congestion automobile. Les transports en commun en site propre (métro, tramway)  ainsi que la marche ou le vélo sont moins soumis à ces effets que la voiture ou les bus. A partir de données et d’apprentissage automatique, il est possible de créer des références de temps de parcours relativement fiables qui dépendent des heures de la journée. Le résultat est un graphe en 3 dimensions, le temps représentant cette 3e dimension, les coûts d’emprunt des arcs évoluant selon l’heure. Cela ne modifie pas l’algorithme de Dijkstra, mais vient rajouter des données d’entrée et demande une heure de départ pour faire tourner l’algorithme (Di Febbraro et al., 1997). L’utilisation des algorithmes de plus court chemin pour les transports collectifs implique également de prendre en compte une contrainte propre à ces derniers : la dépendance au temps. Contrairement aux modes de transport privés tels que la voiture, le vélo ou la marche, pour lesquels les trajets peuvent avoir lieu n’importe quand, les transports collectifs sont tributaires de leurs horaires ; les trajets ne peuvent avoir lieu seulement à des instants précis. Des travaux sur cet aspect ont démontré dès les années 60 que l’algorithme de Dijkstra pouvait prendre en compte cette dépendance au temps, en utilisant des graphes temporisés. Ces graphes temporisés sont composés d’arcs ne pouvant être parcourus qu’à certains instants, ceux des trajets des transports collectifs (Cooke et Halsey, 1966 ; Dib et al., 2015). Cet aspect évolue aujourd’hui avec des lignes de transports en commun pour lesquelles le passage des véhicules est basé sur une fréquence de passage plutôt qu’un horaire, ainsi que l’intégration de données en temps réel, qui permettent d’accroitre la précision des temps d’attente et de trajet, et  ainsi les informations présentées à l’usager. Ces problématiques sont traitées dans et hors du contexte de l’intermodalité, dans des articles tels que López et Lozano (2019).

Table des matières

Introduction
1. Présentation de l’objet de recherche
2. Définitions
3. Enjeux
État de l’art
1. Problème NP-Complet et algorithme de Dijkstra
2. Prise en compte de l’intermodalité
3. Prise en compte de réseaux dynamiques et de la dépendance au temps
Problématique et hypothèses
1. Problématique
2. Hypothèses
Modèle et algorithme
1. Transformation du graphe
2. Observation des effets
3. Premiers résultats
4. Premières conclusions
Application au cas d’étude et résultats
1. Choix du cas d’étude
a. Des réseaux très développés
b. Des réseaux en étoile
c. Des réseaux de petite taille avec peu de correspondances
d. Des réseaux de petite taille très connectés
2. Application
3. Résultats et discussion
Conclusion
Bibliographie
Annexes
Algorithme de Dijkstra
Algorithme de création des arcs de correspondance

Télécharger le rapport complet