Sous le capot, notre moteur d’itinéraires

par Tristram Gräbener, le 26 octobre 2015 | 19 commentaires

Plusieurs transporteurs. Un seul système de réservation. Tel est notre credo. Si nous vous permettons de voyager à travers plusieurs pays européens sans devoir réserver vos billets sur différents sites, c’est parce que nous combinons plusieurs transporteurs au sein de notre système. Toute la magie de Captain Train opère en coulisse, pour que vous n’ayez plus que quelques clics à faire de votre côté.

Prenons un exemple. Vous avez envie d’aller de Londres (Saint Pancras) à Rome (Termini). Voici à quoi ressemble votre voyage.

londres-rome-en-train

De Londres à Rome avec trois transporteurs

Ce voyage se décompose en trois trajets et deux correspondances. Chacun des trois trajets doit être réservé auprès d’un transporteur différent (Eurostar, SNCF et Trenitalia).

Comment en arrivons-nous à ce résultat qui s’affiche sur votre écran ? Tout commence par un calcul d’itinéraire pour trouver le meilleur chemin entre Londres et Rome. Dans un précédent article, nous avons parlé des combinaisons entre transporteurs. Aujourd’hui, nous allons nous pencher sur le calcul des itinéraires au sein de Captain Train.

Simple comme un calcul d’itinéraire

Calculer des itinéraires pour des moyens de transport dont les horaires de passage sont connus à l’avance (bus, train) ne présente rien de difficile. La question a été étudiée par plusieurs chercheurs et de nombreuses solutions ont déjà été trouvées. Si le sujet vous intéresse, l’histoire du calcul d’itinéraire à l’aide d’algorithmes est abordée dans cet article.

Dans notre système, nous utilisons un algorithme rendu public en 2013, qui porte le nom de Connection Scan Algorithm ou CSA. Cet algorithme a le mérite de faire ce que nous attendons de lui tout en demeurant assez simple.

Comme son nom l’indique, cet algorithme manipule des connexions. Une connexion correspond au plus petit trajet qu’un train peut faire entre deux points sans devoir s’arrêter. Dit autrement, on parle de connexion quand un train part d’une certaine gare à une certaine heure pour arriver à une autre gare un peu plus tard, et ce, sans avoir fait de halte intermédiaire entre temps. Par exemple, un train qui part de Paris à 17 h 56 pour arriver à Lyon deux heures plus tard, sans s’être arrêté en chemin, compte pour une connexion.

1-connexion

Pas d’arrêt intermédiaire : 1 connexion

Par conséquent, si le train devait s’arrêter dans une gare intermédiaire pour laisser des passagers monter ou descendre du train, le voyage se composerait alors de deux connexions avec un arrêt intermédiaire entre les deux. Lorsque plusieurs connexions sont nécessaires pour aller d’une gare à une autre, on parle de parcours. Par exemple, aller de Paris à Lyon avec un arrêt au Creusot est un parcours composé de deux connexions ( Paris — Le Creusot et Le Creusot — Lyon).

2-connexion

1 arrêt intermédiaire : 2 connexions

On pourrait croire que les trajets les plus directs sont les plus rapides. Mais il arrive que des trajets comportant plusieurs connexions soient plus rapides que des trajets directs. Pour que notre algorithme puisse trouver le chemin optimal entre deux gares, plusieurs connexions doivent être examinées, y compris celles qui comportent des arrêts entre elles.

Mettre notre grain de sel dans l’algorithme

Demain ne meurt jamais

Les auteurs de l’algorithme sur lequel nous nous appuyons n’ont pas pensé au lendemain. En d’autres termes, ils n’ont pris en compte que les horaires d’une seule et unique journée, évitant ainsi pas mal de pépins. Problème, les horaires des trains sont annoncés plusieurs jours à l’avance. Nous devons donc tenir compte des horaires du jour, évidemment, mais aussi de celle du lendemain, du surlendemain, de la semaine qui suit et même des mois qui viennent.

Si nous voulons être en mesure de calculer des itinéraires pour des voyages prévus dans quatre mois, nous ne pouvons pas y couper. Comment combler ce manque de données dans le temps ? Comment voir plus loin que les horaires du jour ? Une astuce connue consiste à utiliser un petit bout de code dans lequel nous allons indiquer les jours pendant lesquels un train particulier circule.

first_day = "2015-01-01"
validity_pattern = 0b001101
if (validity_pattern[3]) // if the train runs on January 4th
// Do something

