Calcul d’itinéraires multiples et de trajets synchronisés dans des réseaux de transport multimodaux

La mobilité, usages et besoins 

Si la connaissance d’un cheminement terrestre reste encore souvent heuristique par l’utilisation de ce qui est quotidiennement appelé le sens de l’orientation, le recours à une carte s’avère souvent nécessaire. En effet, elle est un outil de l’intelligence du territoire et une mobilité informée et efficace en est sa principale motivation. Elle permet de transmettre et d’étoffer ce savoir spatial tout en proposant à son utilisateur une réponse de qualité et performante lors de son utilisation. C’est ainsi désormais que la modélisation informatique permet d’optimiser des trajets, en temps, en distance ou relativement à tout autre mesure de façon plus ou moins aisée en fonction de la calculabilité et la complexité des problèmes de cheminement posés. De façon parallèle, l’information cartographique numérique permet de fusionner la toujours grandissante quantité de moyens de transport pour l’actualiser et la restituer en une information concentrée plus simple d’accès et d’utilisation

Faut-il encore espérer que cette multimodalité apporte des solutions à des soucis de congestion des infrastructures existantes tout en faisant face à des espoirs de mobilité toujours plus ambitieux, fussent-ils irraisonnés. Car si cette montée en puissance de l’information voyageur est rendue possible par la technologie elle répond également à l’augmentation des besoins de mobilité. Elle se confronte désormais à de nouveaux usages dont les pratiques sortent des systèmes centralisés et qui posent donc de nouveaux défis en vu de leur intégration avec des modes plus classiques. En particulier parce qu’ils ne sont plus uniquement planifiables à l’avance mais s’établissent en des usages spontanés et imprévisibles.

C’est dans cette optique de promotion de déplacements efficaces mais néamoins responsables que s’inscrit cette thèse. Dans la continuité des travaux précédents menés au LAAS-CNRS [18, 26] et portés par la société MobiGIS [41], elle vise à intégrer la diversité des modes de transport actuels à des besoins de mobilité nouveau comme le covoiturage. Au delà de l’information voyageur dans des applicatifs clients, le développement d’outils d’aide à la décision dans le domaine du transport public urbain est une préoccupation tout aussi importante que le déplacement car elle le conditionne en amont. Prises par des professionnels du transport et de la cartographie, ces décisions sont partiellement basées sur des calculateurs qui ne résolvent pas le problème de façon globale mais uniquement sur des problématiques locales de déplacement. Ainsi cela offre toute latitude aux décisions métiers, politiques et de bon sens qu’il n’est pas nécessairement possible ou utile d’intéger partiellement ou en totalité dans des modèles mathématiques et numériques. Cependant, au moment de l’utilisation d’une offre de transport l’utilisateur n’est pas toujours confiant face à la machine dans les choix qui par elle lui sont imposés. Une partie du travail présenté dans ce manuscrit consiste donc à trouver des alternatives au plus court chemin dans le but de réduire cet aspect frontal à la machine par la multiplicité des choix qu’elle permet alors. Par le biais du calcul de plusieurs chemins ordonnés par leur coût, une sélection des déviations possibles pour éviter à certains usagers l’utilisation ou l’enchaînement de plusieurs modes est opérée. Dans cette optique, il est supposé dans ces travaux que la qualification de ce qui constitue une différence entre deux chemins multimodaux n’est pas à laisser au concepteur de l’algorithme mais à ses utilisateurs directs, les usagers, et indirects, les autorités organisatrices de transports, qui les mettent à disposition des premiers.

Cheminements dans les graphes 

Structure de données

Graphes

Un graphe est un objet mathématique discret établissant des relations entre un ensemble d’éléments. Il permet d’abstraire des situations dans lesquelles des liens entre composants peuvent être définis. Dans notre cas, la relation nouée entre un ensemble de positions géographiques et la façon de se déplacer de l’une à l’autre modélise les réseaux de transport, qui peuvent donc être transcrits en graphes (voir Appendice A) afin d’effectuer des calculs de cheminement dessus. Formellement, un graphe G est un triplet (V, E, γ) formé d’un ensemble V de nœuds ou sommets, d’un ensemble E d’arcs ou arêtes, et d’une relation γ : E → V×V entre V et E. Il peut y avoir plusieurs arêtes entre deux nœuds tandis que certains nœuds peuvent être déconnectés puisque reliés par aucune arête à d’autres nœuds. Dans le reste du manuscrit les ensembles V et E seront toujours finis et dans ce cas le graphe est dit fini.

