Playing - Le voyageur de commerce

Parcourir toutes les communes d'un département en empruntant le plus court chemin avec l'algorithme 2-OPT
d3js5.x jquery3.2.1
Sources :

Introduction

Le problème du voyageur de commerce est un problème très connu en mathématiques car d'apparence simple il s'avère qu'il est impossible de calculer la meilleure solution à partir d'un certain nombre de villes dans tous les cas. L'idée est qu'une personne doit parcourir un certain nombre de villes tout en minimisant la distance totale parcourue. Wikipedia donne tous les détails sur ce problème.


La situation de départ est générée aléatoirement. Nous prenons la liste des communes du département sélectionné pour construire un parcours au hasard. A partir de cette situation, l'algorithme parcourt chaque ville dans une boucle principale et pour chacune de ces villes teste l'inversion avec toutes les autres villes. Ce processus se matérialise par les cercles bleu et rouge. Si le parcours global est plus court on procéde à la réécriture de ce parcours.

Cette visualisation permet de voir à quel point l'algorithme est peu efficace lorsqu'il teste des villes à l'autre bout du département. Il y a surement des optimisations à faire mais elles ne sont pas évidentes à définir. En revanche si on a la patience d'attendre, le résultat final est plutôt bon.

Complexité

Pour vous donner une idée de la complexité du problème, nous devons vous parler de Complexité en temps, il s'agit d'une mesure utilisée en algorithmie pour déterminer la complexité d'un traitement en fonction de la taille de son entré (N). Par exemple pour compter le nombre d'éléments dans une liste on dit que sa complexité est O(N), c'est-à-dire qu'il faut parcourir chaque élément une seule fois pour les compter. Ainsi lorsque N vaut 1000 on doit faire 1000 opérations. En revanche pour le problème du voyageur de commerce la complexité est O(1/2 * (N-1)!), ainsi lorsque N vaut simplement 25 (donc 25 villes) il faut faire 310224200866619719680000 opérations. Maintenant regardons un peu ce que savent faire nos machines et parmi elles les serveurs de calcul. Aujourd'hui en 2018, les meilleurs calculateurs font (on arrondit) 10 milliards de milliards d'opérations par secondes. Pour notre exemple à 25 villes cela donne 8 heures de temps de traitement. Mais si on passe à 30 villes on obtient 4 * 10^11 secondes ou 14 000 siècles. Autant dire que nous n'aurons pas le résultat tout de suite.

Problème P = NP

On dit du problème du voyageur de commerce qu'il est NP-complet (Non déterministe Polynomial), que sa complexité ne permet pas une résolution déterministe en temps polynomial (typiquement x^y). Le problème P = NP est l'un des 7 problèmes du prix millénaire et sa résolution permet de gagner un million de dollars. Les mathématiciens ne savent pas si cette affirmation est vraie, est-ce que tous les problèmes NP-Complet peuvent être résolus en temps polynomial (P), ils n'ont pas pu prouver que c'était faux en tout cas...

Heuristique 2-opt

Pour résoudre notre problème du voyageur de commerce nous utilisons une heuristique, c'est-à-dire une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte. L'exemple ci-dessous montre comment cette méthode fonctionne, elle va être appliquée de manière itérative sur tous les couples de noeuds et l'opération est répétée jusqu'à ne plus obtenir d'amélioration. A chaque étape on recalcule la nouvelle distance totale et on conserve le parcours si cette distance est inférieure à la meilleure. Cet algorithme a l'avantage d'avoir une complexité raisonnable, en O(N²). Néanmoins un seul passage sur tous les couples de noeuds n'est pas suffisant, une inversion pouvant rendre possible une nouvelle optimisation. Pour cette raison l'algorithme doit être répété jusqu'à ne plus obtenir aucune amélioration, dans notre cas nous le répétons 10 fois au maximum.

Le parcours (a,b,c,d,e,f,g,h,i,j,k) est ainsi transformé en (a,b,c,d,i,h,g,f,e,j,k). Dans le code source c'est la fonction swap qui réalise cette opération. On peut noter que le parcours entre e et i est inversé. 

function swap(e, i, tour) {
	var size = tour.length;
	var newerTour = [];
	
	// 1. take tour[0] to tour[e-1] and add them in order to newerTour
	for (let c = 0; c <= e - 1; c++) {
		newerTour[c] = tour[c];
	}
	
	// 2. take tour[e] to tour[i] and add them in reverse order to newerTour
	var change = 0;
	for (let d = e; d <= i; d++) {
		newerTour[d] = tour[i - change];
		change++;
	}
	
	// 3. take tour[i+1] to end and add them in order to newerTour
	for (let e = i + 1; e < size; e++) {
		newerTour[e] = tour[e];
	}
	return newerTour;
}
Toujours vérifier ses données

Nous avons eu beaucoup de difficulté à trouver les points correspondant au centre des communes et avons dédié un tutoriel à ce sujet : De l'importance de vérifier ses données

Vous trouverez dans le code source le traitement principal qui itère sur le parcours. Il est loin d'être optimisé car inséré dans une fonction d3.timer afin de réaliser l'animation visible sur cette page. En revanche le code qui calcule la distance entre deux coordonnées est intéressant et peut servir dans d'autres contextes. 