Cette approche a le mérite de ne pas consommer trop de mémoire, mais elle peut donner mal à la tête dans le cas des voyages qui arrivent après minuit, ou dans le cas des changements d’heure (été et hiver). Nous avons donc décidé de répéter chaque connexion aussi souvent qu’un train circule. La simplification de l’algorithme ainsi obtenue compense très largement le surcroit de mémoire mobilisé, ce qui nous permet d’obtenir un gain de performance au total, car nous allons moins souvent taper dans la mémoire du système.

Optimisation selon plusieurs critères

En bon site de réservation, nous voulons vous donner du choix quand vous voyagez. Pour que vous puissiez choisir votre trajet en fonction de ce qui vous semble important : rapidité, nombre de correspondances, mélange des deux…

Nous obtenons toutes ces alternatives en ne faisant tourner qu’une seule fois la moulinette de notre algorithme. Comment ? En cherchant tous les solutions qui correspondent à un optimum de Pareto avec les critères : heure de départ, heure d’arrivée et nombre de correspondances.

Notre méthode calcule plusieurs itinéraires pour un même jour. Grâce à ces calculs, notre algorithme va non seulement pouvoir nous renvoyer des résultats pour des départs à 8 heures du matin, mais aussi à 9 h 30 ou 10 h 23. Dans certaines publications, ce balayage horaire est appelé range search.

Plusieurs départs et destinations

Les grandes capitales européennes possèdent souvent plusieurs gares. Lorsque vous choisissez Paris comme point de départ et Rome comme point d’arrivée, nous devons étudier les itinéraires qui partent de chacune des gares parisiennes ainsi que ceux qui arrivent dans chacune des gares romaines.

gares-de-depart-paris

Une ville. Plusieurs gares.

Calculer tous les itinéraires possibles au départ d’une gare

Au même titre que d’autres algorithmes d’itinéraires, le CSA calcule tous les itinéraires qu’il est possible d’emprunter à partir d’un point de départ donné. Bien que nous n’utilisions pas cette faculté pour trouver des combinaisons entre transporteurs, elle permet de connaitre les gares atteignables depuis une gare en particulier, comme la gare du Nord à Paris.

departs-gare-du-nord

D’une gare à plein de gares.

Grâce à l’optimisation selon plusieurs critères, nous n’avons besoin que d’une seule recherche pour calculer tous les itinéraires possibles dans la même journée, au départ d’une gare donnée, et ce dans toute l’Europe. Nous prenons aussi en compte tous les compromis entre le temps de trajet et le nombre de correspondances. Et tout cela se calcule en moins d’un dixième de seconde, autant dire en un clin d’œil.

Performances

Voici ce qui se passe quand vous cherchez un train sur notre site :
1. Nous cherchons d’abord le meilleur itinéraire entre votre gare de départ et votre gare d’arrivée ;
2. Nous demandons ensuite les tarifs et les places disponibles aux transporteurs concernés.

En d’autres termes, le calcul de l’itinéraire est effectué avant que nous ne demandions les tarifs aux transporteurs, et non pas simultanément. Du coup, nous devons mettre le turbo sur le calcul d’itinéraire car la recherche de votre billet ne s’arrête pas à cette étape. Nous avons ensuite besoin de chercher les tarifs avant de pouvoir vous afficher des billets sur le site.

Dans notre calcul le plus simple pour obtenir l’heure d’arrivée la plus proche du départ, le calcul prenait moins de deux millièmes de seconde. Cependant, à cause des différents critères que nous prenons en compte, le temps de calcul est plus élevé. Sur nos serveurs de production, 50 % de nos itinéraires sont calculés en moins de 30 ms (millièmes de secondes) et 95 % des itinéraires sont calculés en moins de 80 ms.

temps-de-reponse-itineraire-captain-train

Prendre en compte plusieurs critères dans la recherche d’itinéraires ralentit donc le calcul d’itinéraire. Pourquoi ? Parce que cette approche requiert une structure de données plus complexe, capable de contenir un nombre inconnu d’itinéraires possibles pour rejoindre une gare. Mais aussi parce que le nombre d’itinéraires valides entre deux points peut très vite augmenter. D’un point de vue purement théorique, il peut y avoir un nombre exponentiel de solutions, mais dans la pratique il y a rarement plus de 10 connexions valides entre deux gares dans une même journée.

Rebuter les mauvais résultats

