Notre itinéraire n’est pas définitif, celui-ci sera modifié au grès des rencontres et des km. Dans l’idée, nous parcourrons la France en essayant de passer chez vous (la famille, les amis,…) mais également par les ateliers vélos de France.
La suite de la page n’est qu’à titre indicatif : un simple calcul d’un itinéraire optimal théorique entre tous les ateliers vélos. Cela n’est pas notre itinéraire !
Notre position et itinéraire est présenté sur la carte à droite « Où sommes-nous ? ».
Connaissez-vous le problème du voyageur de commerce ? [Ref1] C’est un problème mathématique consistant à trouver le chemin le plus court ( ou long, suivant la métrique utilisée) entre un certain nombre de villes. C’est un problème mathématique complexe (NP-Complet) puisque aujourd’hui aucun algorithme ne donne une solution exacte dans un temps correct (comprendre à l’échelle de votre vie). De nombreux programmes existent cependant pour trouver une solution approchée qui nous satisfait bien pour la plupart du temps !
Impliqué dans un atelier vélo (Les Bikers, Villeurbanne [Ref2]) et de plus en plus avec les autres ateliers de Lyon (Clavette Lyonnaise [Ref3]) et de France (liste rayons, Heureux-Cyclage (HC) [Ref4]), j’ai eu envie d’appliquer cet algorithme pour définir un trajet passant par tous ces points. Par ailleurs, finissant les études (très) prochainement, nous avons planifié un voyage à vélo en France durant cinq mois (Aout – Décembre), c’est l’occasion de lancer une ébauche de parcours et pourquoi pas venir saluer un par un ces ateliers marqué sur la carte !
Parce qu’il n’y a pas grand chose à dire sur le résultat en lui en même, je présente surtout (rapidement) la méthode utilisée pour les obtenir. C’est principalement quelques bidouilles de code Python et C++, de l’informatique donc. Pour ceux que ça n’intéresse pas, sautez directement à la partie résultats pour voir ce que ça donne !
Attention : qui dit voyage à vélo dit prendre le temps et ne pas rentrer dans une planification d’un itinéraire précis ni une volonté d’optimiser un trajet (selon moi). Le trajet présenté ici ne répond donc pas à ces critères. Il satisfait juste ma curiosité personnelle d’une boucle passant par tous les ateliers de France.
Attention bis : Je parle de France et de tous les ateliers de France : c’est plutôt faux. Je me concentre sur un voyage à vélo et donc sans trajet en avion ou bateau, exit donc l’outremer et la Corse. Désolé ! Par ailleurs, je n’ai traité que les données des ateliers de France enregistrés sur le site de l’Heureux Cyclage [Ref4], ce n’est donc probablement pas tous les ateliers.
L’ensemble du projet : script, données initiales, résultats, cartes sont disponible librement sous licence GPL à cette adresse : [Ref10].
La première étape correspond à la récolte des données, comme présenté en introduction, j’ai exporté via le site de l’Heureux Cyclage les données de chaque atelier de la base de données. On obtient alors un simple fichier CSV regroupant les informations basiques de chaque atelier : Nom, état (membre ou non du réseaux de l’HC), adresse, coordonnées GPS,… Afin de trouver un itinéraire, j’ai besoin de pouvoir positionner mes points. J’ai à ma disposition les adresses et les coordonnées GPS de chaque point. Les coordonnées GPS seront plus utiles. A la fois plus précis et plus adapté puisque OpenStreetMap [Ref5] (Carte pour affichage des résultats) permet d’importer tous les points directement à l’aide d’un simple fichier.
D’autre part, en utilisant la distance du grand cercle [Ref6], on peut calculer la distance entre deux points GPS facilement là ou il faudrait interroger un service d’itinéraire pour connaitre le kilométrage entre deux adresses.
Je supprime sans remords tous les ateliers vélos ne correspondant pas à ma zone géographique (pays limitrophes, Corse et Dom/Tom). Mon fichier final ne contient donc que trois colonnes : nom; latitude; longitude.
Un premier test me permet de vérifier que mes données sont correctes. J’utilise pour la visualisation le site web uMap [Ref6] qui permet de créer facilement des cartes personnalisées sur fond OpenStreetMap. Le gros atout pour ce projet est la fonction import : je n’ai qu’a uploader sur le serveur mes fichiers (points et itinéraire) pour qu’ils apparaissent sur la carte avec toujours la possibilité de modifier les propriétés d’affichage. uMap permet donc d’importer un fichier CSV pour la liste des résultats mais également les fichiers GPX comme nous allons le voir par la suite pour l’itinéraire.
144 ateliers sont présents sur ma carte plutôt bien répartis sur la France. Il en manque cependant dans la Champagne Ardenne, vers la Rochelle, Limoges,.. Pour passer dans toutes les villes (importante?) de France, on repassera !
La meilleure solution ne pouvant être trouvée, on utilise un algorithme permettant de calculer une solution approchée. Si celle-ci n’est pas exacte, elle nous conviendra cependant tout à fait ! Je n’ai pas recodé cet algorithme, je me suis « contenté » d’utiliser un logiciel libre proposé par Alexandre Aupetit sur son site [Ref8] en C++. Celui-ci, particulièrement bien fait et facilement modifiable rend la vie plus facile ! En outre, il possible de donner un fichier CSV en entrée pour toutes les villes. En sortie, l’algorithme donne l’ordre des villes et la distance optimale.
La distance initialement utilisée par l’algorithme est la distance euclidienne et ne prends donc naturellement pas en compte que la terre est ronde. Si ce biais peut être négligeable au niveau de la France (et encore ?), il pourrait intervenir si on venait à étendre l’utilisation au monde ou au moins à l’Europe.
L’ordre des ateliers étant obtenu, il reste à formater (et automatiser) les résultats pour obtenir un itinéraire. Le format GPX, parfaitement géré par OpenStreetMap, permet de tracer un itinéraire par une suite de points. Un fichier GPX n’est qu’un formatage XML des données avec les balises spécifiques, nous avons donc un header avec les informations de base (version, nom, …) et des traces (itinéraires) ou chaque point GPX correspond à une ligne de fichier (latitude; longitude).
Un script en Python permet de créer la trace GPX de l’itinéraire en prenant dans l’ordre (fichier sortie) pour chaque atelier ses coordonnées GPS (fichier entrée).
Ayant utilisée les coordonnées GPS des ateliers et la distance du grand cercle, j’obtiens donc un certain itinéraire à vol d’oiseau ! Oui mais voila, en vélo, on a pas encore soudé les ailes !
Pour pallier à ce problème, j’ai pu tester deux solutions.
Ma première idée était d’utiliser l’API google maps Matrix distance [Ref9] afin de créer une matrice des distances entre tous les ateliers deux à deux et d’injecter ces distances dans l’algorithme. Cela donnerait donc un nouvel itinéraire (pas forcément différent) mais plus réaliste au niveau du chemin et de la distance réelle à parcourir.
Malheureusement, je n’ai pas réussi à injecter ces distances dans le programme récupéré ou plutôt celui-ci n’a jamais convergé et donnée une solution acceptable. La matrice a cependant été construite avec un script Python interrogeant le server google maps pour obtenir toutes les distances deux à deux. Le fichier est donc disponible et il ne tient qu’à vous (nous) de le faire tourner ! Utiliser Google est le seul faux pas non libre dans ce projet. Il n’en reste pas moins utile et puissant puisqu’avec une simple requête html, Google nous renvoie le temps et la distance (entre autre) entre les deux points donnés en entrée. Encore plus fort, cette matrice de distance a été calculée avec les itinéraires cyclables proposés par Google (il favorise les pistes cyclables, petites routes,…).
Les détails d’implémentation sont disponibles dans les sources du projet [Ref10].
Cette première idée n’ayant pu aboutir, j’ai pu bidouiller pour obtenir une solution approchée : garder l’ordre actuel des ateliers à visiter mais changer l’itinéraire entre les ateliers. Explication : l’utilisation de l’algorithme génétique donne en sortie l’ordre des ateliers pour obtenir le trajet le plus court. J’ai simplement remplacé le trajet à vol d’oiseau par un itinéraire cyclable entre les dits ateliers.
Encore une fois, le service de Google maps a été mis à contribution, mais c’est cette fois l’API google maps directions [Ref12]. Pour deux points en entrée, la requête HTML renvoie un fichier JSON avec toutes les étapes (comprendre tous les changements de directions) du parcours en précisant les adresses et coordonnées GPS de ces points. Pour chaque paire d’atelier, j’ai alors reconstruit une trace GPX correspondant au trajet cyclable proposé par Google.
Attention, si en regardant de loin, ce tracé parait suivre des routes, en zoomant on s’aperçoit que les lignes ne suivent pas les routes (pas de virages entre deux points) mais correspondent bien aux changement de directions de l’itinéraire. Il en résulte encore une solution approchée de l’itinéraire mais une distance exacte puisque j’utilise le retour de la requête Google (la distance exacte entre les deux points).
Résumons :
Données en entrée : liste des coordonnées GPS des ateliers vélos de France métropolitaine
Algorithme : Ordre des ateliers à parcourir, formatage GPX
-> Itinéraire à vol d’oiseau
Calcul des itinéraires cyclables via GoogleMaps, formatage GPX
-> Itinéraire cyclable
Évidemment, pour obtenir le trajet parfait est réaliste il faudrait obtenir la trace GPX de l’itinéraire réel (prendre en compte chaque virage de la route) et c’est potentiellement un nombre bien bien important de point GPS.
Cette deuxième approche nous donne un bon résultat réaliste et approximée mais part de l’idée que les distances calculées via Google ne modifie par l’ordre du passage des villes.
En effet, la solution apportée définit le passage de la ville n à la ville n+1 en fonction de la distance du grand cercle (via coordonnées GPS), il pourrait très bien en être différemment en tenant en compte de la distance réelle (via Google maps).
En général, je pense que le changement de métrique modifie peu l’ordre des villes de manière globale, la ou cela peut sûrement jouer, c’est au sein des villes ou le nombre d’ateliers est important : Paris, Lyon, Grenoble,…
La carte uMap est disponible ici.
Rien de plus parlant que de visualiser vous même la carte ! Quelques chiffres tout de même :
Quelques commentaires sur la carte et l’itinéraire choisi :
Aller, en bonus, la carte avec les pays limitrophes, ici.
Voila comment, avec quelques données et quelques outils (pour la plupart libre), il est possible de définir un itinéraire optimal. Comme présenté en introduction, ces itinéraires n’ont aucune finalité si ce n’est montrer comment faire un tour de tous les ateliers vélos de France !
Bien sur, pour nous qui seront sur cette route parfois, ce sera un guide et une manière de venir vous rencontrer les uns après les autres si vous le permettez, mais ce ne sera surement pas dans cet ordre !
Pourquoi ne pas comparer dans 6 mois notre réelle trace GPX à cet itinéraire virtuel et optimisé ?
Antoine Courcelles
[Ref1] http://fr.wikipedia.org/wiki/Probl%C3%A8me_du_voyageur_de_commerce
[Ref2] http://bikers-insalyon.fr/
[Ref3] http://clavette-lyon.heureux-cyclage.org/
[Ref4] https://www.heureux-cyclage.org/
[Ref5] http://openstreetmap.fr/
[Ref6] https://fr.wikipedia.org/wiki/Distance_du_grand_cercle
[Ref7]] http://umap.openstreetmap.fr
[Ref8] http://labo.algo.free.fr/code/tspgen/tspgen.html
[Ref9] https://developers.google.com/maps/documentation/distancematrix/
[Ref10] https://gitlab.com/pilotecivil/voyageurCommerce_HC/tree/master
[Ref11] http://umap.openstreetmap.fr/en/map/atelier-velo-hc_39492#6/46.950/3.757
[Ref12] https://developers.google.com/maps/documentation/directions/
3 comments on Atelier Vélo: