Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows

Les auteurs démontrent qu'une méthode exacte simple résout la quasi-totalité des instances classiques du problème du voyageur de commerce avec fenêtres de temps en moins de dix secondes, révélant ainsi que ces benchmarks ne sont plus représentatifs pour évaluer les performances des algorithmes.

L'essentiel

Voici une explication simple et imagée de ce papier de recherche, comme si on en discutait autour d'un café.

🚚 Le Problème du Camionneur (TSPTW)

Imaginez que vous êtes le chef d'orchestre d'une flotte de camions de livraison. Votre mission : faire passer un camion par une liste de clients, chacun ayant une fenêtre de temps précise où il faut livrer (par exemple, entre 9h00 et 10h00).

• Si vous arrivez trop tôt, vous devez attendre (comme un livreur qui s'assoit sur son camion).
• Si vous arrivez trop tard, c'est un échec.
• Le but est de revenir au dépôt le plus vite possible (Makespan) ou de minimiser le temps total de route (Duration).

C'est ce qu'on appelle le Problème du Voyageur de Commerce avec Fenêtres de Temps. C'est un casse-tête mathématique très célèbre.

🧪 Le "Test de Conduite" (Les Benchmarks)

Depuis 40 ans, les chercheurs utilisent un ensemble de "fiches d'examen" classiques (appelées benchmarks) pour tester leurs algorithmes. C'est comme si tous les élèves d'une école de conduite passaient le même examen sur le même circuit de 50 virages.

Si un algorithme résout ces fiches en 10 secondes, on crie au génie ! 🎉

💡 La Révélation de l'Auteur : "C'est un trucage !"

Francisco Soulignac, l'auteur de ce papier, a découvert quelque chose de choquant : ces fiches d'examen classiques sont devenues trop faciles.

Il a créé un algorithme très simple, un peu comme une "astuce de grand-mère" (une recherche intelligente en arrière), qui résout tous les gros problèmes (50 clients ou plus) de ces fiches classiques en moins de 10 secondes.

L'analogie du labyrinthe :
Imaginez que ces fiches d'examen sont des labyrinthes.

• Les chercheurs pensaient que c'était des labyrinthes complexes avec des murs invisibles.
• En réalité, l'auteur a découvert que les murs étaient mal placés. Il y a une "autoroute" cachée qui traverse le labyrinthe.
• Son algorithme simple a juste trouvé cette autoroute.
• Résultat : Il traverse le labyrinthe en courant, pendant que les autres algorithmes complexes (les "super-héros" de l'informatique) tournent en rond en essayant de résoudre des équations compliquées.

🤖 Pourquoi c'est dangereux pour l'Intelligence Artificielle ?

Aujourd'hui, on utilise beaucoup l'Intelligence Artificielle (IA) et le Machine Learning pour apprendre à résoudre ces problèmes. Pour entraîner ces IA, on leur donne des milliers d'exemples de ces mêmes fiches d'examen classiques.

Le danger :
C'est comme entraîner un pilote de Formule 1 uniquement sur un circuit de karting plat et vide.

• L'IA va devenir une championne sur ce circuit précis.
• Mais si on la met sur une vraie route de montagne avec de la pluie (des problèmes réels avec des fenêtres de temps larges et imprévisibles), elle va échouer lamentablement.
• Les chercheurs pensent avoir créé des IA brillantes, mais elles ont juste appris à "tricher" sur un examen trop simple.

🔍 La Preuve par l'Expérience

L'auteur a pris son algorithme simple et l'a confronté à deux types de tests :

1. Les vieux examens (Classiques) : Son algorithme a gagné haut la main, en quelques secondes.
2. Les nouveaux examens "difficiles" (avec des fenêtres de temps très larges) : Là, son algorithme simple s'est effondré. Il n'arrivait plus à trouver de solution, même après des heures.

Cela prouve que les vieux examens ne sont plus représentatifs de la réalité. Ils sont "biaisés".

🏁 La Conclusion en une phrase

Arrêtons de nous fier uniquement aux vieux examens classiques pour juger de la qualité de nos algorithmes ou de nos IA.

Si vous voulez vraiment savoir si votre algorithme est intelligent, ne le faites pas courir sur un circuit vide. Mettez-le dans un vrai trafic, avec des embouteillages et des imprévus (des fenêtres de temps plus larges et plus réalistes). Sinon, nous risquons de célébrer des solutions qui ne fonctionnent que dans un monde imaginaire.

---

En résumé : L'auteur nous dit : "Attention, le test que vous utilisez pour évaluer vos voitures de course est trop facile. N'oubliez pas de tester vos voitures sur la vraie route avant de les vendre !"

Résumé technique

Voici un résumé technique détaillé de l'article « Beware of the Classical Benchmark Instances for the Traveling Salesman Problem with Time Windows » de Francisco J. Soulignac.

1. Problématique : Le Problème du Voyageur de Commerce avec Fenêtres de Temps (TSPTW)

L'article se concentre sur le TSPTW (Traveling Salesman Problem with Time Windows), où un véhicule doit visiter un ensemble de clients dans des fenêtres de temps prédéfinies $[a(v), b(v)]$. Le véhicule peut arriver en avance et attendre, mais ne peut pas arriver en retard.

L'auteur distingue trois variantes de l'objectif à minimiser :

• TSPTW-M (Makespan) : Minimiser le temps de retour au dépôt (temps d'achèvement de la route).
• TSPTW-D (Duration) : Minimiser la durée totale de la route (temps écoulé entre le départ et le retour, incluant les temps d'attente).
• TSPTW-TT (Travel Time) : Minimiser uniquement le temps de déplacement (excluant les temps d'attente).

Le constat critique : La communauté scientifique évalue la majorité des algorithmes (exacts et heuristiques) sur un sous-ensemble spécifique d'instances de référence classiques (compilées par López-Ibáñez et Blum, 2023). L'article soutient que ces instances, en particulier celles avec 50 clients ou plus, ne sont plus représentatives de la difficulté réelle du problème car leur structure permet d'obtenir des résultats exceptionnels avec des méthodes très simples.

2. Méthodologie : Un Solveur Exact Simple et Inversé

L'auteur propose une méthode exacte simple pour le TSPTW-M, basée sur une recherche informée (informed search) en arrière (backward).

• Algorithme 1 (Recherche Best-First en arrière) :

  • L'algorithme explore un arbre de routes partielles en partant du dépôt de fin ($n+1$) vers le dépôt de départ (0).
  • Il utilise une fonction de coût heuristique pour prioriser les nœuds : il maximise la différence entre la borne supérieure du temps ($ub$) et l'heure d'arrivée la plus précoce possible ($\delta_m(R)$). Cela permet de maximiser la flexibilité pour attendre chez les clients précédents.
  • Élagage (Pruning) :
    • Utilisation d'une fonction d'atteignabilité ($U$) précalculée pour éliminer les branches où certains clients ne peuvent plus être visités.
    • Élimination des routes dominées ($ub$-dominated) : si une route partielle $Q$ arrive plus tôt ou part plus tard que $R$ avec le même ensemble de clients visités, $R$ est ignorée.
  • L'algorithme s'arrête dès qu'une route valide avec un makespan inférieur à la borne actuelle est trouvée.

• Algorithme 2 (Résolution du TSPTW-M) :

  • Exécute itérativement l'Algorithme 1 en réduisant la borne supérieure du temps jusqu'à trouver l'optimum.

• Algorithme 3 (Résolution du TSPTW-D) :

  • Utilise une approche de fenêtre glissante sur l'horizon temporel.
  • Il résout le TSPTW-M pour différents temps de départ $t$ en utilisant l'Algorithme 2 comme sous-routine.
  • Il maintient la meilleure durée trouvée ($\Delta(R) = \delta(R, t) - t$).

3. Contributions Clés

1. Démonstration de la facilité des benchmarks classiques : L'auteur montre que son algorithme simple résout toutes les instances classiques du benchmark (avec 50 clients ou plus) en moins de 10 secondes pour le TSPTW-M, et presque toutes pour le TSPTW-D en moins de 30 minutes.
2. Identification d'un biais structurel : Les instances classiques (Lan, Dum, Gen, Ohl, DaS) sont générées en définissant des fenêtres de temps étroites autour d'une route de référence (souvent un chemin du plus proche voisin). Cette structure crée un espace de recherche réduit et biaisé que les méthodes de recherche informée exploitent facilement.
3. Limites de la méthode : L'algorithme échoue sur des instances avec des fenêtres de temps très larges (loose time windows), même avec un petit nombre de clients (ex: benchmarks Rifki/Rif). Cela prouve que la difficulté réside davantage dans la largeur des fenêtres de temps que dans le nombre de clients.
4. Appel à la prudence pour le Machine Learning : De nombreux ensembles de données d'entraînement pour les solveurs basés sur l'apprentissage automatique sont générés avec des procédures similaires à celles des benchmarks classiques, risquant de produire des modèles sur-ajustés (overfitting) à des instances artificiellement faciles.

4. Résultats Expérimentaux

Les expériences ont été menées sur un processeur AMD Ryzen 7 (un seul thread).

• Sur les benchmarks classiques (Asc, Dum, Gen, Lan, Ohl, DaS) :

  • L'algorithme proposé (Algorithme 2) résout 100% des instances avec $n \ge 50$ en quelques secondes.
  • Il résout même 4 instances qui restaient ouvertes dans les études précédentes (Fontaine et al., 2023).
  • Paradoxe : L'algorithme échoue sur certaines petites instances ($n < 50$) si les fenêtres de temps sont larges, alors qu'il est ultra-rapide sur les grandes instances classiques.
  • Comparaison avec l'état de l'art (Ler22, Rud23, Fon24) : L'algorithme de l'auteur est nettement supérieur sur les grandes instances classiques, mais inférieur sur les instances difficiles (large fenêtres).

• Sur le benchmark Rif (instances avec fenêtres larges, $\beta \in \{0, 0.25\}$) :

  • L'algorithme de l'auteur est le pire (échec systématique par épuisement de la mémoire).
  • Les méthodes de l'état de l'art (comme Ler22) restent robustes, confirmant que la difficulté réelle provient de la largeur des fenêtres de temps.

• Sur le TSPTW-D :

  • L'Algorithme 3 résout 14 des 15 instances non résolues précédemment (Lera-Romero et al., 2022) sur les benchmarks classiques.
  • Cela confirme que le TSPTW-D sur ces instances n'est pas significativement plus difficile que le TSPTW-M.

5. Signification et Conclusion

L'article tire une conclusion majeure : les benchmarks classiques ne sont plus suffisants pour évaluer les performances des solveurs TSPTW.

• Biais d'évaluation : Utiliser uniquement ces instances conduit à des conclusions biaisées sur l'efficacité des algorithmes. Une méthode peut sembler excellente sur ces benchmarks tout en étant inefficace sur des problèmes réels ou des instances plus dures (fenêtres larges).
• Recommandations :
  • Il est impératif de compléter les benchmarks classiques par des instances à fenêtres de temps larges (comme celles générées avec le paramètre $\beta$ de Rifki et Solnon, 2025).
  • Les chercheurs en apprentissage automatique doivent éviter de générer des jeux de données d'entraînement basés uniquement sur les procédures de génération des benchmarks classiques, car cela favorise l'overfitting sur des structures triviales.
  • La difficulté du problème TSPTW est davantage liée à la largeur relative des fenêtres de temps qu'au nombre de clients.

En résumé, l'auteur met en garde contre la confiance aveugle dans les résultats obtenus sur les benchmarks historiques, suggérant que la prochaine génération de benchmarks doit se concentrer sur la variabilité de la contrainte de temps (tightness) plutôt que sur la taille du problème.