circle-loader

Quels sont les prochains horaires de passage de mon transport ? Quel est le chemin le plus rapide pour me rendre de mon domicile à mon lieu de travail ? Voici deux exemples de questions auxquelles les développeurs de « Journey Planner » ont eu à répondre. Pour ce faire, les développeurs s’appuient sur des algorithmes de calculs d’itinéraires, avec des spécificités différentes, mais permettant tous d’améliorer l’expérience de planification de trajet.

Chaque seconde, ce sont pas moins de 77 personnes qui prennent les transports en commun en France. Aujourd’hui, de nombreuses solutions permettent de nous déplacer en ville : Google Maps, OpenTripPlanner ou encore nos « API Lyko« . À l’ère du digital et du Big Data, ces applications se doivent d’être de plus en plus performantes. Elles sont donc capables de nous indiquer des itinéraires précis tout en prenant en compte les contraintes de temps de l’utilisateur. Que ce soit en bus, en métro ou bien en tramway, il existe bien des manières de se déplacer. Un volume de données exponentielles navigue à travers Internet et nous facilite ces déplacements. Zoom sur les 4 principaux algorithmes de calculs d’itinéraires.

Le premier algorithme de calculs d’itinéraires : Dijkstra

Edsger Dijkstra — Wikipédia
Photo de Edsger Dijkstra

En 1959, Edsger Dijkstra, célèbre mathématicien et pionnier de l’informatique a publié dans un article faisant seulement 2 pages, ce qui constituera le premier algorithme de calculs d’itinéraires. Cet algorithme répond à un problème simple : déterminer le chemin le plus court dans un grapheen partant d’un point x jusqu’à un point y. Il est à noter que tous les sommets de ce graphe sont interconnectés (à la manière d’un réseau de transport), et que chacun des segments possède un poids représenté par un nombre.

Compréhension avec exemple

algorithme-de-dijkstra
© maths-cours.fr

Voici un modèle de ce graphe . Pour mieux comprendre le principe de cet algorithme, nous allons partir sur un exemple : Trouver le chemin le plus court au départ du point S à M. Pour ce faire, nous allons devoir créer un sous-graphe. Il classera les différents sommets par ordre croissant, de leur distance minimale au sommet de départ. Nous calculerons à la fin, la distance totale du chemin. Celle-ci correspondra à la somme totale des poids des segments empruntés (il est important de noter que S vaut 0).

Pour comprendre au mieux cet exemple, nous construisons un tableau. En effet, ce tableau regroupe tous les sommets du graphe, et nous aidera à visualiser le processus algorithmique. Ce processus s’effectue tour par tour.

Tour 0

Le sommet S, étant le sommet de départ, il peut être sauvegardé dans le tableau, car nous n’y passerons plus.

TourSTLNEM
Tour 00
.
.
.
.
.

Tour 1

Nous remarquons 4 sommets connectés à S, le sommet T à 8 de distance, le sommet L à 5 de distance, le sommet N à 8 de distance, et enfin le sommet E à 10 de distance. Dans un tableau, nous allons donc enregistrer ces différents sommets représentés par un chiffre (poids de la distance) et une lettre (représentant le point d’origine de la connexion).

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.
.
.
.

Nous choisissons donc le sommet L. En effet, c’est le segment hors du sous-graphe qui a la distance minimale (5). Nous n’y reviendrons pas, nous pouvons donc le sauvegarder dans le tableau.

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S0 + 5
..
..
..

Trois sommets sont voisins du sommet L: N, E et M. Les distances relatives à ces sommets par rapport au sommet initial S sont 7, 13 et 12 (en prenant en compte la valeur de la distance précédente qui est 5).

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S 7L 13L 12L
..
..
..

Tour 2

En regardant le tableau, nous pouvons voir que la distance la plus courte est bien le sommet N situé à distance 7 du sommet S. L’algorithme va donc choisir le sommet N, puis l’enregistrer dans le tableau. Nous ne passerons donc plus par ce sommet.

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S 7L 13L 12L 
Tour 2.. 7L5 + 2
...
...

Le sommet M est le seul voisin du sommet N et il n’est pas issu du sous-graphe. Il est situé à distance 11 du sommet S initial (en prenant en compte la valeur de la distance précédente qui est 7).

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S7L13L12L
Tour 2..7L11N7 + 4
...
...

Nous pouvons donc sauvegarder le sommet M dans le tableau.

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S7L13L12L
Tour 2..7L11N
....
....

Tour 3