// get distance between two coordinates in km
function getDistance(lat1, lat2, lon1, lon2) {
	var R = 6371; // Radius of the earth

	var latDistance = toRad(lat2 - lat1);
	var lonDistance = toRad(lon2 - lon1);
	var a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
           + Math.cos(toRad(lat1)) * Math.cos(toRad(lat2))
           * Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
	var c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
	var distance = R * c;

	return Math.round(distance); // in km
}

Comme toujours la section commentaire ci-dessous permet d'échanger sur ce problème et si vous connaissez un autre algorithme nous pouvons surement le mettre en oeuvre.

COMMENTAIRES

Cat

Boujour,

Bravo pour ce sujet et l'ensemble de vos exemples très instructifs des possibilités offertes par l'open Source..

Il semble que vous vous soyez intéressé à la Routing Machine… Un Control Geocoder existe par exemple à ce lien https://github.com/perliedman/leaflet-control-geocoder pour afficher un lieu. Une recherche comme "Nancy" propose aussi bien la ville française que celle des états unis !

Selon ma compréhension des informations fournies par l'auteur, l'option geocodingQueryParams permettrait de limiter une recherche sur un pays donné, avec ou sans "nominatim".

Quel est la syntaxe attendue pour limiter la liste trouvée, pour la France, (voire également France et pays limitrophes…) ? Merci par avance !

L.Control.Geocoder.nominatim({geocodingQueryParams: 'FR'});
ou
L.Control.Geocoder.nominatim({geocodingQueryParams: 'fr'});

… apparemment ne fonctionnent pas...

Cordialement,

Cat

Pour information une solution fonctionnelle trouvée en redéfinissant le contrôle. La liste est ainsi limitée au territoire Français :
var osmGeocoder = new L.Control.geocoder({
placeholder: 'Rechercher...',
errorMessage: 'Lieu inconnu !',
geocoder: L.Control.Geocoder.nominatim({geocodingQueryParams: {countrycodes: 'fr'}})
});

Reste que seul un pays est possible (pas de possibilité de fr et ch pour France et Suisse par exemple...

ericfrigot

Bonjour et merci d'avoir parlé de ce sujet. Je ne connaissais pas cette librairie qui m'a l'air très intéressante ! Peut-être un futur tutoriel :) Je n'ai pas testé mais il y a un 's' à countrycodes, est-ce que vous avez essayer de passer un tableau ? countrycodes : ['fr', 'ch']. Sinon il faudra effectivement faire deux requêtes différentes.

Cat

Bonjour,

Héhé comme quoi on en apprend tous les jours !

Grace à votre judicieuse remarque sur le "s" je complète mes connaissances et effectivement c'est bien une possibilité de tableau !

Lu à ce lien : https://nominatim.org/release-docs/develop/api/Search/#parameters
countrycodes=<countrycode>[,<countrycode>][,<countrycode>]...

Mais il existe d'autres options : viewbox, bounded etc...

Syntaxe correcte en isolant ou non le tableau :
// Limiter les recherches à la France et ses 8 frontières plus Pays-Bas et Autriche
var MyPays = [['fr', 'be', 'lu', 'de', 'ch', 'it', 'mc', 'es', 'ad', 'nl', 'at']];

var osmGeocoder = new L.Control.geocoder({
placeholder: 'Rechercher...',
errorMessage: 'Lieu inconnu !',
geocoder: L.Control.Geocoder.nominatim({geocodingQueryParams: {countrycodes: MesPays}})
});

Rechercher "Forclaz" trouve bien ce col dans les 2 pays : France et Suisse.

Merci à vous !

PS: En respectant les termes d'utilisation de Nominatim cet Open Source offre beaucoup de possibilités pour préparer nos vacances en utilisant une liste de Point d'intérêts comme cette dernière : POIs France voire utiliser le géocodage inversé pour localiser une photo disposant de coordonnées GPS en drag in drop etc... Donc de nombreuse idées peuvent émerger !

kin

Pour les données des villes, par pays, région, département etc. tu peux utiliser l'overpass-turbo : https://overpass-turbo.eu/ avec ce style de requête :
"area[name="France métropolitaine"];(node[place="city"](area););out;" => choppe l'ensemble des villes de France
En sortie tu peux choisir JSon, CSV, XML etc. Très pratique !

Charles Mougel

Bonjour,
Superbe illustration du problème Mathématique théorique avec des données réelles : les communes.
Une petite remarque pour ce qui concerne une éventuelle application pratique : dans la réalité, deux communes voisines n'ont pas toujours une route les reliant à vol d'oiseau, il serait alors nécessaire d'ajouter un tableau de distances par la route pour une résolution réaliste du problème (je pense aux hautes alpes et ses vallées abruptes... ;-)
Joli travail, très inspirant, merci.

ericfrigot

Bonjour,
Merci pour votre commentaire, ça fait toujours plaisir. J'avais regardé pour intégrer la distance réelle (par la route donc) mais le problème vient du temps de réponse des APIs existantes. Même pour l'exemple de la Guyane avec ses 22 communes, ça aurait pris trop de temps de récupérer en direct les distances. L'autre solution aurait été de préparer des matrices avec ces distances ce qui me semble déjà plus réaliste.

kin

Bonjour,
Pour les distances, tu peux regarder du côté d'Open Source Routing Machine, c'est extrêmement rapide

ericfrigot

Merci beaucoup pour la mention de ce service, ça a l'air génial et extrêmement rapide ! Je vais peut-être tenter une nouvelle version avec ce service et l'algorithme Recuit simulé (Simulated annealing) pour faire une visualisation un peu plus esthétique.