[OSM-talk-fr] Fwd: Expérience OSRM et isochrones carrés

Jeu 23 Fév 03:17:55 UTC 2017

Je pense qu'OSRM utilise une heuristique de recherche d'itinéraires basée
sur les "quadtiles" (les mêmes qui servent aussi à l'indexation des données
OSM) qui favorise des trajets trouvés dans les carrés sans forcément en
déborder pour trouver d'éventuels chemins plus courts: si on reste en
dessous d'un seuile de tolérance, pas la peine de chercher plus loin, il
continue à chercher les points intermédiaires dans ces mêmes carrés et ne
voit pas nécessairement de raison d'en sortir pour une étape intermédiaire
sur un carreau voisin si un point de départ et un point d'arrivée sont tous
les deux dans le même carreau.

Comme le calcul des isochrones tente justement de chercher des chemins les
plus courts depuis un ensemble de points identifiés (mais avec la
contrainte du point initial fixe au centre des isochrones), il y a sans
doute une faille à ce niveau si tu fais une recherche entre un point final
et ce uniquement centre au lieu de chercher les temps de parcours à partir
d'une du point d'une isochrone plus petite), car alors tu obtiens toujours
des chemins favorisant un jeu plus réduit de chemins initiaux dans ce
carreau.

Visiblement ton graphique montre bien un problème avec les isochrones qui
se superposent, au lieu de s'emboiter sans intersection (autrement dit où
la surface d'un isochrone plus petit est entièrement incluse dans
l'isochrone plus grande sans même se toucher en bordure): l'anomalie est
très visible sur les bords nord et sud du carreau, qui semble bien
corredpondre aussi aux "quadtiles" de découpage standard (comme sur les
tuiles du rendu) qui divisisent le monde entier. Sinon tu as peut-être des
problèmes aussi à estimer des temps de parcours sur certains segments, et
une exception se produit qui t'amène à prendre un autre point précédent
mais oublier de faire une estimation correcte (ou bien cette estimation est
trop grossière et conduit à éliminer trop précocément des parcours
possibles pourtant plus courts (en temps, donc tenant compte de la nature
de la route, des limites de vitesse, de la présence de feux, stops, voies
prioritaires/cédez-le-passage pour estimer ce temps à partir des distances
mesurées le long des chemins possibles, avant même de chercher d'éventuels
raccourcis transverses...).

Les isochrones théoriques les plus courts en temps ne sont pas forcément
non plus les plus pratiques: au niveau local près du point de départ ou
celui d'arrivée, on passe plus facilement par des plus petites rues/routes
plus lentes, avec plus d'intersections/stops/feux et des vitesses plus
limitées alors que pour la partie centrale du parcours on privilégie
normalement les plus grands axes.

La difficulté étant de déterminer à partir d'où on peut les prendre et
jusqu'où on peut en sortir, et en cas d'angles importants le long des
grands axes, si on peut se permettre de couper par une route plus petite:
c'est tout le calcul des isochrones qui en dépend à condition de ne pas
être trop restreint par la sélection de points intermédiaires: soit on
parcourt la totalité des noeuds d'intersection du graphe, ce qui prend
énormément de temps car ça explose de façon combinatoire, soit on en prend
juste quelques uns avec les quadtiles en choisissant de chercher unqiuement
dans les cadrans les plus favorables sur ces tests limites, on élimine
alors d'autres noeuds voisins dans le même quadtiles qui pourtant permettre
des chemins plus courts. Si on utilise cette heuristique (classique dans
les recherches d'itinéraires pour éviter "l'explosion" combinatoire), on
obtient seulement une estimation des temps, mais pas l'isochrone le
meilleur attendu.

Pourtant ce qui m'étonne ici c'est que les isochrones montrés sont
relativement courts (5,10,15 minutes) et qu'on est loin d'exploser les
limites d'une recherche exhaustive: le graphe complet explorable n'est pas
si grand que ça. Et l'heuristique d'élagage des arbres semble se déclencher
beaucoup trop tôt (ou bien pour calculer l'isochrone suivant, tu élimines
trop vite des points de l'isochrone précédent en n'en retenant que 4
points, là où il semble pourtant qu'au minimum tu devrais pouvoir en
conserver quelques centaines, en n'éliminant QUE les points qui ne sont PAS
des intersections de routes possibles mais en gardant la trace minimale
pour chacun de ces points des routes déjà visitées pour y parvenir et qu'on
ne doit pas visiter à nouveau sous peine de faire un calcul avec des
chemins incluant des demi-tours par les mêmes chemins)

Reste donc à savoir si tu as bien chargé tous les chemins possibles (mais
ça peut être coûteux en requêtes à la base de données si tu en fais pour
chaque point) ou seulement chargé les données autour de quelques points
choisis par l'heuristique.

On peut noter qu'assez souvent la base de données OSM, quand on l'interroge
sur la liste des chemins passant par un noeud, retourne une erreur après un
timeout, surtout si les chemins sont membres de grosses relations (on le
voit par exemple dans JOSM en sélectionant un noeud ou un chemin et
pressant CLTR+ALT+D pour rechercher les relations ou chemins
dépendants,alors que la base n'a aucun mal à répondre quand au lieu de
chercher à partir de l'id d'un noeud ou chemin on fait une recherche par la
plus petite "bounding box" possible, à moins de 10 centimètres autour de ce
noeud ou autour d'un noeud de ce chemin).
-

Sinon les isochrones ne sont constituées normalement que des points
atteignables (on ne peut pas atteindre les surfaces au milieu des batiments
ou des champs ou forêt, en tout cas pas en véhicule): ils sont donc
constitués uniquement d'une série de points, mais les segments qui les
joignent ensuite peuvent alors créer des polygones avec des chevauchements
d'isochrones (mais uniquement s'il y a des restrictions: sens de
circulation, ponts, tunnels).

Cependant sur ton image on voit bien où sont situés les points (sans tenir
compte des segments tracés entre eux pour former les polygones, qui sont
des approximations très grossières des temps restant à parcourir par
d'autres moyens, à pied voire à la nage et ne tiennent pas compte non plus
des interdictions d'accès, des obstacles physiques ou autres clotures de
propriétés privées), et on voit très bien que les mêmes points servent à
plusieurs isochrones distincts, ce qui n'est normalement pas possible. Il y
a donc un bogue dans ton algo qui peut retourner des temps calculés
différents entre ton noeud central de départ et ces noeuds : il est
possible par exemple que tu aies calculé non pas des temps exacts mais des
intervalles de temps arrondis, et que pour l'isochone de 15 minutes par
exemple tu vas en fait aussi inclure les points qui peuvent être atteint en
maximum 15 minutes, qui sont les mêmes points atteignables en 5 minutes
aussi retenus pour l'isochone de 5 minutes. S'il y a des intervalles de
temps, il serait toutefois bon de ne pas mélanger des minimums et des
maximums ou de réduire tous les temps calculés juste à leur valeur
minimale, il vaut mieux sans doute les pondérer, quitte à prendre partout
les temps médians mais garder uniquement en valeur secondaire les écarts de
temps possibles (je ne sais pas si tu as estimé des intervalles de temps ou
juste des temps moyens).

Philippe.

Le 22 février 2017 à 22:14, Marc Sibert <marc at sibert.fr> a écrit :

> Bonjour,
>
> Avec le temps j'arrive à faire rentrer OSM dans les applications de mon
> entreprise (grande distrib.).
>
> On a mis Addok, une base PG/PGIS et maintenant on essaie des calculs
> d'isochrones avec OSRM, mais ça nous donne des périmètres plus ou moins
> "carrés" (les tracés ici sont à 5, 10 et 15 min en voiture)
>
> Je recherche donc des interlocuteurs ayant déjà déployé OSRM dans des
> dockers.
>
> Merci de me contacter ici ou en perso (ci-dessous), je tacherais de
> documenter tout ça si ça marche.
>
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20170223/7a8ae918/attachment.htm>