La particularité de Dijkstra est qu’il va parcourir tous les points d’un sommet de son graphe ainsi que toutes les connexions. Dans cet exemple, on se rend compte que le problème n’est pas encore tout à fait résolu, car nous n’avons pas parcouru les connexions depuis le sommet T. En effet, le sommet T est connecté à un seul point : E. Celui-ci est situé à distance 12 du sommet initial S, on le rajoute donc à notre tableau.

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S7L13L12L
Tour 2..7L11N
Tour 3.8S..12T.
....
....

Un seul point est connecté directement avec le point E, le point M. Il est situé à distance 22 du sommet S.

TourSTLNEM
Tour 00
Tour 1.8S5S8S10S
.5S7L13L12L
Tour 2..7L11N
Tour 3.8S..12T.
...12T22E
....

Conclusion

Le problème posé au départ est donc résolu. Nous sommes ainsi arrivés au sommet M à partir de S en passant par le chemin le plus court ! Pour répondre à ce problème, il nous suffit de reprendre le tableau en le parcourant de la fin au début. Nous nous plaçons donc sur la colonne M. Quel est le plus petit poids pour arriver à M ? C’est 11N ! Ainsi nous pouvons remonter : le plus petit poids de N est 7L, le plus petit poids de L est 5S et le plus petit poids de S ? C’est notre point de départ. En inversant notre tableau, on retrouve enfin le chemin le plus court : S -> L -> N -> M.

Pour aller plus loin

Voici une vidéo explicative très complète (en anglais) qui vous permettra de comprendre plus en détail, le fonctionnement des algorithmes de calculs d’itinéraires et plus spécifiquement celui de Dijkstra.

RAPTOR, l’algorithme qui en a sous le capot

RAPTOR ou de son nom complet RoundbAsed Public Transit Optimized Routeur a été décrit en 2012 par Daniel Delling dans un article de Microsoft. Cet algorithme s’est avéré rapidement populaire, et s’est intégré à des planificateurs de voyages tels que OpenTripPlanner. En effet, cet algorithme de calculs d’itinéraires offre des résultats tout à fait surprenants en termes de performance. Par exemple, il est capable de calculer tous les trajets possibles entre deux emplacements aléatoires du réseau de Londres (20 000 arrêts et 5 millions de départs quotidiens) en seulement 8 millisecondes !

journey-planner-open-trip-planner
© researchgate

Mais comment s’y prend t-il ?

Le document de Daniel Delling présente plutôt bien l’idée de cet algorithme. En effet, dans un premier temps, pour chaque trajet donné (d’un point A à Z), RAPTOR le catégorise en itinéraire, en prenant en compte le chemin qu’il suit. Dans un second temps, pour chaque itinéraire on calcule l’heure d’arrivée au plus tôt pour chaque arrêt. Enfin, après avoir exploré tous ces itinéraires, on enregistre les résultats sous forme de tours (rounds), et on passe au suivant. Avec cette étape, RAPTOR se rapproche assez de la logique de l’algorithme de Dijkstra, vu dans l’exemple précédent.

algorithme-raptor-rounds
© ljn.io

Si nous prenons l’exemple ci-dessus, on retrouve un itinéraire de la station A à la station C sur un service direct. L’heure d’arrivée à la station C sera donc à 12:00. Au deuxième tour, on remarque que ce temps d’arrivée a été amélioré. En effet, l’algorithme nous propose directement de se rendre à la station B pour prendre un train, pour finalement arriver à la station C à 11:00. L’algorithme fonctionne pendant tout le processus d’amélioration. Une fois que tous les itinéraires ont été vérifiés et que l’heure d’arrivée ne peut plus être améliorée, le mécanisme s’arrête et la requête se termine.

Il est important de rappeler que RAPTOR fonctionne par cycle d’amélioration de l’heure d’arrivée. À chaque début de tour, il examine les arrêts. Si l’heure d’arrivée à ces arrêts a été améliorée par le tour précédent, il va explorer les arrêts traversés par les itinéraires.

Pour aller plus loin

La compréhension de cet algorithme peut être assez compliquée. Néanmoins si vous souhaitez en savoir plus sur les algorithmes de calculs d’itinéraires , n’hésitez pas à consulter l’article de Microsoft expliquant entièrement le processus algorithmique. De plus, l’article de Linus Norton a fortement inspiré mon explication de l’algorithme RAPTOR.

L’algorithme d’analyse de connexion