Pour obtenir ces temps de calcul, nous avons dû compléter un peu l’algorithme de départ (CSA) pour qu’il devienne capable de mettre de côté certains résultats. Dit autrement, l’algorithme sait filtrer les pires itinéraires. D’autant plus pratique que nous cherchons beaucoup de connexions, sur une plage horaire très étendue, ce qui nous amène parfois à calculer des itinéraires loin, très loin d’être judicieux. Nous évitons ainsi que les résultats contreproductifs encrassent nos recherches.

Afin de filtrer les connexions peu intéressantes, nous avons construit un graph statique du réseau ferroviaire. Ce graphe comporte des nœuds (qui correspondent grossièrement aux gares) et des arêtes (qui correspondent aux rails entre les gares). Le coût (ou poids) affiché sur chacune de nos arêtes correspond à la plus petite durée de trajet possible parmi tous les trains qui circulent sur cette arête.

Avant chaque recherche, nous cherchons à résoudre le problème du plus court chemin (d’une gare vers toutes les gares) en utilisant l’algorithme de Dijkstra. Nous obtenons ainsi, pour chaque gare, le temps de trajet minimum pour arriver à destination, de sorte que ce temps ne peut pas être amélioré. Ce temps de référence nous permet de déterminer si une solution intermédiaire est en mesure d’améliorer nos résultats, ou non. À sa lumière, nous filtrons ainsi les résultats qui n’apportent rien.

Le filtrage de résultats au moyen de l’algorithme de Dijkstra ne doit pas être confondu avec l’algorithme A*, qui change l’ordre dans lequel les nœuds du graphe sont examinés. Avec Dijkstra, nous considérons toutes les connexions dans la même séquence.

Difficultés et autres joyeusetés

Nous sommes satisfaits du fonctionnement de notre moteur d’itinéraires. Il nous permet de tenir notre promesse : connecter l’Europe par le rail. Cependant, nous avons dû faire face à quelques pépins en cours de route.

Manipuler le temps avec soin

Tout ce qui touche au temps et à la durée doit être manipulé avec précaution. Malheureusement, notre algorithme ne se préoccupe pas trop de ce qui va se passer demain, contrairement aux trains. Pour dilater notre algorithme dans le temps, afin qu’il tienne compte du futur comme du présent, nous mémorisons nos temps de connexions sous un timestamp Unix et non pas comme une heure dans la journée. En faisant ceci, nous évitons tous les conflits occasionnés par les trajets qui démarrent aujourd’hui mais se terminent après minuit

Cependant, le compte n’y est toujours pas. Nous devons toujours prendre en compte les fuseaux horaires. Nous devons aussi gérer les changements d’heure (en été et en hiver). Malgré tous nos efforts algorithmiques, manipuler des données brutes dans une temporalité dilatée s’avère plus costaud que le calcul de l’itinéraire en lui-même.

La condition de Bellman n’est pas respectée

Dans un monde idéal, chaque sous-partie d’un itinéraire optimal est elle aussi optimale. Il arrive cependant que cela ne soit pas le cas avec certains trains, car nous tenons aussi à réduire le nombre de correspondances.

Par exemple, pour aller de Londres à Venise, l’itinéraire qui comporte le moins de correspondances consiste à faire Londres – Paris en Eurostar, puis de prendre le train de nuit Thello entre Paris et Venise qui passe par Dijon. Une sous-partie de cet itinéraire est donc Londres — Dijon. Cependant, il est possible d’arriver plus vite à Dijon, en partant à la même heure de Londres, si l’on grimpe dans le TGV entre Paris et Dijon plutôt que dans le Thello. La solution intermédiaire qui combine Eurostar et Thello entre Londres et Dijon est donc strictement dominée par la combinaison Eurostar et TGV, elle devrait en théorie être écartée.

Un problème similaire survient en présence de doubles rames : deux trains différents, liés l’un à l’autre, parcourent un bout de chemin ensemble avant de décrocher pour suivre des chemins différents. Nous devons considérer les deux rames comme des solutions intermédiaires, bien qu’elles soient strictement égales.

Rejoignez notre défi CSA*

Étant donné que l’algorithme de départ est relativement simple, nous avons mis sur pied un petit défi Github, afin que vous puissiez mettre en place votre version de l’algorithme. Vous pouvez jouer avec, sans faire les fous. Et si vous voulez faire les fous, nous recrutons.

* Rien à voir avec la télévision.


19 commentaires

Merci pour cette explication très complète sans être trop compliquée.

Petite question : d’où viennent les données avec lesquelles vous calculer les itinéraires ?

par François, le 26 octobre 2015 à 22h53. Répondre #

*calculez

par François, le 26 octobre 2015 à 23h03. Répondre #