De plus, si pour tout couple de sommets, l’existence d’un arc d’un nœud vers un autre implique l’existance d’un arc du deuxième nœud vers le premier alors le graphe est dit non-orienté et est alors composé d’arêtes et de sommets, autrement il est dit orienté et les ensembles V et E contiennent les nœuds et les arcs respectivement. C’est le cas des graphes de transport pour lesquels un seul sens de circulation peut exister entre certaines paires de sommets. Il est possible de construire une famille de fonctions donnant pour chaque sommet ceux qui lui sont adjacents, c’est à dire tels qu’il existe un arc de E pour lequel le couple obtenu par l’application de γ le contient. Si le sommet est le premier élément du couple il sera appelé prédécesseur et s’il s’agit du second élément il sera appelé successeur. Pour chaque sommet l’accès à ses ensembles de ses prédécesseurs et de ses successeurs est à la base de toute exploration du graphe à partir de ce sommet. La cardinalité de ces ensembles définit les différents degrés d’un sommet.

Un graphe est dit fortement connexe s’il existe un chemin entre tous ses couples de nœuds. Les graphes de transport considérés seront toujours supposés fortement connexes. En effet les problématiques de mobilité sont établies sur des éléments qui sont reliés les uns aux autres. Cependant dans la réalité, cette connexité n’est pas toujours atteinte puisque la génération de graphes de transport est sujette à des erreurs de saisies. Pour palier ce problème il est possible de retirer les nœuds qui ne sont pas connectés ou de les connecter en utilisant des projections spatiales aux nœuds ou aux arcs les plus proches. Dès lors que γ est bijective et qu’il n’existe pas d’arcs d’un sommet vers lui même, le graphe est dit simple. La notation simplifiée G = (V, E) est donc adoptée et il existe au plus un arc entre tout couple de sommets différents et aucun arc entre tout couple de sommets identiques. Nous considérerons, pour simplifier, que les graphes de transport sont des graphes simples bien qu’il puisse exister deux modes de transport différents entre deux sommets. Lorsque ce cas se présente, il est possible de créer autant de nœuds fictifs qu’il y a d’arcs entre deux sommets, de relier le sommet origine à chacun d’eux puis de les relier tous au nœud cible.

Enfin, la densité d’un graphe est donnée par le rapport du nombre d’arcs sur le nombre maximal que peut en comporter le graphe. Puisque les graphes considérés sont désormais simples et orientés le nombre maximal d’arcs qu’ils peuvent comporter est le nombre de nœuds au carré. La densité dans les réseaux de transport est en général proche de 4 car un nœud ne peut connecter que les nœuds qui lui sont voisins géographiquement.

Graphes étiquetés

Les graphes étiquetés permettent de rajouter de l’information sur chaque arc ou sommet en plus des relations que décrivent les arcs entre les sommets. Cet ajout d’information se fait par l’adjonction d’autant de fonctions que nécessaire et qui chacune donne à tout arc ou nœud une valeur dans un ensemble arbitraire. Lorsque ces ensembles sont composés de nombres la notion de graphe valué sera préférée. Par exemple sur un graphe de transport, une fonction donnera la longueur à parcourir, voire le temps qu’il faut à pieds ou en voiture, pour relier un nœud à un autre. Mais il est également possible de spécifier le mode de transport de l’arc, qu’il s’agisse d’un bus, d’un métro ou d’un arc de voirie, ce qui est une donnée d’importance dans ce manuscrit.

Chemins

