Calcul d’itinéraire multimodal et multiobjectif en milieu urbain

Une méconnaissance des réseaux

La situation est paradoxale. La plupart des personnes intérrogées répondent qu’elles abandonneraient la voiture si les transports en commun étaient mieux développées. Pourtant une part considérable de la population en France est desservie par les transports en communs et se situe à moins de deux kilomètres d’un arrêt de transports en communs (soit moins de dix minutes à vélo). Il s’agit donc bien souvent d’une méconnaissance des réseaux (« je ne savais pas qu’il y avait telle ligne »), d’un manque de volonté de mieux les connaître (« je n’ai pas envie d’apprendre par cœur l’horaire du bus »), de préjugés (« le bus c’est lent »7 ). Ainsi, très peu de personnes savent qu’il est possible de prendre un bus RATP au prix d’un simple ticket (1¤70 en juillet 2010) pour aller de l’aéroport d’Orly à Paris8 . Cette situation est encore plus criante dans le communes rurales. Ainsi le réseau des 62 lignes régulières d’autocar de la Haute-Garonne est inconnu pour la plupart des Toulousains alors qu’il permet d’accéder à pratiquement toutes les communes du département

Trop de possibilités Finalement, l’offre des transports en commun est pénalisée par sa richesse. Ainsi la RATP et la SNCF proposent cinq cartes différentes pour l’Île-de-France : réseau de bus, réseau de métro, réseau de RER et réseau de Transilien (trains de banlieue) et le réseau noctilien (bus de nuit). À celà il faut rajouter les réseaux de bus départementaux. De ce fait, l’utilisateur a tendance à se rabattre sur un seul mode de transport et n’envisagera pas les autres devant la complexité de se représenter tout le réseau multimodal. Il est donc parfaitement compréhensible que les trajets empruntés ne combinent pas plusieurs modes de transport.

 Généralités sur les graphes 

Dans un article publié en 1736, Leonhard Euler démontre qu’il est impossible d’emprunter une et une seule fois les sept ponts de Königsberg (aujourd’hui Kaliningrad). Pour cela il introduit une structure de données qui sera appelée plus tard graphe. Un graphe est une structure de données très simple utilisée dans de nombreux domaines tels que les télécommunications, la planification, l’électronique, les transports ou encore la théorie de la complexité. Généralités sur les graphes 10 Figure 1.1 Les sept ponts de Königsberg. Euler démontra qu’il est impossible de traverser une et une seule fois tous les ponts et introduisit la notion de graphe Google Scholar référence près de cinq millions d’articles comportant le mot graph dans le titre. Face à l’étendue du domaine il ne serait donc pas possible de présenter l’ensemble de la théorie des graphes. Nous nous focaliserons donc dans cet état de l’art sur le problème particulier du plus court chemin. Après avoir défini les notations, nous présenterons les principaux algorithmes en nous intéressant en particulier à leurs conditions d’applications. 

 Notations 

En simplifiant à l’extrême, un graphe définit l’existence d’une relation entre objets tels qu’une ligne entre deux stations de métro, une relation d’amitié dans un réseau social ou encore une rue entre deux carrefours. État de l’art 11 Nœuds et arcs Les objets sont appelés nœuds (nodes) ou sommets (vertices) et les relations arcs (edges) ou arêtes (links). Soit N l’ensemble des n = |N| nœuds où || désigne le cardinal d’un ensemble et A l’ensemble des m = |A| arcs. Puisqu’un arc relie toujours exactement deux nœuds (mais deux nœuds ne sont pas nécessairement reliés), on a A ⊆ N × N. G(N, A) définit donc un graphe. Figure 1.2 Les sept ponts de Königsberg représentés par un graphe. Les arcs représentent les ponts, les nœuds 1 et 2 la terre ferme et les nœuds 3 et 4 les îles Être orienté ou pas Lorsque les relations sont symétriques, le graphe est dit non-orienté. Formellement, un graphe est non-orienté lorsque ∀(u, v) ∈ A, (v, u) ∈ A. Un réseau informatique sera généralement non-orienté puisque deux ordinateurs peuvent communiquer dans les deux sens. À l’opposé, un réseau routier est orienté pour modéliser les rues à sens unique. Il est habituel (mais pas systématique) d’utiliser les termes nœud et arc pour les graphes orientés et sommet et arête pour les graphes non orientés. Poids sur les arcs Dans de nombreux problèmes, il est souhaitable de pouvoir qualifier une relation. Pour cela à chaque arc est associé un poids qui le décrit. Dans un réseau social il peut définir la nature de la relation (ami, famille, collègue) et dans un réseau routier la longueur d’une rue. Parfois le terme coût est utilisé. En associant à chaque arc ∀a ∈ A un poids ca ∈ C, on obtient un graphe G(N, A,C) qui est dit valué. Même si dans les cas les plus courants les poids sont constants, il est possible d’utiliser des fonctions pour représenter les poids. 

Représentation 

Pour représenter un graphe informatiquement, généralement deux modélisations sont utilisées. Matrice d’adjacence Une matrice M de dimension n×n représente un graphe de la manière suivante : Muv = 1 s’il existe un arc du nœud u au nœud v et 0 sinon. Plutôt que 1, il est possible d’utiliser le poids de l’arc pour marquer son existence. Si cette représentation permet de facilement tester l’existence d’un arc en O(1), obtenir l’ensemble des successeurs d’un nœud est en O(n). Enfin, la mémoire nécessaire pour stocker la matrice est en O(n 2 ). Liste d’adjacence Dans cette représentation, un vecteur de n éléments contient pour chaque nœud la liste de ses successeurs. Cette représentation nécessite donc moins de mémoire qu’une matrice d’adjacence et obtenir la liste des successeurs d’un nœud est en O(1). Lorsque le degré des nœuds est indépendant de la taille du graphe — comme dans un réseau routier — État de l’art 13 alors la mémoire nécessaire est en O(n). Cette représentation est donc préférée pour les graphes grands et peu denses.