L'algorithme RAPTOR expliqué

Round bAsed Public Transit Optimized Router, ou RAPTOR pour faire court, est un algorithme conçu au centre de recherche Microsoft Research par Daniel Delling, Thomas Pajor et Renato F. Werneck en 2012. Il a défini une approche révolutionnaire de la planification d'itinéraires et de l'optimisation du routage dans les graphes de transport en commun.

Il y a un premier problème majeur que l'on rencontre lorsqu'on cherche à résoudre des problèmes d'itinéraire dans un graphe : on considère soit le plus court chemin en temps, soit en distance, idéalement les deux — c'est là que le routage Pareto-optimal entre en jeu :

Routage Pareto-optimal

Avec le routage Pareto-optimal, on cherche à concilier plusieurs critères concurrents à la fois : ainsi, au lieu de renvoyer un unique « meilleur » trajet, on peut proposer un panel varié d'options toutes optimales, au sens où aucune n'est purement et simplement battue par une autre.

Un trajet est Pareto-optimal lorsqu'aucun autre itinéraire n'est au moins aussi bon sur tous les critères tout en étant strictement meilleur sur au moins un. Concrètement, cela signifie que pour un trajet Pareto-optimal, toute tentative d'améliorer un critère (par ex. le rendre plus rapide) se ferait nécessairement au détriment d'un autre (par ex. le rendre plus cher).

En général, il existe plusieurs de ces itinéraires, et aucun ne domine les autres : comparé à tous les autres, chacun est meilleur sur au moins un critère.

Même si certains sont des compromis équilibrés qui ne sont les meilleurs sur rien en particulier. Ensemble, cet ensemble d'itinéraires non dominés est ce que l'on appelle la frontière de Pareto.

Si l'on trace un graphique à deux axes où chaque itinéraire possible est un point, l'ensemble des itinéraires Pareto-optimaux tracera une frontière entre les itinéraires admissibles et le reste.

Si un itinéraire est meilleur que tous les autres sur chaque critère, c'est un itinéraire dominant. Cet itinéraire est Pareto-optimal, et c'est le seul point sur la frontière de Pareto.

Qu'est-ce qui rend un réseau de transport en commun particulier ?

Alors qu'un réseau routier est assez simple : on résout le plus court chemin avec Dijkstra ou A\*, en pondérant les arêtes selon le trafic, en priorisant les autoroutes, etc. ;

Un réseau de transport en commun n'est pas tout à fait pareil : un métro arrivera (généralement) à la même heure qu'il soit bondé ou non.

Ça devrait être encore plus simple, non ?

Eh bien, pas vraiment. Car, contrairement aux trottoirs ou aux routes, on ne peut pas partir quand on veut : on est soumis aux horaires.

C'est tout l'intérêt de RAPTOR : comment prendre correctement en compte les heures de départ et d'arrivée, temps de correspondance compris, pour proposer les meilleures options de trajet.

Pour cet article, nous utiliserons le réseau de métro de Lyon. Avec une aire urbaine de plus de 2 M d'habitants, il est de taille raisonnable pour notre propos sans être écrasant.

Il y a 4 lignes principales (hors funiculaires). Dans la suite de l'article, on considérera que l'on part directement de « Guillotière » (en noir) pour aller à « Hôtel de Ville » (en rose).

Le réseau ci-dessus est simplifié : on ne garde que les stations et correspondances clés, ce qui fait passer de 42 stations à une vingtaine à peine.

Les horaires sont assez simples : entre 2 et 6 minutes entre deux métros selon la ligne, 1 minute de correspondance dans tous les cas.

Comparaison des algorithmes

Essayons de résoudre ce problème avec des algorithmes connus.

D'abord, essayons l'algorithme de Dijkstra, la référence pour trouver les plus courts chemins :

Efficace pour garantir la découverte du plus court chemin, certes, mais on voit qu'on explore comme un feu de forêt, en mettant chaque arête en file de priorité l'une après l'autre.

Bon, grâce à ça, on connaît le plus court chemin !

Mais s'il existait un moyen plus rapide d'y arriver, avec des contraintes réelles ? Et si marcher était plus rapide, ou s'il existait un tout autre chemin ?

Avant de s'emballer, essayons A\* (avec la norme L2), censé nous aider à « tirer » vers notre objectif :

Le résultat est clair : un peu moins d'exploration que Dijkstra, mais exactement le même chemin.

Bon, alors pondérons nos arêtes avec les horaires, en augmentant le poids du chemin selon le nombre de minutes d'attente :

