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.
Aller plus loin
- Annonce de l’ouverture de Navitia 2 (994 clics)
- Code source du calculateur Navitia 2 (532 clics)
- navitia.io (549 clics)
# Multimodal et autres questions
Posté par Vincent P (site web personnel) . Évalué à 7.
Bonjour,
Bravo pour la libération et la démarche d'ouverture tout d'abord !
Quelques questions :
Merci pour les précisions !
[^] # Re: Multimodal et autres questions
Posté par Tristramg . Évalué à 9.
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 BAud (site web personnel) . Évalué à 2.
ah, je viens de comprendre : TC comme Transport Collectif… ou Transport en Commun, éventuellement.
[^] # Re: Multimodal et autres questions
Posté par Vincent P (site web personnel) . É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 David Demelier (site web personnel) . É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.
git is great because linus did it, mercurial is better because he didn't
[^] # Re: Commentaires en français
Posté par AntoineD . É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 stephan.simart . Évalué à 2.
Ceci dit, les premières contributions étant Néerlandaises, ça devrait rapidement motiver tout le monde ;)
# Route de montagne
Posté par Sytoka Modon (site web personnel) . É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 Tristramg . É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 El Titi . É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 Tristramg . É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 à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.