En 2013, 54 ans après la publication de l’algorithme de Dijkstra, Julian Dibbelt, Thomas Pajor, Ben Strasser et Dorothea Wagner présente l’algorithme d’analyse de connexion dans l’article Intriguingly Simple and Fast Transit Routing. Il est connu pour faire partie des algorithmes de calculs d’itinéraires les plus performants. Il a l’avantage d’être plus simple à comprendre et à mettre en place que RAPTOR.

Comment ça marche ?

Il ne suffit pas de beaucoup de lignes pour intégrer l’algorithme de connexion. Le CSA (Connection Scan Algorithm) se contente de parcourir une table horaire (précalculée) correspondant à des connexions. En effet, une possibilité de trajet entre deux stations est représentée par une connexion. Elle ne retiendra donc que la solution optimale en termes de temps de trajet. La table horaire que le CSA va parcourir doit être, en amont, triée par date de départ croissante.

Voici un exemple d’une table horaire :

Station de départStation d’arrivéeHeure de départHeure d’arrivée
AB01
BD12
AB23
BC34
AB45
AB56
BD56
BC67

On remarque qu’elle est composée d’une colonne :

  • Station de départ
  • Station d’arrivée
  • Heure de départ
  • Heure d’arrivée

et de 9 connexions représentées par les lignes de ce tableau.

L’objectif est de se rendre d’un point de départ x à un point d’arrivée y en partant à l’heure t0. Pour cela, nous allons parcourir cette liste de connexion en considérant l’heure et la station d’arrivée, si elles sont optimales nous les conservons.

Compréhension avec exemple

En partant de l’exemple de la table horaire ci-dessus, imaginons vouloir rejoindre C depuis A, en partant à l’heure 5.

Nous détaillerons cet exemple à l’aide d’un tableau représenté ci-dessous :

StationABC
Heure de départ5
ConnexionN / A

Ce tableau est composé des différentes stations de la table horaire, des heures de départ associées à ces stations et des connexions établies. Nous partons de la station A à l’heure 5. Il n’y a donc pas de connexion au départ.

Commençons par parcourir la table horaire du début. Les lignes dont l’heure de départ est plus petite que 5 ne sont pas prises en compte, nous les ignorons.

Nous arrivons donc à la connexion (A, B, 5, 6) qui entre dans nos critères.

En effet, l’heure de départ de cette connexion (5) est égale à l’heure de départ de A (5 ≤ 5). Nous mettons donc à jour le tableau :

StationABC
Heure de départ56
ConnexionN / A(A, B, 5, 6)

Passons donc à la connexion (B, D, 5, 6). Elle ne correspond pas à nos critères horaires. En effet, l’heure de départ de cette connexion (5) est plus petite que l’heure de départ de B (enregistrée au-dessus), qui est de 6.

Dernière étape

Enfin, passons à la dernière ligne de la table horaire avec la connexion (B, C, 6, 7). Cette connexion entre parfaitement dans nos critères horaires. En effet, le point de départ de cette connexion est le point B, à l’heure 6. Elle est la même que celle de la station B que nous avons enregistrée plutôt.

Mettons à jour le tableau.

StationABC
Heure de départ567
ConnexionN / A(A, B, 5, 6)(B, C, 6, 7)

La table horaire a été entièrement parcourue. De ce fait, l’algorithme s’arrête. Pour obtenir le trajet souhaité, il suffit de parcourir le tableau à partir de la destination. C’est-à-dire, à partir de C. On retrouve la connexion (B, C, 6, 7). Il suffit maintenant de chercher l’entrée associée au départ de la connexion, ici B. On trouve (A, B, 5, 6) comme point d’entrée de notre connexion et notre point de départ. Nous avons terminé la recherche.

On peut ainsi retrouver le trajet à parcourir :

  1. (A, B, 5, 6)
  2. (B, C, 6, 7)

L’algorithme de connexion nous a donc permis de répondre au problème initial.

L’exemple présenté ci-dessus est basé sur un petit nombre de stations, ce qui le rend assez simple à comprendre et résoudre. Néanmoins, il faut savoir que cet algorithme possède une complexité proportionnelle au nombre de stations étudiées.

Pour aller plus loin

Si vous souhaitez aller plus loin dans la compréhension des algorithmes de calculs d’itinéraires n’hésitez pas à consulter l’article original.

L’algorithme de modèle de transferts

L’algorithme de modèle de transferts a été développé en 2010, au bureau d’ingénierie de Google à Zurich en Suisse. Il a été mis au point par la chercheuse Hannah Blast au côté d’un certain nombre d’ingénieurs de Google. Cet algorithme dispose d’une plus grande performance de calcul comparé aux autres algorithmes existants. Il est d’ailleurs suffisamment rapide pour mettre à jour le résultat d’une recherche, pendant que vous faites glisser les points d’extrémité de deux arrêts sur Google Maps.

