Comment créer une liste de marche optimisée en fonction des coordonnées de longitude et de latitude?

Je travaille sur une campagne politique où des dizaines de bénévoles mèneront des promotions pour frapper à la porte au cours des prochaines semaines. Étant donné une liste avec des noms, des adresses et des coordonnées long / lat, quels algorithmes peuvent être utilisés pour créer une liste de marche optimisée.

Comme l'a dit Steve Kallestad, il s'agit d'un problème TSP, et il existe de merveilleux solveurs gratuits pour trouver des solutions approximatives.

Cela peut être trop de travail pour ce que vous recherchez, mais vous pouvez essayer d'utiliser l'un de ces solveurs en combinaison avec l'API Google Maps, pour trouver des distances de marche réelles entre vos coordonnées: https://developers.google.com/maps / documentation / directions / # DirectionsRequests

(Je n'ai jamais utilisé cette API, donc je ne sais pas à quel point ce serait facile ou efficace)

Les gens voient quelque chose d'étroitement lié au problème des vendeurs ambulants et pensent qu'il ne peut pas être résolu.

Beaucoup de travail a été fait sur ce sujet et tout cela n'indique pas qu'une solution n'est pas disponible. Selon les paramètres et la solution souhaitée, vous pourrez peut-être trouver quelque chose qui fonctionnera.

Vous voudrez peut-être jeter un œil à la bibliothèque python OpenOpt .

Une autre ressource à examiner serait le solveur et générateur TSP .

Si vous utilisez R, un package TSP est disponible .

En fait, mettre en œuvre une solution à votre problème est un peu trop à couvrir ici, mais cela devrait fournir un bon point de départ. Dans ces packages et dans la documentation des liens que je vous ai fournis, vous constaterez qu'il existe une assez grande variété de stratégies algorithmiques disponibles. Vous avez une petite région géographique et un petit nombre de "vendeurs", donc la puissance de calcul nécessaire pour calculer une stratégie dans un délai raisonnable devrait être disponible sur votre bureau.

Concrètement, vous n'avez pas besoin de trouver la stratégie absolument la plus optimale. Vous avez juste besoin d'un très bon. Choisissez un package TSP qui a l'air le moins écrasant et essayez-le.

Comme @SpacedMan l'a noté dans un commentaire , la disposition des rues aura une influence massive sur l'optimisation de la liste de promenade. Vous avez inclus uniquement "latitude et longitude" dans le titre de votre question; mais la résolution de ce problème ne conduit pas à une "liste de marche", mais à une "liste à vol d'oiseau".

En regardant votre tracé de rue sous forme de graphique, avec des poids de bord décrivant les distances, et en essayant de trouver la traversée la plus courte entre toutes les adresses requises, vous serez amené à considérer votre problème comme un " problème de chemin le plus court ". L'algorithme de Dijkstra est la solution la plus connue (il y en a d'autres); dans sa mise en œuvre naïve, il converge en O (n ² ) , ce qui peut être acceptable si vos listes d'adresses sont de taille modérée. Sinon, recherchez les versions optimisées dans les liens ci-dessus.

En ce qui concerne les bibliothèques et les ressources pour commencer à résoudre le problème, puisque vous ne spécifiez pas de langues ou de plates-formes, permettez-moi de signaler la compilation des solveurs de routage dans le wiki Open Street Maps et en général, leur page cadres et bibliothèques .

Voici une idée folle: parlez aux bénévoles qui connaissent les quartiers et qui ont déjà fait du porte-à-porte. Obtenez leurs conseils et leurs idées. Ils auront probablement des informations qu'aucun algorithme ne produira, et ces modifications seront précieuses pour toute liste de routes générée par ordinateur. Un exemple: éviter de traverser des rues très fréquentées avec des lumières lentes ou sans lumière. Autre exemple: des paires de bénévoles travaillant sur les côtés opposés d'une même rue se sentiront plus en sécurité qu'un bénévole travaillant seul dans cette rue.