L’idée était simple : trouver le point optimal sur une carte pour que n personnes se rencontrent, autrement dit le barycentre. Au début j’ai simplement calculé la moyenne des latitudes et des longitudes, mais la distance entre deux longitudes dépend de la latitude… C’était donc clairement insuffisant. J’ai ensuite utilisé la distance orthodromique (Great Circle), Vincenty aurait été plus précis mais un peu excessif pour ce projet.

Application Android

La moyenne latitude/longitude suffisait pour prototyper une petite application et valider les distances, ce qui m’a permis de découvrir la plateforme Google Maps API et l’intégration des cartes dans Android.

Nouvelle manière de calculer le barycentre

J’ai mis au point une technique qui projette beaucoup de points sur la carte, sélectionne le meilleur puis relance un tir de points dans une zone plus restreinte autour de lui. C’est un peu comme un algorithme génétique où seul le meilleur individu est conservé et où les mutations diminuent au fil des générations. Tant que la fonction de coût est continue avec un minimum local unique, ce n’est pas un problème.

Cette approche cherche le point qui minimise la somme des distances à toutes les entrées.

Autre objectif ajouté : le point devait se situer sur les terres.

J’ai eu quelques difficultés à générer un dégradé à trois couleurs, ce qui a donné des résultats assez amusants :

Mais j’ai fini par stabiliser le programme et, après un léger montage pour ajouter la carte, obtenir ce graphique :

• Du bleu vers le rouge, le coût augmente.
• En vert puis violet foncé, les points qui explorent des zones de plus en plus petites autour des meilleurs candidats.
• En rose, les points situés sur les terres, cherchés dans une zone qui grandit autour du barycentre trouvé précédemment.

(Le point violet est le barycentre trouvé par la méthode, confirmé par la carte de coûts où le bleu correspond à un coût faible et le rouge à un coût élevé.)

Site web

Pour toucher davantage d’appareils, j’ai aussi décidé de créer une version web.

Améliorations

1. Ajouter l’import de lieux depuis un fichier (CSV, GPX, KML, …).
2. Trouver le « barycentre de voyage » qui minimise le temps de trajet total en voiture, via des APIs de matrices de distances (fonctionnel mais encore à optimiser pour réduire les appels et afficher toutes les routes et durées sur la carte).
3. Affiner l’algorithme.
4. Utiliser OpenLayers pour s’affranchir des APIs propriétaires de Google.
5. Rendre les voyages facilement partageables et dépendants du temps.