Valhalla - carte isochrone et calcul d'itinéraire

Contexte

En 2015, j'avais écrit un article sur comment afficher des points sur une carte⁴, avec Leaflet. J'étais resté sur une utilisation simple.

En 2021, ayant assisté à une présentation, mentionnant les cartes isochrone, je me suis demandé s'il était possible de générer ce genre de carte avec OSM/Leaflet.

La réponse est : oui, mais !

Alors, oui, c'est faisable, mais ce n'est pas forcément simple (en tout cas, aussi simple que d'afficher des points sur une carte), et les services en ligne pour générer les données geojson sont ou bien payants ou bien limités à une zone ou bien limité à nnn requêtes par mois, nnn étant un nombre assez faible.

Valhalla

Inspiré de la mythologie nordique⁵, Valhalla est un logiciel libre et open source, composé de divers outils, notamment :

• THOR (Tiled, Hierarchical Open Routing) ;
• ODIN (Open Directions and Improved Narrative) ;
• TYR (Take Your Route).

Et d'autres (Baldr, Loki, Midgard, Sif, Skadi, Meili, Mjolnir).

Pourquoi avoir choisi ici Valhalla et non OSRM ? OSRM chargeant la totalité des données en RAM pour des performances accrues, ça peut nécessiter une quantité de RAM très élevée (tousse 128 Go de RAM /tousse), et nécessitant de générer la totalité des nodes pour le routage. Valhalla, au contraire, plus souple (ne chargeant que les données nécessaire à la volée), mais peut s'avérer moins précis ou moins rapide au niveau routage.

Accessoirement, Valhalla supporte la génération de cartes isochrones, sans passer par des outils ou libs additionnelles.

Dernier point, et probablement le plus intéressant ici : on peut également modifier les paramètres (vitesse, notamment) à la volée, avec Valhalla, ce qui n'est pas possible avec OSRM (il faut regénérer la totalité des nœuds avec les paramètres modifiés et tout recharger en RAM).

Ici, un lien vers un tableau résumé (en anglais) entre les deux solutions : https://github.com/Telenav/open-source-spec/blob/master/osrm/doc/osrm-vs-valhalla.md#from-product-managers-perspective

Que cela soit OSRM ou Valhalla, les deux peuvent se déployer via Docker (c'est la solution que j'ai fini par retenir, ces outils sont assez complexes et ont des dépendances chiantes à gérer).

Prérequis

Au niveau matériel, c'est surtout de l'espace disque et la vitesse de transfert pour les données qui sera importante. Si on se contente d'une région française (ancien découpage en 22 régions), par exemple, pour la région Lorraine (que j'ai utilisé pour faire les tests), il faut compter environ 1 Go (un peu moins en fait).

