Algorithmes de recherche d’itinéraire

Algorithmes de recherche d’itinéraire

Algorithmes utilisés par les applications

L’algorithme de Dijkstra est un très bon algorithme de recherche d’itinéraire, classique et bien éprouvé. Il trouvera à coup sûr le chemin le plus court d’un point A à un point B en explorant l’entier du graphe, quelle que soit la complexité de ce dernier. Cependant, dans le monde réel, le réseau routier est un graphe relativement simple de type planaire, c’est-à-dire que si on le dessine sur un papier les arcs (routes) ne se chevauchent pas. De plus, les applications existantes ne doivent pas forcément retourner le meilleur chemin, mais peuvent se contenter d’un chemin suffisamment court. Des systèmes tels que Google ou Viamichelin ne révèlent pas leur algorithme de calcul, qui fait partie de leurs secrets de fabrication. Il est vraisemblable d’estimer qu’ils n’utilisent pas simplement Dijkstra, mais plutôt des dérivés, en se servant d’heuristiques, comme le fait A*. Sans doutes utilisent-ils des heuristiques sophistiquées qui donnent un bon rapport entre la qualité de l’itinéraire calculé et l’efficacité du calcul (Golshan, 2015) (Byrne, 2015).
Les systèmes open source, quant à eux, indiquent souvent utiliser Dijkstra, A* ou les contractions hiérarchiques, parfois à choix pour le développeur.

Comparaison des différents systèmes de cartes

Les différents systèmes de cartes que nous venons de voir offrent différents avantages et inconvénients.À l’exception d’ArcGIS et de Viamichelin pour ses API, tous les systèmes sont gratuits, au moins jusqu’à un certain point. Le calcul d’itinéraires existe pour chaque système, à l’exception des données de l’Office fédéral de la topographie, mais rien n’est prévu pour les personnes à mobilité réduite. Il est en général possible de choisir le mode de transport et c’est la marche à pied qui se rapproche le plus de ce que nous souhaitons. ArcGIS gère parfaitement le contournement d’obstacle. Avec OpenStreetMap, tout est possible, le système étant ouvert et un certain nombre de librairies open source étant disponibles.Il ressort de ces considérations que deux possibilités s’offrent à nous. Soit nous voulons vraiment pouvoir calculer des déplacements en évitant absolument des obstacles. Dans ce cas, la seule possibilité est de travailler sur OpenStreetMap, avec des librairies qu’il reste à définir à ce niveau. Soit nous demandons à un outil comme Google Maps de calculer plusieurs propositions d’itinéraires et nous analysons ensuite les résultats sous l’angle de la mobilité réduite. Mais si aucune des propositions de Google Maps n’est envisageable pour l’utilisateur final, il ne sera pas possible de lui calculer un itinéraire de remplacement.

Google Maps JavaScript API – LatLng et Polyline

Nous venons de voir que l’origine, la destination et les points de cheminement pouvaient être de type LatLng. Comme nous avons utilisé cet objet par la suite, il vaut la peine de donner quelques précisions le concernant. Il est défini dans la classe google.maps.LatLng. Il représente un point définit par ses coordonnées géographiques de latitude et longitude. La latitude est comprise dans l’intervalle [–90,+90] et la longitude dans l’intervalle [–180,+180]. Une fois un LatLng instancié, on ne peut pas modifier les valeurs de longitude et de latitude. Si nécessaire, il faut créer un nouvel objet LatLng. Le constructeur admet trois paramètres. Les deux premiers sont des nombres, la latitude et la longitude, toujours dans cet ordre. Le troisième, booléen, est optionnel et est à false par défaut. Si on le met à true, l’objet acceptera des latitudes et longitudes en dehors des intervalles prévus. Sinon, ces valeurs seront converties selon des règles qu’il ne vaut pas la peine de mentionner ici, mais que le lecteur retrouvera dans les informations de Google (2017g), section #LatLng. Il existe un objet littéral LatLngLiteral, qui peut être passé au constructeur à la place des paramètres. Il est aussi accepté par la plupart des méthodes qui acceptent LatLng. Il comporte deux champs, lat et lng.

