Libération de navitia : un calculateur d’itinéraire pour les transports en communs

Posté par . Édité par Florent Zara, palm123 et Benoît Sibaud. Modéré par ZeroHeure. Licence CC by-sa
52
30
avr.
2014
C et C++

La société Canal TP a ouvert sous licence Affero-GPL son produit phare : le calculateur d’itinéraires pour transports en commun Navitia. Il s’agit d’un serveur qui expose une API REST afin d’être intégrée dans divers services (site web, application mobile, client CLI…). Les sources de données acceptées sont le format GTFS souvent utilisé pour diffuser des horaires en OpenData et OpenStreetMap pour les itinéraires piétons.

Le cœur est en C++11 avec une interface en Python pour gérer l’API REST.

En plus de la fonction centrale de calcul des itinéraires, voici certaines autres fonctionnalités :

  • approche à pied, vélo, vélo libre service
  • prochains départs, arrivées (pour l’instant théorique, le temps réel est encore en développement)
  • « isochrones » (terme approximatif qui revient à calculer le temps pour atteindre tous les arrêts depuis un point)
  • service « à proximité »
  • explorer le référentiel de données (par exemple l’ensemble des lignes passant par tel arrêt)

Algorithmes

Pour les personnes curieuses des entrailles, le calcul routier est simplement l’implémentation de l’algorithme de Dijsktra par Boost::Graph. La partie transports en commun est l’implémentation de l’algorithme Raptor. Cela permet de gérer de grands réseaux tels que toute l’Île-de-France. Des expérimentations ont été lancées dès l’ouverture par des Néerlandais afin d’essayer d’intégrer l’intégralité des transports des Pays-Bas.

Historique

Cette ouverture se place dans une démarche d’ouverture progressive de Canal TP.

Navitia 2 est la ré-écriture de Navitia 1 qui a plus de 10 ans. En parallèle, Canal TP a été impliqué lors de divers évènements OpenData transports. Cela a permis de découvrir les besoins d’une API simple à utiliser et rapide à intégrer. À titre de comparaison, les micro-services SNCF sont basés sur Navitia 1 et les retours soulignaient la difficulté d’une intégration rapide (typiquement dans le cadre d’un hackathon).

La construction d’une API simple à intégrer a été accompagnée d’une plateforme qui vise à intégrer les données en OpenData navitia.io. L’ouverture du code source sous licence libre a donc été la conséquence logique de cette ouverture pour s’adresser à un public plus large et espérer que l’information transports en communs devienne universelle.

Concurrents

On ne peut pas vraiment parler de concurrence, d’ailleurs plusieurs échanges ont lieu avec les développeurs et peut-être qu’une convergence des API et de l’alimentation des données aura lieu.

  • OpenTripPlanner : probablement le calculateur d’itinéraire libre le plus connu. Il est extrêmement configurable et flexible, mais semble atteindre des limites sur les gros jeux de données (par exemple l’Île-de-France)
  • RRRR : projet initié par des développeurs d’OpenTripPlanner visant à faire une version particulièrement optimisée en performance et consommation mémoire afin de pouvoir fonctionner sur un téléphone
  • Synthèse : autre système très complet, utilisé à Toulouse par Tisséo
  • Mumoro : projet purement académique

Avenir

