Data & GIS tips: Parcourir le Monde

Quel est l'itinéraire idéal pour parcourir le Monde ? Combien de temps de vol cela prendrait ? Quels sont les deux pays les plus distants l'un de l'autre ?
Dans ce post, j'ai fait mumuse avec la carte du globe, et appris des choses au sujet des distances orthodromiques et des voyageurs de commerce. Bon voyage !

Dernièrement, j'ai eu un échange avec @matamix au sujet du calcul de trajets permettant de couvrir un ensemble de points de façon optimale.

Nous avons échangé au sujet du code, puis une question m'est venue : dans quel ordre devrais-je visiter les différents pays, dans l'éventualité d' un tour du monde (rêvons un peu). C'est la problématique du voyageur de commerce, qui doit démarcher un certain nombre d'adresses en un minimum de temps. Il s'avère que la problématique du voyageur de commerce peut s'appliquer à des domaines non spatiaux, comme ordonner des séquences génétiques, voire regrouper des individus (au sens statistique) selon leur proximité : intéressant !

"Attrape-moi si tu peux !"

Tout d'abord, il faut se poser la question des distances entre les différents pays. L'espace dans lequel on doit travailler n'est pas euclidien, plan, mais sphérique. Ainsi, pour rejoindre le Japon depuis les Etats-Unis, inutile de traverser l'Atlantique, bien sûr. Les distances que l'on doit calculer sont les distances de grands cercles ou orthodromiques. Il existe apparemment différentes méthodes, la plus courante étant celle utilisant la loi sphérique des Cosinus

Sous R, on peut calculer 4 sortes de distances des grands cercles grâce au paquet geosphere.

J'ai récupéré les contours des pays depuis le magnifique Natural Earth, déterminé le centre des pays, et calculé les distances entre chaque, de sorte à réaliser une matrice de distance entre les différents pays. Cette matrice peut être vue comme un réseau constitué de noeuds : les pays, connectés entre eux par des arêtes de poids égal à la distance qui les sépare.

On obtient une matrice des distances orthodromiques, dont voici ci-dessous une illustration, avec 177 lignes et 177 colonnes (autant de pays que dans la couche des pays), soit 177^2 "cases". Plus la couleur est claire et plus la valeur de distance est grande. On voit que la diagonale est obscure. Les poids sur celle-ci sont nuls, puisque la distance de la France à la France est nulle. On voit que la matrice est symétrique puisque la distance, à vol d'oiseau, est la même de la France à l'Espagne que de l'Espagne à la France.

Entrez dans la matrice...

D'ailleurs, à partir de cette matrice, je me suis amusé à déterminer les trajets les plus grands entre deux pays sur le globe. En voici la liste des 10 premiers, chaque ligne représentant un trajet, dans l'ordre d'importance :

En allant du Paraguay à Taïwan, on parcourt quasiment la moitié de la Terre, la circonférence de cette dernière étant de 40 075 km

Et voici la carte correspondante pour les 5 plus grands trajets :

De même, voici la liste des pays les plus "isolés" :

Revenons à nos moutons...ou plutôt à nos voyageurs de commerce. Maintenant que notre matrice a été constituée, nous pouvons calculer le chemin optimal qui parcourt tous les noeuds une seule fois en cumulant un poids minimal (une distance minimale). Il existe plusieurs méthodes permettant de résoudre la problématique du voyageur de commerce. Dans un premier temps, j'ai tenté la plus commune, la méthode des plus proches voisins, mais elle me trouvait un itinéraire assez bizarre.

Le voyageur de commerce qui avait mal planifié son voyage

En fait, c'est normal : la méthode des plus proches voisins prend un point au hasard, détermine le point le plus proche, et répète l'analyse de proche en proche jusqu'à ce que tous les points aient été visités. Une variante prend comme point de départ chaque noeud, compare les tournées, et choisit la meilleure. Cet algorithme est assez basique.

C'est avec l'algorithme Concorde que j'ai obtenu le meilleur résultat. Voici ce que dit Wikipédia à propos de Concorde :
"a state of the art implementation”
“one of the best exact TSP solvers currently available.”
“is widely regarded as the fastest TSP solver, for large instances, currently in existence".
Bref , il s'agit du voyageur de commerce le plus performant du monde, apparemment. Il doit être milliardaire à l'heure qu'il est !

Voici donc l'itinéraire que j'ai pu trouver pour parcourir les pays du monde entier, prenant en compte les distances sphériques entre pays. On voit que j'ai aussi inclus l'Antarctique : soyons un peu aventureux !

Carte avec les fuseaux horaires

Voici un extrait des pays, dans l'ordre, au moins pour les premiers (ou les derniers, selon le sens où l'on va) :

Bon, Corée du Nord, 16e dans la liste, on passe ?

En distance, en tout, cela représente un peu plus du tiers de la distance Terre-Lune, cette dernière étant de 384 400 km, et entre trois et quatre fois le tour de la Terre

Je me suis demandé combien de temps de vol cela représenterait pour parcourir tout ça. Il existe un site appelé travelmath qui donne le temps de vol entre tous les pays.

(et 11 secondes)

Avec un petit chouilla de scraping - rien de compliqué - j'ai pu récupérer ces temps tout le long de mon itinéraire, soit pour 176 couples origine-destination. J'ai fait le calcul : il faudrait 12 jours ! pour effectuer cet itinéraire. En bref, si vous projetez une année sabbatique, ça vous fait un jour à passer dans l'avion par mois en moyenne, pas très reposant...et peu écologique !

Dataventures

Bon, je dois vous avouer qu'utiliser le Concorde (l'algorithme) n'a pas été forcément une mince affaire. Dans un premier temps j'ai testé l'outil Concorde en interface graphique et me suis rendu compte qu'il fournissait des bons résultats :

Pas mal !

Mais le souci, c'était que visiblement, ce dernier ne prenait en compte que les fichiers de coordonnées, et pas les matrices de poids !..

J'ai essayé de convertir ma matrice de distances orthodromiques en coordonnées avec un échelonnage multi-dimensionnel et une fonction de R appelée cmdscale, mais cette méthode est loin d'être optimale car j'avais en coordonnées le Cameroun plus proche de la France que la Belgique (!). Ca m'a un peu trotté cette histoire jusqu'à ce que je conclue, bêtement, que cela venait du fait que l'espace dans lequel raisonne cmdscale ne peut prendre en compte la nature sphérique des distances (c'est comme si on était dans une autre dimension avec ma matrice).

Comme un petit problème..

J'ai donc dû me rabattre sur les exécutables source. J'ai téléchargé Concorde depuis un site universitaire canadien

Le site, qui n'a peut-être jamais crashé, contrairement à son outil éponyme

A noter que la licence ne prévoit qu'une utilisation académique, et non commerciale, malgré le nom de l'algorithme ;-) L'outil est exécutable sous Windows grâce à Cygwin, un émulateur Linux. Du coup, j'ai installé Cygwin en 64 bits. Hors, ça ne fonctionnait pas. Je me suis aperçu après moult recherches que Concorde.exe fonctionnait avec Cygwin 32 bits, et non 64 bits. Bon, finalement, lorsque concorde.exe a affiché l'aide dans l'invite de commandes, j'étais soulagé !

**Alleluïa**

Une fois tout bien configuré, j'ai pu utiliser Concorde dans R après avoir donné le chemin via concorde_path (youpi !) :

Cool, ça marche. Le rouge, c'est juste un avertissement

Allez, pour finir, voici des cartes que l'on trouve sur le web, qui donnent le chemin le plus court pour parcourir la planète (pas si éloignées que ça de la mienne) :