Choix des points à extraire dans la base de données

Les points sont stockés dans la base de données avec leurs coordonnées de longitude et de latitude exprimées en degrés. Nous avons imaginé plusieurs options pour opérer une présélection des points.
Nous aurions pu garder tous les points qui se trouvaient dans le rectangle dont l’origine et la destination du trajet forment deux angles opposés et dont les côtés vont d’est en ouest et du nord au sud. C’est d’ailleurs un faux rectangle, car la surface de la Terre n’est pas un plan.
Mais vu que les trajets qui seront parcourus par les utilisateurs de notre application ne dépasseront a priori pas quelques kilomètres, nous pouvons accepter cette approximation. Il faudrait agrandir ce rectangle afin de tenir compte de la tolérance que nous donnerons à la méthode isLocationOnEdge(). Mais cela ne suffira pas, car le chemin peut lui-même sortir du rectangle. Il faudrait donc prévoir un rectangle encore plus grand. Ce rectangle offre l’avantage qu’il est facile de sélectionner les points. Il faut garder tous les points dont les latitudes sont comprises entre deux bornes et dont les longitudes sont comprises entre deux autres bornes.
Mais l’inconvénient est que le rectangle sera presque carré si l’écart de latitudes et de longitudes entre l’origine et la destination sont proches et qu’il sera très étroit si l’origine et la destination ont des latitudes ou des longitudes proches. Dans le premier cas, les points se situant dans les deux autres angles du rectangle seront conservés inutilement. Dans le second cas, il y a de fortes chances que le trajet lui-même sorte du rectangle. En conclusion ce rectangle aura des proportions aléatoires en fonction de la position relative des origine et destination.

Généralités sur le crowdsourcing

Le terme crowdsourcing est un mot-valise dérivé de crowd, la foule en anglais, et de outsourcing, l’externalisation ou sous-traitance. Il s’agit bien de sous-traiter un travail à la foule (Coline B, 2016). Ce néologisme a été créé par Jeff Howe qui l’a employé pour la première fois dans un article publié en juin 2006 dans Wired, un magazine de technologie américain (Sobczak & Groß, 2010, p. 15). À noter que la Commission générale de terminologie et néologie (2014, p. 12995) propose les termes de « production participative » ou « production collaborative » pour éviter l’anglicisme crowdsourcing.
Schenk et Guittard (2012, pp. 94-95) distinguent trois situations de crowdsourcing en fonction de ce qui est requis de la foule. Dans la première, on demande aux gens de réaliser une tâche simple, mais à grande échelle. Dans la deuxième, l’organisation cherche à résoudre un problème complexe; il faut alors que les participants disposent de ressources cognitives spécifiques et rares ; ce doit donc être des experts. Dans la troisième, c’est la capacité créative des individus qui est sollicitée ; ce n’est alors ni le nombre, ni l’expertise des individus qui sont utiles. C’est bien le premier cas qui nous concerne. Nous souhaitons que les utilisateurs réalisent une tâche simple, qui ne demande pas de connaissances particulières, mais à de multiples reprises : la saisie des données pour chaque point.

Table des matières

