Le problème du voyageur de commerce

Parcourir toutes les communes d'un département avec le plus court chemin

Dernière mise à jour le 13/09/2018
d3js5.x

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 Polynomial), que sa complexité ne permet pas une résolution 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

Info: 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.

comments powered by Disqus