Au niveau logiciel, Docker (https://www.docker.com/), docker-compose et un serveur web (peu importe, Apache, Lighttpd, Nginx…) seront requis. Ayant déjà lighttpd installé et me servant comme serveur de test local, je l'utiliserai. Étant donné que pour les tests réalisés ici, le serveur ne fera que servir des fichiers statiques, ce n'est pas nécessaire de sortir l'artillerie lourde LAMP⁶. Je n'ai pas testé, mais ça devrait également fonctionner avec Windows (10 ou Server), avec Docker et IIS.

Pas obligatoire, mais utile pour les premiers tests : jq (un outil CLI⁷ permettant de formater/manipuler du JSON⁸)

Installation

Installation rapide sous Debian (et dérivés). Adaptez pour votre distrib (zypper, pacman, …)

sudo apt install docker docker-compose jq

sudo usermod -aG docker alex

Remplacer alex par votre compte utilisateur.

Se déconnecter/reconnecter (dans le doute, reboute) pour que cette modification soit prise en compte.

Créer un répertoire (chez moi, c'est dans ~/work/map/valhalla).

Créer dans ce répertoire un fichier texte, le nommer "docker-compose.yml".

Copier-coller le contenu suivant dans le fichier "docker-compose.yml".

version: '3.0'
services:
valhalla:
    image: gisops/valhalla:latest
    ports:
    - "8002:8002"
    volumes:
    - ./custom_files/:/custom_files
    environment:
    - tile_urls=http://download.geofabrik.de/europe/france/lorraine-latest.osm.pbf
    - use_tiles_ignore_pbf=True
    - force_rebuild=False
    - force_rebuild_elevation=False
    - build_elevation=False
    - build_admins=True
    - build_time_zones=True

Enregistrer et fermer le fichier.

Ouvrir un terminal (si ce n'est déjà fait), se déplacer dans le répertoire contenant ce fichier docker-compose.yml

cd ~/work/map/valhalla

Exécuter docker-compose

docker-compose up --build

Cette commande (tout en un) crée le conteneur docker, télécharge les ressources, et démarre le conteneur.

Cette opération peut prendre un long moment.

Premier test

Pour vérifier que Valhalla est correctement installé et fonctionne, ouvrir un nouveau terminal, et copier-coller cette commande :

curl http://localhost:8002/route --data '{"locations":[{"lat":48.6892,"lon":6.1758},{"lat":48.6399,"lon":6.1837}],"costing":"auto","directions_options":{"units":"kilometers","language":"fr-FR"}}' | jq .

Cette commande, ici, demande à Valhalla de calculer un itinéraire entre deux points (Nancy Gare à Houdement Porte Sud/zone commerciale), en voiture.

Modifier les coordonnées [{"lat":48.6892,"lon":6.1758},{"lat":48.6399,"lon":6.1837}] par des coordonnées présentes sur votre jeu de données si c'est en dehors de la région Lorraine (ou alors, ne vous étonnez pas si un message d'erreur apparaît).

Si aucune erreur n'est trouvée et que le résultat ressemble à ceci, c'est que cela fonctionne.

{
"trip": {
    "locations": [
    {
        "type": "break",
        "lat": 48.6892,
        "lon": 6.1758,
        "original_index": 0
    },
    {
        "type": "break",
        "lat": 48.6399,
        "lon": 6.1837,
        "city": "left",
        "original_index": 1
    }
    ],
    "legs": [
    {
        "maneuvers": [
        {
            "type": 1,
            "instruction": "Conduisez vers le nord-est sur Avenue Foch.",
            "verbal_succinct_transition_instruction": "Conduisez vers le nord-est. Ensuite, Serrez à droite vers Toutes directions.",
            "verbal_pre_transition_instruction": "Conduisez vers le nord-est sur Avenue Foch. Ensuite, Serrez à droite vers Toutes directions.",
            "verbal_post_transition_instruction": "Continuez pendant 20 mètres.",
            "street_names": [
            "Avenue Foch"
            ],
            "time": 1.412,
            "length": 0.019,
            "cost": 1.589,
            "begin_shape_index": 0,
            "end_shape_index": 2,
            "verbal_multi_cue": true,
            "travel_mode": "drive",
            "travel_type": "car"
        },

        …

    ],
    "summary": {
    "has_time_restrictions": false,
    "min_lat": 48.63963,
    "min_lon": 6.175782,
    "max_lat": 48.689305,
    "max_lon": 6.194352,
    "time": 417.009,
    "length": 6.655,
    "cost": 716.95
    },
    "status_message": "Found route between points",
    "status": 0,
    "units": "kilometers",
    "language": "fr-FR"
}

Récupérer les données dans un terminal, c'est bien beau, mais ça serait mieux si on pouvait afficher ça sur une carte.

Carte isochrone

Ou comment afficher sous forme de surface, toutes les zone accessibles en un certain temps, à partir d'un point.

Par exemple : depuis la Place Stan, qu'est-ce qui est accessible en 10 minutes à pieds.

Je suis parti des fichiers d'exemples fournis avec Valhalla⁹, modifiés/simplifiés ici pour cet article.

La démo est accessible ici :

https://blog.chibi-nah.fr/images/valhalla/demo1/

Démo en vidéo, avec un service valhalla fonctionnel. On peut voir les changement des paramètres et les modifications sur la carte en temps réel.

Les fichiers de démo (la partie interactive étant commentée) sont disponibles dans cette archive zip : https://blog.chibi-nah.fr/images/valhalla/demo1/demo1.zip

Pour réactiver la partie interactive, comme sur la démo vidéo, ouvrir le fichier js/isochrone.js

Descendre à la ligne 66 (dans la fonction getContours()), et supprimer ces caractères :

/*

Descendre à la ligne 78, et supprimer ces caractères :

*/

Descendre à la ligne 81, et supprimer cette ligne :

let url = "isochrone.json";

Enregistrer.

Maintenant, le script chargera les données depuis le service valhalla écoutant sur http://localhost:8002, comme indiqué à la ligne 67.

Au niveau technique, pas grand chose à dire en fait. Toutes les opérations se font dans la fonctione isochrone.js.

À la ligne 2, on définit les coordonnées de départ (le premier point).

const initLocation = {lat: 48.69354, lng: 6.18327};

Ici, ces coordonnées correspondent à la Place Stanislas, à Nancy (Lorraine/Grand-Est, France, Europe).

Juste en dessous, on initialise Leaflet, et on sélectionne le serveur de tuiles b.tile.openstreetmap.org. (modifier http/https si nécessaire).

Les fonctions suivantes, parseContour(), createMarker(), onLocationChanged(), onMapClick()` ont été récupérées quasiment telles-quelles depuis les fichiers de démo. Je ne m'attarderai pas dessus. Idem pour les fonctions onTileLayerChange() et onLatLngInputChanged().

On arrive maintenant sur getContours(). Cette fonction est probablement la plus intéressante, parce que c'est dans cette fonction que l'on récupère les différents paramètres du formulaire html.

Se référer à cette page de documentation https://valhalla.readthedocs.io/en/latest/api/turn-by-turn/api-reference/#costing-models

notamment cette section https://valhalla.readthedocs.io/en/latest/api/turn-by-turn/api-reference/#pedestrian-costing-options

pour en savoir plus sur les différents paramètres gérés.

Donc, dans getContours(), on se retrouve avec ce gros pavé de code :

let url = 'http://localhost:8002/isochrone?json=';
let json = {}
json['locations'] = [{"lat":coord.lat, "lon":coord.lng}];
json['costing'] = 'pedestrian'
json['costing_options'] = {"pedestrian":{"walking_speed":document.getElementById('speed').value, "alley_factor": "1","use_tracks":"1","service_penalty":"1"}};
json['denoise'] = document.getElementById('denoise').value;
json['generalize'] = document.getElementById('generalize').value;
json['contours'] =  parseContour(document.getElementById('contours').value);
json['polygons'] = document.getElementById('polygons_lines').value === 'polygons';

url += escape(JSON.stringify(json));

On commence par définir l'adresse du serveur valhalla, via location, suivi de l'appel à Thor (via le module isochrone).

json= sera suivi d'un objet javascript sérialisé, contenant les paramètres situés juste en dessous.

• locations contient les coordonnées de latitude et longitude, ici, correspondant au point sur la carte (le curseur bleu).
• costing contient le type de déplacement. Ici, 'pedestrian' indique un déplacement à pieds.
• denoise, generalize et contours contiennent les paramètres définis dans le formulaire. Ce n'est pas forcément essentiel.
• polygons contient le type de rendu à faire, soit en lignes, soit en zones. Ça prend un booléen true ou false en paramètre.

Et enfin, LE paramètre le plus important : costing_options. Je l'ai gardé pour la fin, parce que c'est ici que tout se joue.

L'objet pedestrian contient toutes les options de routage (toutes ne sont pas utilisées ici, il y en a nettement plus dans la doc).

• walking_speed : vitesse de déplacement à pieds. Dans la démo, cette valeur est modifiable facilement via le formulaire.
• alley_factor : facteur (pénalité/coût) pour traverser les allées. la valeur par défaut étant à 2, je l'ai définie ici à 1.
• use_tracks : Une valeur de 0 indique d'exclure tout routage à travers des pistes ou sentier (dans la mesure du possible). La valeur de 1 indique d'inclure les sentiers. La valeur par défaut est de 0.5.
• service_penalty : Une pénalité appliquée sur les routes génériques. Par défaut à 0, ici, je l'ai définie à 1.

Il existe d'autre types de pénalités/coûts, comme l'utilisation de ferrys, des pentes (collines), des escaliers, etc.

Ici, je me suis limité à l'essentiel.

Calcul d'itinéraire

Parmi les utilisations possibles de Valhalla, c'est bien entendu le calcul d'itinéraire.

Par exemple, comment aller de la Préfecture à la Porte Notre-Dame à pieds.

La démo est accessible ici :

https://blog.chibi-nah.fr/images/valhalla/demo2/

Démo en vidéo, avec un service valhalla fonctionnel. On peut voir les durées changer en fonction de la vitesse de déplacement.

Les fichiers de démo (la partie interactive étant commentée) sont disponibles dans cette archive zip : https://blog.chibi-nah.fr/images/valhalla/demo2/demo2.zip

Pour réactiver la partie interactive, comme sur la démo vidéo, ouvrir le fichier js/route.js

Descendre à la ligne 36 (dans la fonction get_routes()), et supprimer ces caractères :

//

Descendre à la ligne 37, et supprimer cette ligne :

const url = 'route.json';

Enregistrer.

Maintenant, le script chargera les données depuis le service valhalla écoutant sur http://localhost:8002, comme indiqué à la ligne 20.

On définit le point de départ avec startPoint, le point d'arrivée avec endPoint, ainsi que les coordonnées du centre de la carte avec initLocation.

const initLocation = {lat: 48.69629, lon: 6.18186};
const startPoint = {lat: 48.69353, lon: 6.18327};
const endPoint = {lat: 48.69935,lon: 6.17778};

Juste en dessous, on initialise Leaflet, et on sélectionne le serveur de tuiles b.tile.openstreetmap.org. (modifier http/https si nécessaire).

La fonction get_routes() contient les paramètres pour le calcul d'itinéraire.

json['locations'] = [startPoint,endPoint];
json['costing'] = 'pedestrian';
json['costing_options'] = {"pedestrian":{"walking_speed":document.getElementById('speed').value, "alley_factor": "1","use_tracks":"1","service_penalty":"1"}};
json['directions_options'] = {"units":"kilometers","language":"fr-FR"}

• locations contient les points de départ et d'arrivée.
• costing correspond au moyen de transport. Ici, piéton pedestrian
• costing_options contient les contraintes sous forme de coût pour le déplacement à pieds. On retrouve notamment la vitesse de déplacement, ici, lue via le champ speed du formulaire sur la page de démo. Cela permet de recalculer la durée en fonction de la vitesse de déplacement.
• directions_options contient l'unité de mesure pour les déplacements et la langue à utiliser pour les instructions.

La fonction build_geojson() a été modifiée pour pouvoir afficher les instructions pour l'itinéraire.

let duration = leg.summary.time;
let minute = (duration / 60).toFixed(0);
let seconde = (duration % 60).toFixed(0);

roadTrip += "<h3>Itinéraire</h3>"

roadTrip += "<b>Durée totale : </b>" + minute + "minutes " + seconde + " secondes<br />"
roadTrip += "<b>Distance totale : </b>" + leg.summary.length + " km<br /><br />"

leg.maneuvers.forEach( (maneuver) => {

    if(maneuver.type == 4) {
        roadTrip += "<b>type : </b>" + maneuver.type;
        roadTrip += " ; durée : " + maneuver.time + ' secondes<br />';
        roadTrip += "<b>instruction : </b>" + maneuver.instruction;
    }
    else {
        roadTrip += "<b>type : </b>" + maneuver.type;
        roadTrip += " ; durée : " + maneuver.time + ' secondes<br />';
        roadTrip += "<b>instruction : </b>" + maneuver.instruction;
        roadTrip += "<br />" + maneuver.verbal_post_transition_instruction;
        roadTrip += "<br /><br />";
    }
});

• leg.summary contient les données d'informations sur l'itinéraire, notamment la durée via time et la distance via length.
• leg.maneuvers contient chacune des étapes pour l'itinéraire. C'est pour cela que l'on utilise une boucle, et chaque instruction se retrouve alors dans l'objet maneuver.

Pour chaque étape (ou maneuvre) :

• type contient le type. Par exemple 1 pour départ, 4 pour arrivée… pour plus de détails, lire la documentation de Valhalla.
• time contient la durée de la maneuvre
• instruction contient les instructions (tourner à droite dans Rue des Dominicains)
• verbal_post_transition_instruction contient des instructions supplémentaires (continuer pendant 60 mètres).

Pour le reste, quasiment pas de modifications par rapport à l'exemple.

Conclusion

Cet article n'a fait qu'effleurer ce qui est faisable avec Valhalla. Cependant, je pense que c'est un bon point de départ pour quiconque souhaiterait se lancer dans l'aventure, aussi bien pour générer des cartes isochrones ¹⁰ que pour faire du calcul d'itinéraire¹¹.

Licence

Le projet Valhalla et les démos de ce projet¹² étant sous licence MIT, les exemples et code source présentés sur cette page sont également sous licence MIT.

Les données OSM sont sous licence ODbL : https://www.openstreetmap.org/copyright/fr

--