Résolveur TSP
Comparaison de métaheuristiques pour le problème du voyageur de commerce
Résultats
- Implémentation de 5 algorithmes métaheuristiques pour le PVC avec contraintes réelles
- Analyse comparative sur plus de 3000 itérations par instance
- Génération de graphes personnalisés avec noeuds interdits, contraintes de précédence et péages
Résolveur TSP est un projet de recherche opérationnelle qui résout le problème du voyageur de commerce avec des contraintes réelles. Il implémente 8 algorithmes métaheuristiques et fournit une analyse statistique comparative sur 24 tailles d’instances (N de 5 à 3000 noeuds). Le solveur gère les noeuds interdits, les contraintes de précédence et les coûts de péage, avec des résultats validés sur plusieurs graines aléatoires.
Problème
Le problème du voyageur de commerce (TSP) consiste à trouver le trajet le plus court visitant un ensemble de villes exactement une fois et revenant au point de départ. Ce projet étend le TSP classique avec trois contraintes réelles: noeuds interdits (routes en travaux), contraintes de précédence (dépendances de livraison), et coûts de péage (frais d’autoroute). L’objectif minimise le coût total = distance + péages + pénalités.
Architecture
Le projet est organisé en trois couches: données (génération de graphes et gestion d’instances), algorithmes (8 implémentations métaheuristiques), et évaluation (calcul de coût et validation des contraintes).
Ma contribution: J’ai implémenté la famille Recherche Tabou (standard et variantes 2-opt), le Recuit Simulé Multi-start, et le framework d’analyse statistique pour comparer les algorithmes.
La génération produit des instances aléatoires avec paramètres configurables: nombre de noeuds (5-3000), ratio de noeuds interdits (5%), ratio de contraintes de précédence (15%), et ratio d’arêtes avec péage (20%). Chaque instance est validée avant résolution.
Huit algorithmes ont été implémentés:
- Plus Proche Voisin: Heuristique gloutonne, construit le parcours en choisissant toujours le noeud non visités le plus proche. Rapide mais glouton, n’explore pas les alternatives.
- Recherche Tabou 2-opt: Recherche locale avec mémoire et amélioration par échange d’arêtes. Le plus évolutif: le gap passe de 250% (N=10) à 250% (N=1000) quand la taille augmente.
- Recherche Tabou: Recherche locale avec mémoire, évite de visiter récemment explorées via une liste tabou. Bonne qualité mais se stabilise à 500% de gap.
- Recuit Simulé: Relaxation stochastique, accepte les pires solutions avec probabilité décline. Pointe à 700% de gap (N=200), puis descend à 500%.
- Recuit Simulé Multi-start: Exécute RS plusieurs fois avec différentes graines. Meilleure évolutivité: le gap passe de 250% à 150% pour N=3000.
- Algorithme Génétique: Approche évolutive, les populations évoluent par sélection, croisement et mutation. Ne passe pas à l’échelle: gap dépasse 2000% pour N > 200.
- Colonie de Fourmis: Intelligence essaim, les agents déposent des phéromones sur les arêtes. Gap augmente à 750% pour N=200.
- Hill Climbing Multi-start: Amélioration locale depuis plusieurs starts aléatoires. Pointe tôt à 700% de gap (N=50), ne s’améliore pas pour les grandes instances.
Patterns utilisés: Strategy pour la sélection d’algorithmes, Factory pour la génération d’instances, Observer pour le suivi de progression en temps réel, Template Method pour la logique d’évaluation partagée.
Analyse Comparative
L’expérience couvre 24 tailles d’instances de N=5 à N=3000, avec 5 graines aléatoires par instance. Les résultats montrent le gap (pourcentage au-dessus de la borne inférieure) et le temps d’exécution (secondes par instance). Total: environ 2400 solutions évaluées par algorithme, 19000+ solutions au total.
| Algorithme | Gap N=10 à 75 | Gap N=200 à 3000 | Temps d’Exécution | Évolutivité |
|---|---|---|---|---|
| Plus Proche Voisin | 300-700% | 700%+ | 0,00008s à 100s | Mauvaise |
| Recherche Tabou 2-opt | 250-550% | 250% (à N=1000) | 0,015s à 250s | Excellente |
| Recherche Tabou | 250-500% | 500% (plateau) | 0,018s à 50s | Bonne |
| Recuit Simulé | 250-700% | 500% (à N=250) | 0,08s à 70s | Modérée |
| Recuit Simulé Multi-start | 250-650% | 150% (à N=3000) | 0,12s à 100s | Meilleure |
| Algorithme Génétique | 350% à 2000%+ | 2000%+ | 0,5s à 150s | Mauvaise |
| Colonie de Fourmis | 250-750% | 750%+ (à N=200) | 0,25s à 60s | Mauvaise |
| Hill Climbing Multi-start | 350-700% | N/A (pointe à N=50) | 0,0035s à 70s | Mauvaise |
Le recuit simulé multi-start et la recherche tabou 2-opt sont les seuls algorithmes dont le gap s’améliore quand N augmente. L’algorithme génétique et la colonie de fourmis ne passent pas à l’échelle au-delà des petites instances.
Ce Que J’ai Appris
- La sélection d’algorithme dépend de la taille: Pour N plus petit que 50, le plus proche voisin est une base raisonnable. Pour N plus grand que 100, seul le RS multi-start et Tabou 2-opt s’améliore.
- Le paramétrage compte plus que le choix d’algorithme: La sensibilité du recuit simulé au schedule de cooling a eu plus d’impact que changer d’algorithme.
- L’algorithme génétique a besoin de meilleurs opérateurs: Le croisement par ordre ne préservait pas les bons sous-parcours. J’essaierais PMX (croisement partiellement mapper) à la place.
- Le multi-start est sous-utilisé: Exécuter N fois avec différentes graines coûte peu mais réduit significativement la variance.
Compromis Clés
Qualité vs Temps: La recherche tabou 2-opt atteint le meilleur ratio qualité/temps pour les grandes instances (N > 100). Le plus proche voisin est le plus rapide mais la qualité se dégrade rapidement.
Évolutivité: Seul le RS multi-start et la recherche tabou 2-opt montrent un gap qui s’améliore quand N augmente. Tous les autres algorithmes se dégradent ou stagnent.
Mémoire: Les colonie de fourmis stockent une matrice de phéromones complète (O(N au carré)). La recherche tabou maintient une liste tabou qui grandit. Pour les grandes instances, la mémoire devient un goulot d’étranglement.
Sensibilité aux Paramètres: Le schedule de cooling du recuit simulé affecte dramatiquement les résultats. Implémentation d’un cooling adaptatif basé sur la taille de l’instance.
Si Je Refaisais Cela
- Paralléliser sur les coeurs: La colonie de fourmis et l’algorithme génétique sont trivialement parallèles — j’utiliserais multiprocessing.Pool
- Ajouter branch-and-bound pour la vérité terrain: Les petites instances (N plus petit que 15) ont besoin de solutions optimales pour valider la qualité
- Sélection automatique: Entraîner un modèle simple pour prédire le meilleur algorithme basé sur les caractéristiques (N, densité, ratios)
- Approche hybride: Utiliser le plus proche voisin pour la solution initiale, puis affiner avec Tabou 2-opt
Limitations et Travail Futur
Solveur exact non implémenté: Branch and bound garantirait des solutions optimales pour les petites instances, utile comme vérité de terrain.
Pas de parallélisation: Tous les algorithmes s’exécutent en mono-thread. La colonie de fourmis et l’algorithme génétique parallélisent trivialement sur plusieurs coeurs.
Instances statiques: Les graphes sont générés une fois avant résolution. Les mises à jour dynamiques de graphe modéliseraient mieux la logistique réelle.