Voilà ! On a trouvé un meilleur chemin qui permet d'arriver à 8h11 au lieu de 8h16 avec les anciens itinéraires.

Vous vous demandez peut-être si c'était de la chance avec ce réseau précis : eh bien non ! Cette méthode fonctionne à merveille !

Petit souci : c'est très lent, car ça explore et réajuste les poids en permanence.

De plus, ça ne garantit pas le meilleur trajet, car ça ne prend en compte ni les trajets à pied ni le nombre de correspondances. Qui préférerait un trajet une minute plus court mais avec deux correspondances de plus ?

C'est là que RAPTOR entre en jeu :

À première vue, on pourrait penser qu'il explore bien plus et qu'il est plus lent ; penchons-nous dessus et essayons de comprendre comment l'algorithme fonctionne.

RAPTOR — l'algorithme

Comment fonctionne l'« exploration »

Vous avez peut-être remarqué que la ligne verte est explorée avant même de considérer ses lignes voisines ? Eh bien c'est tout l'intérêt de RAPTOR :

Calcul par rounds (tours)

Un round correspond à un nombre fixe de trajets effectués jusque-là (ou, de façon équivalente, à un nombre fixe de correspondances) :

• Round 0 → trajets utilisant 0 correspondance et aucun embarquement (par ex. marcher simplement de l'origine à la destination).
• Round 1 → trajets utilisant au plus 0 correspondance (par ex. marcher, embarquer, puis remarcher).
• Round 2 → trajets utilisant au plus 1 correspondance.
• Round k → trajets utilisant au plus k-1 correspondances.

Ce qui signifie que RAPTOR va calculer l'heure d'arrivée à toutes les stations de la ligne courante, puis sauter sur chaque ligne de métro connectée, faire de même, et ainsi de suite.

Sur ce point, cela peut ressembler à l'algorithme de Dijkstra, comme un feu de forêt, mais au lieu de considérer des sommets, il considère des trajets et se rapproche donc bien plus des approches de programmation dynamique.

Chaque balayage de ligne est un parcours linéaire, sans opération de tas.

Qu'est-ce qu'un trajet (trip) ?

Un trajet (trip) est un déplacement précis d'un véhicule (par ex. un métro) le long d'une ligne donnée, défini par son heure de départ à la première station et ses heures d'arrivée successives à chaque station de la ligne, selon un horaire fixe.

Ce qui signifie qu'on ne considère pas une ligne de métro, mais le trajet qu'un train effectue à un moment donné.

Comment RAPTOR utilise-t-il les horaires ?

RAPTOR a besoin d'une seule chose pour fonctionner : les horaires.

Il nous faut l'heure de départ et d'arrivée de chaque train, bus, tramway, etc. sur chaque ligne, pour chaque station. Une fois ces données disponibles, la majeure partie de notre programme est déjà pré-calculée.

Étant donné une heure de départ à une station donnée, on regarde la prochaine heure d'arrivée du train, puis on enregistre l'heure d'arrivée pour chacune des stations de la ligne, en se référant directement à l'horaire.

Ainsi, le calcul de l'heure d'arrivée pour chaque station est quasiment instantané.

Ensuite, RAPTOR traite toutes les lignes que l'on peut emprunter depuis une station améliorée au round précédent. Ici, les lignes rouge et bleue au round 1.

Cela signifie que RAPTOR n'utilise pas de file de priorité. Une simple liste ou un simple ensemble suffit, et c'est en partie pour cela qu'il est si rapide : pas d'insertion complexe, parallélisation facile.

En résumé (TL;DR)

• On part d'une station donnée
• Toutes les autres stations du réseau ont une heure d'arrivée attendue infinie (positivement)
• On définit un nombre de rounds admissibles (un nombre maximal de trajets)
• On récupère toutes les heures d'arrivée pour chaque station accessible depuis notre position de départ
• Une fois l'ensemble des stations entièrement mis à jour, pour chaque station dont l'heure d'arrivée s'est améliorée, on recommence
• On s'arrête si l'on ne peut plus améliorer aucune heure d'arrivée ou si l'on atteint le nombre maximal de rounds

Un exemple vaut mille mots

Disons que nous sommes à la station A à 8h00.

On regarde quand passe le prochain train : 8h03.

On enregistre alors l'heure d'arrivée à chaque station de notre ligne desservie par ce train. [8:03 ; 8:05 ; 8:07 ; 8:10 ; 8:13]

Le premier round est maintenant terminé.

Il y a une correspondance à la station B avec une ligne allant directement à la station D.

Puisqu'avec RAPTOR on considère chaque trajet possible, faisons les mêmes calculs : on regarde le premier train qu'on peut prendre : 8h06, ça marche.

On peut alors récupérer l'horaire correspondant, qui ressemble à ceci : [8:06 ; 8:08 ; 8:10], améliorant ainsi l'heure d'arrivée à la station D de deux minutes et à la station E de trois minutes.

On ne peut plus améliorer aucune heure d'arrivée, on s'arrête donc là.

Si l'on prévoit d'aller à la station E, on aurait deux options :

• Arriver tôt avec une correspondance
• Arriver plus tard sans correspondance

Cela constituerait notre frontière de Pareto.

Un mot sur la performance

Plus tôt, on a vu RAPTOR sembler explorer davantage que Dijkstra tout en l'emportant. L'astuce, c'est que chaque unité de travail est peu coûteuse. Le O((V + E) log V) de Dijkstra paie une taxe en log V à chaque relâchement pour maintenir sa file de priorité ordonnée.

Avec RAPTOR, un round n'est que deux parcours linéaires : balayer chaque ligne une fois, relâcher chaque trajet à pied une fois, avec rien d'autre que des lectures et écritures de tableaux.

Cela place un round à environ O(Σ |stations de ligne| + |correspondances|), sans aucun facteur logarithmique.

Le nombre de rounds K est le reste de l'histoire, et c'est une petite constante : les trajets réels dépassent rarement une poignée de correspondances. Ainsi, l'ensemble de la requête s'exécute en environ O(K · (Σ |stations de ligne| + |correspondances|)).

Je pense qu'on est prêts à plonger dans le vif du sujet ! Préparez votre éditeur favori, on va écrire du code !

RAPTOR, implémentation

D'abord, on implémente la base : les horaires, en minutes depuis l'ouverture du métro (8h00).

STOPS = ['A', 'B', 'C', 'D', 'E']
route_stops = {
    'L1': ['A', 'B', 'C', 'D', 'E'],
    'L2': ['B', 'D', 'E'],
}

timetables = {
    'L1': [[3, 5, 7, 10, 13],],
    'L2': [[6, 8, 10],],
}

N'oublions pas les correspondances à pied ! Marcher d'un train à un autre n'est pas instantané ! (Bon, ça l'est dans notre exemple, mais attention, c'est important !)

transfers = {p: [] for p in STOPS}

Ensuite, on définit le nombre maximal de rounds

K = 2

Il nous faut maintenant créer nos listes des meilleures arrivées aux stations.

L'une servira à construire notre frontière de Pareto, c'est-à-dire qu'elle contiendra la meilleure heure d'arrivée pour chaque station à un round donné.

tau = [{p: INF for p in STOPS} for _ in range(K + 1)]

La seconde sera une liste des meilleures heures d'arrivée tous rounds confondus : elle servira à l'élagage → On n'inscrira pas un nouvel itinéraire si l'on avait déjà une meilleure heure d'arrivée à un round précédent.

tau_star = {p: INF for p in STOPS}

Ensuite, on fixe les variables propres à notre exécution : station de départ, heure de départ ; et on adapte nos variables existantes en conséquence.

source = 'A'
target = 'E'
departure_time = 0

tau[0][source] = departure_time
tau_star[source] = departure_time

Dernière étape avant de coder le vrai cœur du sujet : créer un ensemble qui servira de file des stations améliorées ; il est donc composé d'une seule station : celle de départ.

marked = {source}

L'algorithme

Maintenant, on attaque la partie difficile.

On pré-calcule les interconnexions. Quand une station est marquée, on doit savoir instantanément quelles lignes la traversent (et à quel endroit le long de la ligne).

routes_at = {p: [] for p in STOPS}
for r, seq in route_stops.items():
    for i, p in enumerate(seq):
        routes_at[p].append((r, i))

Petit utilitaire

Une fonction simple qu'on utilisera souvent : trouver le « prochain train » que l'on peut prendre.

r étant la ligne, i l'indice de la station et _ready_time_ le moment où l'on est à la station, prêt à embarquer.

Notez qu'une version optimisée, mais bien plus verbeuse, est disponible à la fin de cet article.

def earliest_trip(r, i, ready_time):
    best = None
    for ti, trip in enumerate(timetables[r]):
        if trip[i] >= ready_time and (best is None or trip[i] < timetables[r][best][i]):
            best = ti
    return best

Dictionnaire

Maintenant que la plupart des variables ont été couvertes, voici un petit dictionnaire pour vous aider à en comprendre le sens

Boucle principale

On initialise maintenant la boucle principale, en itérant sur le nombre maximal de rounds défini, en reportant les résultats obtenus au round précédent (0) afin de réutiliser les trajets déjà calculés (par ex. pour prendre un train plus tôt)

for k in range(1, K + 1):
    tau[k] = dict(tau[k - 1])

On collecte maintenant les lignes que l'on va balayer à ce round (sauvegardées dans marked au préalable)

    Q = {}
    for p in marked:
        for (r, i) in routes_at[p]:
            if r not in Q or i < Q[r]:
                Q[r] = i
    marked = set()

On itère ensuite sur Q pour trouver chaque point d'embarquement des lignes à explorer

    for r, start_i in Q.items():
        seq = route_stops[r]
        t = None
        for i in range(start_i, len(seq)):
            p = seq[i]

Si l'on est à bord d'un train, on regarde l'heure à laquelle on arrive à la station courante. On n'adopte cette heure que si elle bat les deux repères : la meilleure heure jamais enregistrée pour cette station, et la meilleure heure déjà connue pour la destination.

En cas de succès, on enregistre la nouvelle arrivée pour ce round, on met à jour le meilleur global pour la station, et on ajoute la station à marked pour pouvoir la balayer au round suivant.

            if t is not None:
                arr = timetables[r][t][i]
                if arr < min(tau_star[p], tau_star[target]):
                    tau[k][p] = arr
                    tau_star[p] = arr
                    marked.add(p)

On vérifie maintenant s'il existe un candidat pour un train plus tôt que l'on peut prendre depuis la station où l'on se trouve, et on bascule dessus le cas échéant

            cand = earliest_trip(r, i, tau[k - 1][p])
            if cand is not None and (t is None or timetables[r][cand][i] < timetables[r][t][i]):
                t = cand

Trajets à pied (footpaths)

Que l'on considère des trajets à pied à l'extérieur du réseau ou à l'intérieur des stations, cela reste important à prendre en compte (par ex. passer de la ligne A à la B peut prendre quelques secondes, ou une dizaine de minutes). Mais attention ! Comme il ne s'agit pas d'embarquer dans un autre trajet, on reste dans le même round ! (marcher de la station E jusqu'à votre destination peut être plus lent que de faire de même depuis la station \_D).