Introduction
1. État de l’art de la recherche d’itinéraire porte à porte 
1.1. Présentation du problème
1.2. Applications semblables
1.2.1. Handimap.org
1.2.2. OpenRouteService (Rollstuhlrouting)
1.2.3. Wheelmap.org
1.2.4. Synthèse des applications existantes
1.3. Algorithmes de recherche d’itinéraire
1.3.1. Algorithme de Dijkstra.
1.3.2. Algorithme de Sedgewick et Vitter
1.3.3. Algorithmes à buckets
1.3.4. Algorithme A*
1.3.5. Contractions hiérarchiques
1.3.6. Algorithme de Bellmann
1.3.7. Algorithme FIFO
1.3.8. Algorithme d’Esopo et Pape
1.3.9. Algorithme de Floyd
1.3.10. Algorithmes utilisés par les applications
1.4. Sélection du graphe dans la base de données
1.5. Systèmes de cartes existants
1.5.1. Google Maps APIs
1.5.2. ViaMichelin
1.5.3. OpenStreetMap
1.5.4. ArcGIS
1.5.5. Office fédéral de topographie Swisstopo
1.5.6. Comparaison des différents systèmes de cartes
1.6. Librairies de traitement de cartes
2. Développement
2.1. Google Maps
2.1.1. Google Maps Directions API
2.1.2. Google Maps Javascript API – Service Directions
2.1.3. Google Maps JavaScript API – LatLng et Polyline
2.1.4. Google Maps JavaScript API – Bibliothèque Geometry
2.2. Sélection des points à analyser
2.2.1. Choix des points à extraire dans la base de données
2.2.2. Sélection des points à afficher
2.3. Implémentation dans l’application existante
2.3.1. Adaptation du menu
2.3.2. Auto-complétion des champs « De » et « À »
2.3.3. Méthode searchRoutes()
2.3.3.1 Récupération des données
2.3.3.2 Utilisation du service Directions
2.3.3.3 Traitement des marqueurs
2.3.3.4 Recentrage de la carte
2.3.3.5 Justification de la présélection par la pseudo-ellipse
2.3.3.6 Sélection par l’utilisateur de l’un des chemins affichés
2.3.4. Fonction reinitializeRoutes()
2.4. Ajout de marqueurs au début et à la fin de la route
2.5. Modification des InfoWindows liées aux marqueurs
2.6. Déploiement sur un serveur en ligne
3. Crowdsourcing
3.1. Généralités sur le crowdsourcing
3.2. Techniques de motivation au crowdsourcing
3.2.1. Participation involontaire
3.2.2. Motivation intrinsèque
3.2.2.1 Aspect social
3.2.2.2 Ludification (gamification)
3.2.3. Motivation extrinsèque
3.2.3.1 Récompense financière
3.2.3.2 Récompense liée à l’usage de l’application elle-même
3.3. Limites de la motivation au crowdsourcing
3.4. Méthodes applicables pour WE-MAP
4. Analyse
4.1. Méthodologie
4.1.1. Focus groups
4.1.2. Participants
4.1.3. Procédure
4.2. Résultats
4.2.1. Naviguer dans l’application
4.2.2. Ajouter des informations
4.2.2.1 Problème de l’activation de la géolocalisation
4.2.2.2 Taille de la carte (position.php)
4.2.2.3 Ajout d’un endroit existant
4.2.2.4 Ajout d’un endroit ne remplissant aucun critère
4.2.2.5 Divers
4.2.3. Saisie d’itinéraires
4.2.4. Fenêtre d’information
4.2.5. Carte
4.2.6. Intérêt de l’application
4.2.7. Crowdsourcing
4.3. Discussion
4.3.1. Fonctionnalités
4.3.1.1 Ajout d’informations
4.3.1.2 Saisie et calcul d’itinéraires
4.3.1.3 Fenêtres d’information
4.3.1.4 Carte
4.3.2. Intérêt de l’application et crowdsourcing
4.4. Conclusion de l’évaluation
4.5. Modifications apportées à l’application
4.5.1. Activation de la géolocalisation
4.5.2. Calcul d’itinéraire
4.5.3. Fenêtres d’information : grisé des critères absents
4.5.4. Fenêtres d’information : tooltips sur les critères
4.5.5. Fenêtres d’information : ordre des boutons « Modifier » et « Supprimer »
4.5.6. Tutoriel
5. Gestion du projet
5.1. Planification et cahier des charges
5.2. Rencontres avec les responsables du projet
5.3. Gestion du temps
5.4. Respect des délais
5.5. Outils utilisés
6. Bilan
Conclusion

Télécharger le rapport complet