Un concept simple

Le concept de base de l’algorithme de modèle de transferts est plutôt simple à comprendre. Dans un premier temps, prenons toutes les stations de la ville de Londres, pour chacun de ces arrêts l’algorithme précalculera toutes les possibilités de trajets entre elles. Ensuite, il va stocker chacun de ces trajets sous forme de transfer patterns, autrement dit, il va stocker tous les transferts pour un trajet x à y en une base de données. Par exemple, pour un trajet de A à B, on va stocker :

A, C, D, B
A, E, B
A, C, B
etc...

Au moment de la recherche entre un point x et y, on récupère tous les patterns correspondants entre x et y. Puis, pour chaque pattern, on récupère les horaires entre chaque pair de stations constituant ce pattern. Et enfin, pour chaque pattern calculé avec les horaires, on prend celui qui arrive le plus tôt.

Afin de comprendre plus en détail le processus algorithmique, voici une explication par étape.

Etape 1

Nous supposons qu’au préalable, nous possédons le maximum de trajet possible pour un territoire donné. Par exemple pour la ville de Londres cela correspondrait à des millions de trajets précalculés.

Etape 2

L’approche initiale de l’algorithme serait que pour chaque trajets x et y, nous stockerons en base de données ces modèles de transferts.

Prenons un trajet allant de A à K. Il contiendra les modèles suivants :

A, C, D, K
A, D, E, K
A, D, K
A, E, C, K

Imaginez maintenant le même type de transfer patterns pour tous les trajets d’un territoire donné.

Une fois les modèles de transferts stockés en base de données, ils seront facilement accessibles et réutilisables au moment de la recherche d’itinéraire. Mais comment peut-on réutiliser ces modèles ?

Etape 3

Au moment de la recherche de trajet, le passager aura la possibilité d’utiliser les modèles de transferts présentés ci-dessus afin d’atteindre sa destination. Tous les modèles correspondant au trajet de A à K seront donc récupérés et traités afin de répondre à la demande. Pour rappel, voici notre modèle :

A, C, D, K
A, D, E, K
A, D, K
A, E, C, K

Etape 4

Néanmoins, récupérer seulement les modèles ne suffit pas. En effet, l’algorithme va passer par une phase de traitement des modèles. Pour cela, chacun d’eux sera transformé en une liste de voyages. L’algorithme traite cette liste de transferts en une liste de paires d’origine et de destination, représentant ainsi les différentes étapes du voyage.

Prenons les modèles de transferts dans la liste ci-dessus.

Premièrement, pour A -> C -> D -> K, la liste de pairs serait:

[A, C], [C, D], [D, K]

Ensuite, pour A -> D -> E -> K, la liste de pairs serait:

[A, D], [D, E], [E, K]

Après cela, pour A -> D -> K, la liste de pairs serait:

[A, D], [D, K]

Enfin, pour A -> E -> C -> K, la liste de pairs serait:

[A, E], [E, C], [C, K]

Après avoir transformé nos modèles de transferts en une liste de pairs, l’algorithme récupère la liste des horaires correspondant à chacune d’elles :

A->C                 C->D                  D->K 
9:00, 9:20           9:20, 9:50            9:40, 10:10 
10:00, 10:20         10:20, 10:50          10:40, 11:10 
11:00, 11:20         11:20, 11:50          11:40, 12:10
12:00, 12:20         12:20, 12:50          12:40, 13:10
13:00, 13:20         13:20, 13:50          13:40, 14:10
14:00, 14:20         14:20, 14:50          14:40, 15:10
 A->D                 D->E                  E->K  
 8:50, 9:20          10:00, 10:20           10:30, 11:00
11:00, 11:20         11:10, 11:30           11:30, 12:00
12:00, 12:20         12:10, 12:40           12:30, 13:00
12:30, 12:50         13:10, 13:40           13:30, 14:00
13:00, 13:20         14:40, 15:00           14:30, 15:00
14:00, 14:20         15:20, 15:30           15:30, 16:00
 A->D                 D->K                   
 8:50, 9:20           9:40, 10:10             
11:00, 11:20         10:40, 11:10           
12:00, 12:20         11:40, 12:10           
12:30, 12:50         12:40, 13:10           
13:00, 13:20         13:40, 14:10           
14:00, 14:20         14:40, 15:10           
A->E                 E->C                   D->K
10:00, 10:30         10:10, 10:40            9:40, 10:10
11:00, 11:30         10:50, 11:20           10:40, 11:10
12:00, 12:30         11:40, 12:00           11:40, 12:10
13:00, 13:30         12:20, 13:00           12:40, 13:10
14:00, 14:30         13:20, 14:00           13:40, 14:10
15:00, 15:30         14:20, 15:00           14:40, 15:10

