TSP Resolver
Tournées de livraison sous contraintes : huit heuristiques implémentées, calibrées et comparées de 5 à 3 000 villes.
CESI · Recherche opérationnelle · Projet d'équipe (5 personnes)
- Commande
- ADEME → CesiCDP : réduire les émissions liées aux tournées
- Problème
- TSP-PC-ER, NP-difficile
- Algorithmes
- 8 heuristiques, 4 familles
- Plan d'expérience
- N de 5 à 3 000, 5 instances par taille
Points clés
- NP-difficulté démontrée par réduction : Ham-Cycle ≤p TSP ≤p TSP-PC-ER
- Huit heuristiques implémentées, chacune calibrée par son propre plan d'expérience
- Instances partagées et graine fixée : tous les algorithmes jugés sur les mêmes graphes
- Recommandation par régime de taille, et limites de l'expérience explicitées
Essayez vous-même
Chaque tournée part du dépôt et y revient. Les pointillés sont les routes interdites, les flèches les livraisons à effectuer dans l'ordre. On construit au plus proche voisin, puis on défait les croisements par mouvements 2-opt, en refusant ceux qui casseraient une contrainte, que le compteur « bloquées » comptabilise.
- Dépôt
- Route interdite
- Doit être livrée avant
- Coût = carburant × distance + péage
- Coût
- 0.00
- Gain
- 0.0 %
- Inversions
- 0
- Bloquées
- 0
Sortir de l'optimum local
Le recuit simulé démarre là où une descente 2-opt s'arrête, sur sa propre instance tirée au hasard. Il accepte parfois d'empirer, avec une probabilité qui s'effondre à mesure que la température baisse. Les pointillés marquent son point de départ : tout ce qui passe dessous a été gagné en franchissant une crête.
Trait pâle : coût courant. Trait plein : meilleur trouvé. Pointillés : l'optimum local du 2-opt, d'où part le recuit.
- Dépôt
- Route interdite
- Doit être livrée avant
- Coût = carburant × distance + péage
- Meilleur coût
- 0.00
- Départ (2-opt)
- 0.00
- Dégradations acceptées
- 0
- Température
- 0.0000
Démonstration écrite pour cette page, indépendante du livrable. Elle reprend le modèle du projet (coût = carburant × distance + péage, routes interdites, contraintes de précédence) sur des instances tirées au hasard, mais n'utilise que deux des huit algorithmes étudiés, à des tailles de l'ordre de la trentaine de villes. Le livrable, lui, est un notebook Python disponible sur le dépôt.
Comment ça marche
- 1
Modéliser le terrain
Le réseau devient un graphe complet dont chaque arête porte un coût réel : péage plus prix du carburant au kilomètre. Deux contraintes viennent du métier, certaines routes sont interdites, et certaines villes doivent être livrées avant d'autres.
- 2
Prouver qu'on a le droit de renoncer
Avant d'écrire une heuristique, il faut établir qu'aucun algorithme exact raisonnable n'existe. C'est fait par réduction polynomiale depuis le cycle hamiltonien, en passant par le TSP classique. Sans cette étape, choisir une approximation serait un aveu de paresse plutôt qu'une décision.
- 3
Couvrir quatre familles
Huit algorithmes plutôt qu'un seul, choisis pour couvrir un large spectre du compromis qualité/temps : une heuristique constructive, une recherche locale, quatre métaheuristiques à solution unique, deux méthodes à population.
- 4
Calibrer avant de comparer
Chaque algorithme a d'abord son propre plan d'expérience pour fixer ses paramètres, taux d'évaporation des phéromones, schéma de refroidissement, longueur de la liste tabou. Comparer des méthodes mal réglées ne dit rien sur les méthodes, seulement sur les réglages.
- 5
Mesurer sur les mêmes graphes
Un générateur unique à graine fixée produit toutes les instances. Les huit algorithmes affrontent exactement les mêmes graphes, de 5 à 3 000 sommets, à raison de cinq instances par taille, ce qui élimine le biais d'une méthode chanceuse sur des cas faciles.
Le contexte
Commande fictive de l'ADEME à CesiCDP : optimiser des tournées de livraison pour réduire la consommation de carburant et les émissions associées. L'instance servant de fil rouge est volontairement concrète, une boucherie qui doit livrer ses commandes de Noël depuis un dépôt à Paris vers Rennes, Rouen, Bordeaux, Toulouse et Lyon.
Ce n'est pas le voyageur de commerce des manuels
Le TSP scolaire minimise une distance sur un graphe où tout est permis. Le problème traité ici, noté TSP-PC-ER, ajoute deux couches qui viennent du terrain et changent la nature du travail.
- Un coût réel plutôt qu'une distance : péage + prix du carburant au kilomètre
- Arêtes interdites (Edge Restrictions) : une route en travaux ne peut pas être empruntée
- Contraintes de précédence (Precedence Constraints) : certaines villes doivent être livrées avant d'autres
- Conséquence pratique : une solution mathématiquement optimale mais qui emprunte une route fermée ne vaut rien
Établir la difficulté avant de choisir l'approche
L'appartenance à NP se vérifie sur un certificat, une tournée ordonnée, en temps linéaire : chaque sommet apparaît une fois, aucune arête empruntée n'est interdite, le coût tient sous le seuil, les précédences sont respectées. La difficulté se démontre ensuite par réduction depuis le TSP classique, en posant simplement aucune précédence et aucune route bloquée : le TSP est un cas particulier du nôtre.
- Le nombre de tournées distinctes vaut (n−1)!/2
- À 15 villes : plus de 4 × 10¹⁰ parcours
- À 20 villes : plus de 6 × 10¹⁶
- Les contraintes réduisent ce nombre, mais diviser par une constante ne change pas l'ordre de grandeur
Huit algorithmes, quatre familles
Le choix n'est pas de trouver « le bon » algorithme mais de couvrir le compromis qualité/temps assez largement pour que la comparaison ait du sens.
- Constructif, Plus Proche Voisin, en variante multi-start
- Recherche locale, Hill Climbing multi-start
- Solution unique, Recuit simulé, recuit simulé multi-start, recherche tabou, recherche tabou 2-opt
- Population, algorithme génétique, colonie de fourmis
Ce que les mesures ont montré
Aucun algorithme ne gagne partout, et c'est le résultat intéressant : la bonne réponse dépend de la taille de l'instance et du temps qu'on accepte d'y consacrer.
- Jusqu'à N ≈ 300 et quand la qualité prime : la recherche tabou 2-opt domine
- Au-delà de N ≈ 300 : le recuit simulé passe devant, son temps d'exécution croissant quasi linéairement
- À toute taille, comme référence rapide : le Plus Proche Voisin multi-start, très bon rapport qualité/temps
- Génétique et colonie de fourmis décrochent au-delà de N ≈ 50 avec les paramètres retenus
- Le recuit multi-start n'améliore pas le recuit simple : le budget d'itérations réparti entre les relances devient insuffisant pour que chacune converge
Ce que l'expérience ne dit pas
C'est la partie du livrable dont je suis le plus satisfait. Les écarts mesurés sont exprimés par rapport à une borne inférieure volontairement simple, la demi-somme des minima sortants, qui sous-estime largement le coût optimal. Les pourcentages d'écart paraissent donc énormes et ne reflètent pas la qualité réelle des solutions : ils servent à classer les algorithmes entre eux, pas à mesurer une distance à l'optimum.
- Une borne plus serrée (Held-Karp, relaxation linéaire) donnerait une image bien plus juste
- Cinq graines par taille : trop peu pour conclure sous N = 30, où les écarts restent dans le bruit
- Paramètres calibrés sur N ≤ 30 : leur transfert aux grandes instances est approximatif, et un pic d'écart vers N ≈ 50 le trahit
- Ce pic n'est pas une propriété des algorithmes mais un artefact de notre calibration, le distinguer était l'enjeu de l'analyse
Ce que j'en retire
- Prouver la difficulté d'un problème avant de choisir comment l'attaquer, plutôt que l'inverse
- Calibrer chaque méthode avant de la comparer : sinon on compare des réglages, pas des méthodes
- Une mesure ne vaut que ce que vaut sa référence, ici, une borne lâche rendait les écarts spectaculaires et peu informatifs
- Savoir distinguer un résultat d'un artefact de protocole
- Le même réflexe me sert chez Thales : arbitrer précision contre latence sur des mesures dont je connais les limites