Donc, pour chaque station améliorée, on vérifie si l'heure d'arrivée s'améliore encore en tenant compte du temps de marche, et on met tout à jour en conséquence

    for p in list(marked):
        for (q, w) in transfers[p]:
            if tau[k][p] + w < tau[k][q]:
                tau[k][q] = tau[k][p] + w
                tau_star[q] = min(tau_star[q], tau[k][p] + w)
                marked.add(q)

Enfin, si rien ne s'est amélioré au round courant, on s'arrête là

    if not marked:
        break

C'est fini !

On peut maintenant construire notre frontière de Pareto

trips = []

for k in range(1, K + 1):
    trips.append(tau[k][target])

Cela nous donne l'heure d'arrivée pour chaque round ; à partir de là, vous pouvez en déduire la frontière de Pareto !

N'oubliez pas que RAPTOR donne le meilleur de lui-même une fois parallélisé : penchez-vous dessus !

Merci d'avoir lu jusqu'au bout ; posez toutes les questions que vous pourriez avoir et je ferai de mon mieux pour y répondre.

Bibliographie & divers

Daniel Delling, Thomas Pajor, and Renato F. Werneck. 2012. Round-based public transit routing. In Proceedings of the Meeting on Algorithm Engineering & Expermiments (ALENEX '12). Society for Industrial and Applied Mathematics, USA, 130–140.

L'algorithme du plus court chemin de Dijkstra

Le célèbre algorithme, trouvé en 20 minutes par Edsger Dijkstra dans un café d'Amsterdam, est à la base de nombreux algorithmes de plus court chemin.

Si vous avez un graphe à pondération positive, Dijkstra garantit de trouver le plus court chemin d'un sommet à un autre, et le fait en O((V + E) log V). Son principal avantage est la relative simplicité d'implémentation (grâce à l'absence d'heuristiques) et son côté garanti. Jusqu'à très récemment, c'était l'algorithme principal pour résoudre les itinéraires dans un graphe de transport en commun, en pondérant les arêtes dans l'espoir de représenter la fiabilité, le coût, etc. le tout en un, avec le temps de trajet.

Eh bien ici, on cherche à s'éloigner de ce principe de file de priorité, ce qui rend la parallélisation bien plus facile.