Etape 5

Comme nous venons de le voir, l’algorithme a construit un modèle de transferts pour chaque trajet. Ce modèle correspond à tous les arrêts sur lesquels le passager aura potentiellement besoin de s’arrêter. Par la suite, nous avons transformé ce modèle en une liste de paires d’origine et de destination. Enfin pour chacune de ces paires, nous lui avons attribué une liste d’horaires.

Que nous restent-ils donc à faire ? La dernière étape consiste à récupérer le modèle dont les horaires sont les plus tôt.

Si nous jetons un œil aux tables horaires ci-dessus, on remarque que deux modèles de transferts ont une paire qui désigne son heure d’arrivée à 10:10. Ce qui semble être l’heure d’arrivée la plus tôt à destination de K parmi tous les modèles présents. Néanmoins pour le modèle A->E->C->K, les premiers horaires de la deuxième paire, E->C sont de : 10:10, 10:40. En effet, elle ne précède pas correctement l’heure la plus tôt désignée au-dessus. On ne retient donc pas ce modèle. Le modèle au-dessus, quant à lui, possède deux paires donc les horaires se succèdent correctement pour arriver le plus tôt à 10:10. Lors de la recherche de l’utilisateur, le modèle récupéré sera donc : A->D->K.

Les horaires correspondants sont: 8:50, 9:20 -> 9:40, 10:10

Pour aller plus loin

Le modèle de transferts est l’algorithme de calculs d’itinéraires le plus rapide. Il permet de récupérer des résultats en temps réel. Néanmoins cette approche « par paires » à ces limites. En effet, lorsqu’il s’agit de calculer des itinéraires pour des grandes villes, pour un pays, voir un continent entier, cela s’avère beaucoup coûteux. De plus, elle présente des limites au niveau des connexions longues distances (Paris – Madrid, par exemple). Pour répondre à ce problème, une variante de l’algorithme de modèle de transferts a été créée : l’algorithme de modèle de transferts scalable. Pour plus d’information à ce propos, n’hésitez pas à consulter cet article.

L’article original présentant l’algorithme est également intéressant à étudier si vous souhaitez aller plus loin dans la compréhension des algorithmes de calculs d’itinéraires.

Finalement, nous avons vu une manière particulière de stocker les modèles de transfert, permettant par la suite d’accélérer les requêtes en temps réel. Néanmoins, il existe une autre technique, plus complexe, mais qui permet d’utiliser moins de mémoire de stockage : l’utilisation de cycles acycliques.

Classification des algorithmes de calculs d’itinéraires

À propos de Lyko et de ses algorithmes de calculs d’itinéraires

Chez Lyko, nous avons développé notre propre calculateur de trajets intermodaux. Bien évidemment, chacun des algorithmes présentés au-dessus possède ces limites. Il a donc été nécessaire de nous baser sur un algorithme « fait-maison« , regroupant l’algorithme de Dijkstra et l’algorithme d’analyse de connexion (Connexion Scan Algorithm – CSA en anglais).

Le mélange de ces deux algorithmes nous a permis de développer un calculateur d’itinéraire performant et peu gourmand en ressources.

À vous de jouer!

Dans cet article, je viens de vous présenter, les principaux algorithmes de calculs d’itinéraires de transports en commun. Il existe cependant de nombreux autres algorithmes ; vous avez donc l’embarras du choix pour commencer à travailler. Tâchez de trouver le juste milieu entre performance et consommation de puissance. En effet, certains algorithmes demandent des processeurs très performants. Pensez aussi au traitement de vos données et à les inclure correctement dans le développement de votre programme.

À découvrir également notre infographie : MaaS : la solution de mobilité au service de l’intermodalité

À propos de Lyko

Expert du MaaS (Mobility as a Service), Lyko met à disposition des collectivités, des industries du tourisme et de la mobilité une suite d’outils intelligents permettant de simplifier le développement de leur propre solution de mobilité intermodale. En quelques lignes de codes, nous leur offrons la possibilité de se connecter instantanément aux données et aux systèmes de distribution de plus de 1 500 opérateurs de transports publics et privés, répartis dans toute l’Europe. Pour en savoir plus, n’hésitez pas à consulter notre site internet lyko.tech.

Post a Reply

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *