Comment ça marche ?

Les données

• Les graphes sont extraits des données d’openstreetmap via le module python osmnx. Mille mercis à son créateur Geoff Boeing.
• Les adresses sont récupérées sur la base nationale d’adresses lorsqu’elles contiennent un numéro de rue, directement dans le graphe lorsqu’elle contiennent un nom de rue sans numéro, et sur openstreetmap dans les cas restants (bâtiment public, bar, …)

Les maths !

• L’algo employé pour calculer un itinéraire est le fameux algorithme de Dijkstra, ou plutôt sa variante A*. L’utilisation du concept de cyclabilité pour modifier le poid des arêtes fait qu’on ne peut plus utiliser la distance sphérique classique comme heuristique. Et le fait que les étapes soient souvent des ensembles de sommets nécessite aussi une petite adaptation qui lui fait perdre de son efficacité...
  Gérer les étapes demande un rien plus de réflexion : il s’agit d’imposer au chemin de passer par au moins une arête de chaque étapes indiquée. Quoique beaucoup plus facile à programmer, imposer de passer par juste un sommet de l’étape ne correspond pas à ce à quoi s’attend l’utilisateur : quand on dit « pour aller de A vers B, j’emprunte la rue R » c’est qu’on longe R sur une distance non nulle, et pas qu’on la traverse juste.
  Le code est dans le fichier dijksta.py.
• Les rues de chaque ville sont enregistrées dans un arbre lexicographique, ce qui permet de rechercher facilement la rue la plus proche au sens de la distance de Levenshtein (nombre de fautes de frappe) de ce qui a été tapé par l’utilisateur. Le code est là.
• Il y a aussi des arbres pour la gestion des étapes indiquées par un clic de l’utilisateur. À la base, il s’agit de R-arbres, même si la manière dont ils sont créés les rend grosso-modo semblables à des arbres quadratiques . Bien qu’il soit plus facile de rechercher le sommet le plus proche du point cliqué par l’utilisateur, il est plus pertinent de rechercher l’arête la plus proche. Les arêtes du graphes sont donc découpées en segments puis rentrées dans un « arbre quadratique d’arêtes ». Et la recherche s’effectue par un « branch and bound » . Le code est là.

L’IA

La couche d’apprentissage surpervisée est tout à fait basique. On peut dire qu’il s’agit d’un réseau de neurones à une seule couche. L’avantage est qu’elle nécessite relativement peu de données pour fournir des résultats utilisables.
En pratique, à chaque arête du graphe est associé un flottant qui représente sa cyclabilité, et qui est pris en compte par Dijkstra. Lorsqu’un nouvel itinéraire est rentré, il est comparé à l’ancien, celui qui aurait était renvoyé jusqu’ici. On augmente alors la cyclabilité toutes les arêtes qui figurent sur le nouvel itinéraire mais pas sur l’ancien, et on diminue la cyclabilité de toutes les arêtes qui figurent dans l’ancien itinéraire mais pas dans le nouveau (ces arêtes ont été évitées par le contributeur).