Un chemin sur un graphe est une séquence d’arcs consécutifs c’est à dire tels que chaque nœud successeur soit le nœud prédécesseur de l’arc suivant, sauf pour le prédécesseur du premier arc et le successeur du dernier. Si le chemin ne passe pas deux fois par le même arc il est dit simple alors que s’il ne contient pas deux fois le même nœud, il est dit élémentaire ; tout chemin élémentaire est donc simple. Les ensembles des chemins simples et élémentaires d’un graphe sont de taille finie mais de cardinalité factorielle dans le pire des cas en fonction du nombre de nœuds et d’arcs. Lorsque les graphes sont valués, il est possible de construire une fonction de valuation d’un chemin qui prend en entrée un ensemble de fonctions de valuations du graphe, un arc et un ensemble de valeurs chacune dans un ensemble arbitraire, et qui retourne un nouvel ensemble de ces valeurs mises à jour après le passage par l’arc donné. Par exemple si le graphe dispose d’une fonction donnant le coût de chaque arc alors la fonction d’évaluation des chemins prendrait en entrée un arc, la fonction permettant de récupérer le coût d’un arc et le coût courant du chemin. La fonction d’évaluation des chemins retournera ensuite le nouveau coût mis à jour après le parcours de l’arc. Il est donc possible d’obtenir un chemin valué sur un graphe valué.

Cheminements

Les problèmes de cheminement consistent à trouver des chemins entre deux nœuds sur un graphe étiqueté ayant certaines propriétés vis à vis de fonctions de valuation de chemins. La version la plus simple est de trouver un chemin qui minimise le nombre de nœuds qu’il traverse pour aller de l’origine à la destination. En travaillant sur des graphes valués, le problème de plus court chemin classique cherche plutôt à minimiser le coût du trajet. Il est ensuite possible de complexifier à l’envie par l’ajout de contraintes et d’objectifs. Des algorithmes spécialisés peuvent être élaborés pour chaque type de problème.

Table des matières

INTRODUCTION
1 La mobilité, usages et besoins
2 Cheminements dans les graphes
2.1 Structure de données
2.1.1 Graphes
2.1.2 Graphes étiquetés
2.1.3 Chemins
2.1.4 Cheminements
2.2 Problèmes du plus court chemin
2.2.1 Algorithmes classiques
2.2.2 Algorithmes informés
2.2.3 Prise en compte de la dépendance au temps
2.2.4 Intégration de contraintes
2.3 Itinéraires synchronisés
2.3.1 Problèmes Aller-Retour
2.3.2 Problèmes de covoiturage dynamique
2.4 Chemins alternatifs
2.4.1 Méthode multi-objectifs
2.4.2 Méthode du point de passage
2.4.3 Méthode des plateaux
2.4.4 Méthode des pénalités
2.4.5 Méthode des K plus courts chemins
3 K plus courts chemins
3.1 Principes généraux des méthodes de k plus courts chemins
3.1.1 Calcul des k plus courts chemins élémentaires
3.1.2 Calcul des k plus courts chemins avec cycles
3.2 Adaptations d’algorithmes existant au cas des réseaux de transport
3.2.1 Adaptation de l’algorithme de Yen
3.2.2 Adaptation de l’algorithme de Eppstein
3.2.3 Adaptation de l’algorithme REA
3.3 Nouvel algorithme de k plus courts chemins avec cycles
3.3.1 Principe général
3.3.2 Algorithme IEA
3.3.3 Exemple illustratif de l’application de l’algorithme IEA
3.4 Introduction de procédures coupe-cycle
3.4.1 Coupe cycle pour l’algorithme REA
3.4.2 Coupe cycle pour l’algorithme IEA
3.5 Implémentations et analyses expérimentales
3.5.1 Contexte expérimental
3.5.2 Résultats et analyses
3.6 Chemins alternatifs
3.6.1 Principe
3.6.2 Exemple
3.6.3 Algorithme
3.6.4 Méthodes de sélection
3.6.5 Analyses expérimentales
3.6.6 N-grammes
3.6.7 Distance de Levenshtein
3.7 Conclusion
4 Synchronisation de trajets : application au covoiturage
4.1 Position du problème
4.1.1 Le problème 2SPSPP
4.1.2 Méthode de résolution
4.1.3 Proposition d’un algorithme générique pour le 2SPSPP
4.2 Etude de variantes du 2SPSPP
4.2.1 Origines ou destinations identiques
4.2.2 Impact de la dépendance au temps
4.2.3 Plusieurs passagers avec points de synchronisation identiques
4.2.4 Horaires de départ ou d’arrivée
4.2.5 Contrainte sur le détour du conducteur
4.3 Analyses expérimentales
4.3.1 Contexte
4.3.2 Sens de parcours
4.3.3 Contrainte de détour
4.4 Conclusion
5 Contributions et transferts industriels
CONCLUSION

Lire le rapport complet