Le problème du voyageur de commerce

Au moment de sa mort je travaillais sur un outil de cartographie et je pensais au problème du voyageur de commerce. Par association, je me suis dit qu'en utilisant une courbe fractale qui remplirait un rectangle on pourrait faire une projection de données en 2D (coordonnées d'un point sur une carte) sur des coordonnées en une seule dimension (numéro du point sur une courbe). Cela ne donne pas la réponse optimale au problème du voyageur de commerce, mais cela donne une solution de manière instantanée pour des problèmes de plusieurs centaines de points.

J'ai pensé à utiliser la courbe de Hilbert, mais je me suis dit que la courbe de Sierpinski serait peut-être mieux. J'ai donc cherché sur internet si je pouvais en trouver une liste de coordonnées. J'ai finalement fini par trouver les coordonnées pour un tableau de 100*100=10 000 points sur ce site :

http://www2.isye.gatech.edu/~jjb/mow/mow.html

...site qui présente une manière de résoudre le problème du voyageur de commerce en utilisant la projection de coordonnées sur une courbe fractale. Ce qui relativise la portée originale de mon idée.

J'ai quand même inséré le processus dans excel pour faire des tests. Une chose est certaine, c'est sa rapidité (en premier lieu), puiqu'il suffit de transformer des coordonnées pour qu'elles tiennent dans le carré et le travail est simplement une recherche dans une colonne pour trouver une valeur. En faisant un simple tri sur cette valeur on a notre trajet.

Dans le cas où tout le territoire serait à visiter, on aurait une solution optimale puisqu'elle permet de tout visiter en ne faisant que de petits déplacements à chaque fois. Mais si le problème contient des différences de densité de villes à visiter, on va s'éloigner de l'optimal.

J'ai donc compensé cela de 2 manières :

Un algorithme pour intégrer un point qui serait resté seul à une partie plus proche.
Un algorithme pour défaire les petits croisements qui ne manquent pas de se produire si plusieurs points sont proches du même point de la courbe et aussi après avoir lancé l'algorithme précédent.

Alors que le problème du voyageur de commerce est un problème de la factorielle, l'utilisation de la projection le ramène à un problème de dimension k*n².

Comme je calcule toutes les distances et que je les mets dans une colonne avant de faire les optimisations, cela dépasse rapidement le nombre de lignes d'excel.

Néanmoins j'ai testé les performances de l'algorithme sur des problèmes de 50 villes, 96 villes et un autre de 250 villes. Les solutions sont plutôt honnêtes (meilleure solution pour le problème de 50 villes, 3% en plus de la meilleure solution pour le problème de 96 villes par exemple...)

Le principal problème est le temps de travail dès que le nombre de villes augmente, à 250 villes, il faut 2 heures pour faire un tour d'amélioration. Cela est principalement imputable au fait que certains tests nécessitent des calculs sur la feuille de calcul.

En réduisant les comparaisons totales et en mettant dans le VBA des calculs auparavant sur la feuille, j'ai optimisé le code de sorte que l'optimum de mon programme soit atteint plus rapidement. Néanmoins il faut au moins une demi heure pour le programme des 250 villes pour passer des 16 donnés par la fractale à 12,5 après optimisation. Soit 4% de plus que le 12 des programmes habituels.

En masquant les graphiques, optimisant le typage des variables, utilisant des tableaux en mémoire à la place de cellules excel on irait plus vite en produisant de meilleurs résultats. Néanmoins vous avez ici un outil qui vous de résoudre ce problème sans quitter excel, de manière innovante avec des résultats corrects pour des problèmes courants.

En construction

J'ai dissocié le travail dans 2 fichiers : un dans lequel on fait la saisie et l'autre qui fait le travail. Dans le second, j'ai mis un mot de passe sur le code VBA pour éviter des erreurs de manipulation. Mais le premier qui crée les données et lance le second est ouvert ce qui vous permet de l'intégrer à une de vos applications.

Ces classeurs sont en cours de réalisation pour être disponibles fin du premier trimestre 2011.