<div dir="ltr"><div class="gmail_quote"><div dir="ltr">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.<div><br></div><div>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.</div><div><br></div><div>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...).</div><div><br></div><div>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.</div><div><br></div><div>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.</div><div><br></div><div>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)</div><div><br></div><div>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.</div><div><br></div><div>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).</div><div>-</div><div><br></div><div>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).</div><div><br></div><div>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).</div><div><br></div><div>Philippe.</div></div><div class="gmail_extra"><br><div class="gmail_quote"><div><div class="h5">Le 22 février 2017 à 22:14, Marc Sibert <span dir="ltr"><<a href="mailto:marc@sibert.fr" target="_blank">marc@sibert.fr</a>></span> a écrit :<br></div></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div class="h5">
<div bgcolor="#FFFFFF" text="#000000">
<p>Bonjour,</p>
<p>Avec le temps j'arrive à faire rentrer OSM dans les applications
de mon entreprise (grande distrib.).</p>
<p>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)<br>
</p>
<p>Je recherche donc des interlocuteurs ayant déjà déployé OSRM dans
des dockers. <br></p>
<p>Merci de me contacter ici ou en perso (ci-dessous), je tacherais
de documenter tout ça si ça marche.</p></div></div></div></blockquote></div></div></div></div>