Très bonne question que je me pose aussi 😉

par kalon33, le 27 octobre 2015 à 10h45. Répondre #

Les données viennent des transporteurs, c’est-à-dire de ceux qui font rouler les trains et en fixent les horaires.
Par contre elle ne sont pas disponible au grand public.

par Tristram Gräbener, le 27 octobre 2015 à 10h52. Répondre #

Merci pour cette présentation.
En lisant le début j’avais en tête le fait que le problème n’en était plus un mais le nom m’echappait 🙂

Avec le changement d’heure, la plupart des cto de petite Start-up doivent rester humble face à leur méthode modélisation du temps. Héhé.

par Thomas, le 27 octobre 2015 à 7h26. Répondre #

Pas que les CTO de petite start-up. Les DSI de gros groupes ne font pas les malins non plus 😉

par Tristram Gräbener, le 27 octobre 2015 à 11h36. Répondre #

Intéressant de voir de la belle algorithmique sous le capot de Captain Train.

Pour le défi CSA*, il va y avoir nu concours, il faut poster les solutions quelque part ?

par JH, le 27 octobre 2015 à 10h56. Répondre #

Je vous invite à simplement forker le projet et proposer votre solution par Pull Request si elle vous semble pertinente.

par Tristram Gräbener, le 27 octobre 2015 à 11h19. Répondre #

Euh…votre défi, là…ça ressemble un peu à un moyen détourné d’avoir une idée que vos équipes n’ont pas eue, et gratuitement en plus, non ?…

par Allie, le 27 octobre 2015 à 15h03. Répondre #

Pas du tout ! Le périmètre du challenge est particulièrement restreint et inclus très peu de nos problématiques décrites dans cet article.

Si quelqu’un arrive à améliorer significativement les performance, c’est une publication scientifique qu’il faudrait faire.

À l’origine c’était un projet interne pour que d’autres développeurs chez Captain Train puissent se familiariser avec l’algorithme et éviter une sur-spécialisation.
Étant donné que c’était plutôt ludique on s’est dit que d’autres personnes pourraient être intéressées.

par Tristram Gräbener, le 27 octobre 2015 à 15h35. Répondre #

Merci pour ces détails. Par ailleurs, je me suis toujours posée la question de savoir comment vous tenez compte des changements de gare qu’il faut effectuer sur un trajet passant par Paris ou autre ville à gares multiples. Par exemple, si je fais Bordeaux – Rouen, je vais devoir aller par mes propres moyens de la gare Montparnasse à la gare St Lazare. Quel temps minimum de transfert prenez-vous dans votre algorithme pour ne pas proposer un parcours irréaliste techniquement et est-il différent de celui du site SNCF? Je me souviens d’avoir contourné cet obstacle par le passé, considérant que je pouvais faire le transfert en moins d’une heure (plus le chiffre exact en tête) alors que le site SNCF ne me le proposait pas. Mais j’ai dû acheter deux billets distincts, ce qui peut revêtir d’autres contraintes (en cas d’annulation du premier train, par exemple…). Dans la même veine, tenez-vous compte uniquement du temps et du coût, ou avez pris en considération le fait que le voyageur pourrait éventuellement être prêt à payer un peu plus et à perdre un peu de temps, s’il pouvait en échange s’exonérer d’un changement de gare? Pour certaines personnes (âgées notamment mais pas uniquement ;-)), ce confort n’a quasiment pas de prix. Par exemple, je serai quasiment prête à privilégier un Toulouse-lyon puis Lyon-Rouen en TGV direct à un traditionnel Toulouse-Rouen avec changement à Paris. La distance supplémentaire de la seconde hypothèse est contrebalancée par l’absence de changement de gare. Il suffit de changer de train à Lyon sans changer de gare. Si l’escale n’est pas trop longue et le surcoût pas prohibitif, pour moi, le choix est vite fait. Même si le trajet parait de prime abord aberrant (impression de faire le tour de France), je préfère mille fois passer par Lyon et m’éviter tous les aléas et les contraintes d’une escale parisienne.
Bien cordialement,

par Suzanne, le 27 octobre 2015 à 23h20. Répondre #

Il faut séparer deux cas :
— les trajets sans combinaison (uniquement SNCF, par exemple TGV puis TER)
— les trajets en combinaison (TGV puis Ouigo)

Dans le premier cas, nous remontons les résultats tels qu’ils sont fournis par le transporteur (la SNCF). En effet, comme vous l’avez correctement deviné, avoir un seul billet pour deux trajets oblige le transporteur à s’assurer de vous amener à bon port même en cas de problème sur le premier tronçon. De plus la dégressivité kilométrique rend souvent le trajet moins cher.