Contre toute attente, les premières pull-requets sont arrivées dès le lendemain de la publication du code (il s’agit pour l’instant uniquement de petites modifications pour compiler sur d’autres systèmes). L’ouverture étant très récente, il y a encore un peu de mise en qualité à faire pour atteindre des standards du logiciel libre : documentation, traduction des commentaires, facilité de déploiement… Le temps réel est une autre composante très attendue qui nécessite d’être améliorée.

  • # Multimodal et autres questions

    Posté par (page perso) . Évalué à 7.

    Bonjour,

    Bravo pour la libération et la démarche d'ouverture tout d'abord !

    Quelques questions :

    • Est-ce réellement un calculateur d'itinéraires multimodal, ou juste TC + piéton en complément du TC ?
    • Si c'est multimodal, est ce que la multimodalité est intégrée dans la définition du graphe de réseau ou dans les algorithmes utilisés ?
    • Est ce que l'optimisation d'itinéraire tient compte des horaires de passage ? (à priori oui). Dans ce cas même question, est ce fait en démultipliant le graphe de réseau selon les horaires de passage ou c'est l'algorithme RAPTOR qui permet de tenir compte du temporel ?
    • Quel est le framework Python utilisé ?
    • Si vous mélangez de la donnée GTFS et de la donnée OSM, comment gérez vous les potentielles incompatibilités de licence sur la création des itinéraires de résultat entre l'ODbL ("share-alike") et une licence GTFS qui empêcherait le SA ?
    • OSRM n'est pas cité dans les autres calculateurs, est ce que c'est parce qu'il est d'abord orienté routier ?

    Merci pour les précisions !

    • [^] # Re: Multimodal et autres questions

      Posté par . Évalué à 9.

      • Le principe c’est de trouver les N arrêts accessible en 15 minutes de vélo/marche/vls selon le mode choisi et les M arrêts à l’arrivée, c’est la partie Dijkstra. Ensuite entre ces N×M couples d’arrêts, on cherche les itinéraires en transports en commun. Est-ce que c’est multimodal ça ? Je ne me prononcerai pas, les avis virent vite au troll sur cette question là ;)
      • Oui, le calcul est bien à l’horaire exact (avec des temps de battements et de correspondance configurable). L’algorithme Raptor a un graphe implicite où chaque arc correspond au trajet entre deux arrêts d’un véhicule. Il n’y a donc pas de graphe au sens « plan de métro ». Si tu veux plus d’informations sur la représentation des horaires pour le calcul d’itinéraire, je vais faire un peu de mégalo, et t’orienter vers le chapitre 1 de ma thèse http://tel.archives-ouvertes.fr/tel-00553335
      • Flask
      • Oh ! Question tricky. Voici mon interprétation : il n’y a pas d’agrégation des base OSM et GTFS et il n’y a pas de rediffusion. Lors de la restitution de l’itinéraire avec le tracé piéton et TC, la quantité de données exposée n’est pas « substantial » http://wiki.openstreetmap.org/wiki/Open_Data_License/Substantial_-_Guideline Par contre, il y a bien de l’agrégation des données GTFS de plusieurs transporteurs (sinon ça peut pas marcher). Par exemple RATP+SNCF. Dans ce cas, Canal TP rediffuse (pour l’instant de manière très amateur, mais ils m’ont promis de s’améliorer sur le process) sur http://data.navitia.io
      • Effectivement OSRM est uniquement routier. Les problématiques sont assez différentes dès qu’il y a des notions d’horaires

      J’espère pas dire trop de conneries (je ne travaille plus chez Canal TP depuis un an, mais j’ai suivi cette ouverture puisque ça me tenait à cœur).

      • [^] # Re: Multimodal et autres questions

        Posté par (page perso) . Évalué à 2.

        ah, je viens de comprendre : TC comme Transport Collectif… ou Transport en Commun, éventuellement.

      • [^] # Re: Multimodal et autres questions

        Posté par (page perso) . Évalué à 1.

        Merci pour les précisions, ça répond bien aux questions.

        Pour la question de la licence, c'est effectivement complexe, et certainement dans la zone grise de l'ODbL. Encore une démonstration du besoin de passage d'OSM en domaine public (Troll inside).

        Pour les données GTFS, la question se pose aussi, ça dépend des licences des différentes données.

        Intéressé pour avoir les résultats si une étude juridique complète est faite à ce sujet (c'est certainement Benjamin Jean le mieux placé pour éclairer sur ces sujets).

  • # Commentaires en français

    Posté par (page perso) . Évalué à 2.

    Bonjour,

    Je suis content de voir de plus en plus de projets en C++11 :-). Cependant j'ai vu que votre code était en anglais mais les commentaires en français… Est-ce qu'il y a une raison particulière à ça ?

    C'est un peu dommage pour nos amis anglophones et autres.

    l'azerty est ce que subversion est aux SCMs

    • [^] # Re: Commentaires en français

      Posté par . Évalué à 5.

      oui c'est une raison historique.
      Les nouveaux commentaires sont en anglais et on essaye de traduire les anciens au fur et à mesure, mais ça prend du temps (et on y pense pas tout le temps ;) )

    • [^] # Re: Commentaires en français

      Posté par . Évalué à 2.

      Ceci dit, les premières contributions étant Néerlandaises, ça devrait rapidement motiver tout le monde ;)

  • # Route de montagne

    Posté par (page perso) . Évalué à 4.

    Comment on calcule le temps pour les routes de montagnes (ou autres : tortueuses, chaussées en mauvais état…) ? J'avais cru comprendre que Michelin faisait des essais en grandeur réelle pour corriger les valeurs.

    • [^] # Re: Route de montagne

      Posté par . Évalué à 6.

      Le cœur est le calcul pour transports en communs, dont on les grilles horaires sont fournies et considérées comme exactes. Comment ces grilles horaires sont gérées, c’est un problème des transporteurs (il existe des éditeurs spécialisés dans ce genre d’outils).

      La partie « routière » c’est essentiellement de l’approche à pied ou à vélo sur de courtes distances où la durée varie peu.

      Dans tous les cas, même si navitia est capable de calculer la durée d’un trajet routier, ça n’a pas l’ambition d’être aussi bon que les outils spécialisés.

      Après, lorsqu’on sait qu’à Paris c’est rarement un bus toutes les 3 minutes, mais plutôt trois bus toutes les 9 minutes, c’est un aspect qui n’est pas encore pris en compte (du moins pas de manière très fine, actuellement il y a juste un temps de battement pour les correspondance pour réduire le risque).

  • # Dijkstra ?

    Posté par . Évalué à 4.

    le calcul routier est simplement l’implémentation de l’algorithme de Dijsktra par Boost::Graph.

    Sauf erreur de ma part, dans un graphe avec des coordonnées euclidienne, l'algorithme de Sedgewick et Vitter est bien
    plus efficace car il introduit une heuristique:

    http://archive.numdam.org/ARCHIVE/RO/RO_1996__30_4/RO_1996__30_4_333_0/RO_1996__30_4_333_0.pdf

    Il y a quelques années (houla, avec l'implémentation que j'en avais faite en C et qui tournait sur un SIG extrait des données d'un fournisseur dont l'effigie est un "bonhomme", il n'y avait pas photo.

    (Je pourrais même la ressortir si ça peut servir ;-)

    Je conseille d'ailleurs la lecture de cet excellent ouvrage:
    http://livre.fnac.com/a1467137/Philippe-Lacomme-Algorithmes-de-graphes#ficheResume

    • [^] # Re: Dijkstra ?

      Posté par . Évalué à 4.

      Si le but est de faire un calcul d’itinéaire point à point, il y a considérablement plus performant que ce genre de vieilleries (on parle de plusieurs facteurs 1000) : on peut calcul un trajet sur les routes de n’importe quel point de la planète à n’importe que point en une milliseconde sur un desktop. Le plus lent est de générer le flux de sortie :)

      J’avais tenté de vulgarisé un peu ce qui s’est fait dans un article de blog : http://blog.tristramg.eu/petit-historique-du-calcul-ditineraire.html

      La grande différence c’est que dans le cas de Navitia, il cherche tous les arrêts à ~15 min de marche (paramétrable bien sur) et envisage cet arrêt comme point de départ. Il faut donc une recherche concentrique autour du point de départ, là où une heuristique vise juste à éviter d’étudier ce qu’il y a à gauche si on veut aller à droite.

      Il y a une deuxième différence : le rayon de recherche est très restreint. On parle de 5 km à vélo, à la rigeur 20km en voiture, jamais de trajet qui traverse la France.

      La performance du composant Dijkstra n’est donc absolument pas un problème et la simplicité du code prévaut :)

Suivre le flux des commentaires

Note : les commentaires appartiennent à ceux qui les ont postés. Nous n'en sommes pas responsables.