Dans le deuxième cas, c’est nous qui décidons de la durée. Cela dépend de la correspondance (Paris Austerlitz vers Gare de Lyon c’est plus rapide que vers Montparnasse) et des transporteurs (Eurostar exige une présence de 30 minutes avant…).

Dans l’application android, il est possible de spécifier un via que nous transmettons à la SNCF qui permet parfois d’obtenir le trajet souhaité. Nous réfléchissons à étendre cette fonctionnalité à toutes les interfaces.

par Tristram Gräbener, le 28 octobre 2015 à 12h02. Répondre #

« Dans l’application android, il est possible de spécifier un via que nous transmettons à la SNCF qui permet parfois d’obtenir le trajet souhaité. »
Ah ? Bonne idée je trouve, mais je n’ai pas vu cette option.

par Jojo, le 30 octobre 2015 à 22h53. Répondre #

Effectivement, elle est cachée. Le secret est révélé dans notre aide : http://aide.captaintrain.com/article/81-rechercher-trajet-via

par Tristram Gräbener, le 1 novembre 2015 à 21h14. Répondre #

Ah, merci !
Et je constate que ça marche aussi pour les autres transporteurs (d’après mon test côté DB).

Apparemment vous faites ça en combinant deux billets (comme les combinaisons magiques Ouigo-SNCF-DB-…). Il y a donc un risque de problèmes en cas de correspondance manquée..

Vivement que cette option soit disponible sur la version web !

par joris, le 2 novembre 2015 à 0h47. Répondre #

En fait on fait les deux : on demande un via à la SNCF et on fait deux appels en combinaison.

par Tristram Gräbener, le 2 novembre 2015 à 13h42. #

Bonjour,

J’ai trouvé l’article assez intéressant.
J’ai pour ma part une question d’algorithmique sur un problème légèrement différent. On se donne deux gares A et B. On suppose qu’on dispose du moteur d’itinéraire et que celui ci permet de calculer le temps de parcours entre deux gares quelconques.
Le but est de choisir une gare O, de telle manière à ce que les trajets OA et OB soient environ de même durée et que cette durée soit minimale. Formellement, cela revient à trouver O tel que la quantité : max(OA,OB) soit minimale (on mesure des durées).

Instinctivement, on pourrait calculer le parcours optimal entre A et B et choisir la gare O sur ce parcours. Mais cette méthode ne fonctionne pas toujours : en effet sur l’exemple si dessous, la seule gare située sur le parcours optimal AB (la gare C) est trop proche de A, et la gare O située sur un parcours AB non optimal (temps 5 au lieu de 4) répond mieux au problème.

| — O ———| AB(opt) = 4
| |
| | OA = 2.5
| | OB = 2.5
| | AB via O = 5
A—C————B
1 3

Dès lors, y’a t’il algorithme performant permettant de ne pas tester toutes les gares afin de déterminer la gare O ?

Vous avez peut être déjà réfléchi à ce problème. Sinon, considérez le comme un autre défi ludique 😛

par Julien, le 1 novembre 2015 à 13h36. Répondre #

Ps : mon schéma ascii du contre exemple est tout cassé 🙁 : il s’agissait d’un triangle AOB tel que AB = 4, AO = BO = 2.5, et C est placé sur AB tel que AC = 1

par Julien, le 1 novembre 2015 à 13h39. Répondre #

C’est pas si compliqué. La vaste majorité des algorithmes de calcul d’itinéraires calculent tous les itinéraires d’un point de départ vers tous les autres.

Il suffit de lancer un calcul depuis A, un autre depuis B, puis parcourir toutes les gares et voir celle qui maximise la fonction.

Après, l’enfer étant dans les horaires, ça peut être un peu tricky si le but c’est de minimiser la durée de trajet (deux flemmards qui sont prêts à attendre à condition que la durée dans le train est minimisée), ou bien trouver l’arrivée au plus tôt en commun pour deux personnes (deux agents secrets qui doivent le moyen le plus rapide de transmettre une valise d’une main à une autre).

Un autre enfer et si vous ne disposez que d’une boite noire qui sait répondre que des durées de trajets entre deux gares et au lieu de retourner les durées vers toutes les gares.

par Tristram Gräbener, le 1 novembre 2015 à 21h13. Répondre #

Ajoutez votre commentaire

Requis

Requis (caché)

Facebook

Twitter