💻 computer science

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

Cet article introduit le problème du voleur itinérant avec contraintes de fenêtres de temps, propose de nouvelles instances de référence et un algorithme heuristique qui surpassent les approches existantes sur une large gamme de benchmarks.

Auteurs originaux : Helen Yuliana Angmalisang, Frank Neumann

Publié 2026-04-09

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Helen Yuliana Angmalisang, Frank Neumann

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🎒 Le Problème du Voleur Voyageur (avec une contrainte de temps)

Imaginez un voleur très malin, mais aussi très pressé. Il a deux missions à accomplir en même temps :

Le Touriste : Il doit visiter plusieurs villes pour faire le tour du monde (comme le célèbre problème du "Voyageur de Commerce").
Le Voleur : Dans chaque ville, il peut voler des objets pour les mettre dans son sac à dos. Chaque objet a une valeur (profit) et un poids.

Le piège ? Plus son sac est lourd, plus il marche lentement. S'il vole trop d'objets lourds, il mettra plus de temps à aller d'une ville à l'autre, ce qui lui coûte de l'argent (car il doit louer son sac à dos à l'heure).

La nouvelle contrainte (Le "Time Window") :
Dans ce papier, les chercheurs ajoutent une règle de plus : les villes ne sont pas toujours ouvertes.

Imaginez que vous devez livrer un colis à une maison, mais le propriétaire n'est là que entre 14h00 et 14h30.
Si le voleur arrive à 13h00, il doit attendre (ce qui fait perdre du temps).
S'il arrive à 15h00, c'est trop tard, il ne peut rien voler et il a raté son coup.

C'est ce qu'on appelle le Problème du Voleur Voyageur avec Fenêtres de Temps. C'est un casse-tête énorme : comment choisir quoi voler et dans quel ordre visiter les villes pour maximiser le gain sans jamais arriver trop tard ?

🕵️‍♂️ La Solution : Le "Double Détective" (DSEA)

Les chercheurs ont constaté que les anciennes méthodes de résolution (qui fonctionnaient bien sans les contraintes de temps) échouaient lamentablement ici. Elles trouvaient des itinéraires impossibles (arriver à 15h00 quand la porte est fermée à 14h30).

Pour résoudre ce casse-tête, ils ont créé un nouvel algorithme qu'ils appellent DSEA (Dual Search Evolutionary Algorithm).

L'analogie du "Double Détective" :
Imaginez que vous avez deux détectives qui travaillent ensemble pour trouver le meilleur plan :

Le Détective "Carte" (L'itinéraire) : Il se concentre uniquement sur l'ordre des villes. Il essaie de changer l'ordre de visite pour éviter les retards.
Le Détective "Sac" (Le chargement) : Il se concentre sur ce qu'il faut mettre dans le sac. Il décide quels objets sont assez légers pour ne pas ralentir le voleur, mais assez précieux pour valoir le coup.

La magie de l'algorithme :
Au lieu de faire les choses une par une, ils font les deux en même temps, en se corrigeant mutuellement.

Si le détective "Carte" change l'ordre des villes, le détective "Sac" réajuste immédiatement ce qu'il faut voler.
Ils utilisent une astuce intelligente au début : au lieu de chercher le chemin le plus court (ce qui est souvent impossible à cause des horaires), ils cherchent d'abord un chemin possible qui respecte les horaires, même s'il n'est pas le plus court. C'est comme choisir un trajet un peu plus long pour éviter les embouteillages, plutôt que de prendre le chemin rapide et de se faire bloquer.

🧪 Les Résultats : Qui gagne ?

Les chercheurs ont testé leur nouveau détective (DSEA) contre les anciennes méthodes (comme S4, S5, LKH-3) sur des centaines de scénarios différents (de petites villes à de très grandes métropoles, avec des horaires très stricts ou plus souples).

Le verdict est clair :

Les anciennes méthodes : Elles étaient souvent perdues. Elles trouvaient des itinéraires théoriquement rapides, mais qui échouaient parce que le voleur arrivait trop tard ou trop tôt. Elles ne trouvaient presque jamais de solution réalisable dans les cas difficiles.
Le nouveau DSEA : Il a gagné presque partout. Il est capable de trouver des solutions qui respectent les horaires et qui rapportent le plus d'argent.

Une petite surprise :
Ils ont aussi testé différentes façons de "réparer" le sac à dos quand il y avait un problème. Ils ont découvert que, paradoxalement, ne pas trop réparer le sac était parfois la meilleure stratégie. Mieux vaut laisser le détective "Carte" explorer de nouveaux itinéraires que de passer trop de temps à ajuster le contenu du sac à chaque fois.

🌍 Pourquoi est-ce important pour nous ?

Ce n'est pas juste un jeu pour voleurs imaginaires ! Ce problème ressemble énormément à des situations réelles :

Les ambulances : Elles doivent aller d'un patient à l'autre (itinéraire) tout en transportant du matériel médical lourd (sac à dos), et elles doivent arriver dans des créneaux horaires précis pour les urgences.
La livraison de repas : Le livreur doit optimiser son trajet et ce qu'il porte, tout en respectant les heures de livraison promises aux clients.

En résumé :
Ce papier nous dit que pour résoudre des problèmes complexes où tout est lié (temps, poids, itinéraire), il ne faut pas traiter les pièces séparément. Il faut une approche globale, comme notre "Double Détective", qui ajuste le trajet et le chargement en même temps pour trouver la solution parfaite.

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

L'article aborde une extension du Problème du Voleur Voyageur (TTP - Traveling Thief Problem), qui combine le Problème du Voyageur de Commerce (TSP) et le Problème du Sac à Dos (KP). Dans le TTP classique, un voleur doit visiter un ensemble de villes pour voler des objets, maximisant le profit net (profit des objets moins le coût de location du sac à dos basé sur la durée du trajet). La vitesse de déplacement dépend du poids total transporté.

L'innovation principale de cet article est l'introduction de contraintes de fenêtres de temps (Time Windows) :

Chaque ville $i$ possède une fenêtre de temps $[L_i, U_i]$ .
Le voleur ne peut visiter la ville qu'entre l'heure d'arrivée minimale $L_i$ et maximale $U_i$ .
Si le voleur arrive avant $L_i$ , il doit attendre (ce qui augmente la durée totale et le coût de location).
Si le voleur arrive après $U_i$ , la solution est infeasible (non admissible).

Complexité accrue :
La combinaison de la dépendance entre la vitesse et le poids (TTP) et des contraintes temporelles strictes (TTPTW) réduit drastiquement l'espace de recherche admissible. Une décision de vol d'objet peut entraîner un retard, rendant impossible la visite ultérieure d'une ville, transformant ainsi un problème d'optimisation en un problème de satisfaction de contraintes extrêmement difficile.

2. Méthodologie et Approche Proposée

Les auteurs constatent que les algorithmes existants pour le TTP (S4, S5, C5) et le TSP avec fenêtres de temps (LKH-3, VSR-LKH-3) échouent à trouver des solutions admissibles sur la plupart des instances de TTPTW. Pour répondre à ce défi, ils proposent une nouvelle approche : l'Algorithme Évolutionnaire à Double Recherche (DSEA - Dual Search Evolutionary Algorithm).

A. Initialisation de l'itinéraire (Tour Initialization)

Au lieu d'utiliser l'heuristique classique Chained Lin-Kernighan (CLK) qui cherche le chemin le plus court (souvent infeasible avec des fenêtres de temps), les auteurs proposent un algorithme d'initialisation basé sur une méthode du voisinage le plus proche avec mémoire et système de scoring :

Le score d'une ville dépend du temps d'arrivée prévu.
Si l'arrivée est dans la fenêtre, le score est le temps de trajet.
Si l'arrivée est en retard, une pénalité forte est appliquée.
Si l'arrivée est trop tôt, la ville est moins prioritaire.
L'algorithme génère plusieurs itinéraires candidats et sélectionne celui avec la violation de contraintes la plus faible.

B. L'Algorithme DSEA

DSEA est un algorithme évolutionnaire qui optimise simultanément l'itinéraire ( $\Pi$ ) et le plan de chargement ( $P$ ). Il utilise deux opérateurs de recherche complémentaires :

Opérateur 2-opt (Topo) : Inverse des sous-tours pour améliorer la structure du trajet.
Opérateur d'Insertion (Rain) : Insère une ville à un nouvel emplacement aléatoire.

Stratégie de réparation : L'algorithme intègre des mécanismes pour réparer les plans de chargement (Repack) ou les intégrer directement à l'optimiseur (ITP/IIP).
Variants : Trois variantes sont testées :
- DSEA1 : Sans réparation de plan de chargement (recherche pure sur les itinéraires).
- DSEA2 : Avec réparation "Repack" (suppression d'objets lourds peu rentables).
- DSEA3 : Intégration de la réparation et de l'optimiseur (mise à jour dynamique du plan de chargement).

C. Gestion des Contraintes

Les auteurs utilisent une technique de séparation objectif-contrainte (Constraint-Objective Value Separation) plutôt qu'une méthode de pénalité. Une solution est jugée meilleure si elle a une violation de contraintes plus faible. Si les violations sont égales, celle avec le meilleur objectif (profit) est choisie.

3. Contributions Clés

Définition du problème TTPTW : Introduction formelle du TTP avec fenêtres de temps, un problème pertinent pour des applications réelles comme les services d'urgence, la logistique médicale ou la livraison de repas.
Nouvelles Instances de Benchmark : Création d'un ensemble de benchmarks basé sur les instances TTP existantes (Polyakovskiy et al.), enrichies de fenêtres de temps avec différents niveaux de "serrage" (paramètre $l$ : 100, 1000, -100, -1000) et deux types de génération (Type A : basé sur le TSP optimal, Type B : fenêtres aléatoires).
Algorithme DSEA : Proposition d'un nouvel algorithme hybride combinant initialisation intelligente, opérateurs de recherche multiples et stratégies de réparation.
Évaluation comparative : Analyse approfondie de l'adaptation des algorithmes d'état de l'art (S4, S5, C5, LKH-3, VSR-LKH-3) au nouveau problème.

4. Résultats Expérimentaux

Les expériences ont été menées sur 30 exécutions indépendantes avec une limite de 1 000 000 d'évaluations de fonctions (FE).

Performance des algorithmes existants : Les algorithmes S4, S5, C5, LKH-3 et VSR-LKH-3 (même adaptés) ont un taux de faisabilité (FR) très faible (souvent 0% ou <50%) sur les instances plus grandes ou avec des fenêtres de temps serrées. Ils échouent à trouver des solutions admissibles.
Impact de l'initialisation : L'ajout de l'algorithme d'initialisation proposé aux algorithmes S4, S5 et C5 améliore considérablement leur taux de faisabilité (atteignant 100% sur de nombreuses instances), prouvant que la qualité de l'itinéraire initial est critique. Cependant, leur performance en termes de profit reste inférieure à DSEA.
Performance de DSEA :
- DSEA1 (sans réparation de plan de chargement) s'avère être la meilleure variante dans la majorité des cas, obtenant les meilleurs profits moyens et un taux de faisabilité de 100% sur presque toutes les instances.
- L'absence de mécanisme de réparation permet à DSEA1 d'explorer plus d'itinéraires, ce qui est crucial étant donné la complexité de l'espace de recherche.
- DSEA3 (avec intégration réparation/optimiseur) performe mieux que les autres sur certaines instances spécifiques (petites instances fortement corrélées), mais DSEA1 reste supérieur globalement.
- DSEA2 (Repack) montre des performances inférieures, probablement dû au coût computationnel élevé de la réparation.
Comparaison finale : DSEA surpasse systématiquement toutes les autres approches (S4, S5, C5, LKH-3, VSR-LKH-3) en termes de qualité de solution et de capacité à trouver des solutions admissibles.

5. Signification et Conclusion

Cet article démontre que l'ajout de contraintes de fenêtres de temps au TTP transforme radicalement la nature du problème, rendant les approches classiques inefficaces.

Importance pratique : Le problème modélise des scénarios réels où le temps est une ressource critique et limitée.
Apport théorique : La démonstration que l'initialisation de l'itinéraire est plus critique que l'optimisation itérative du plan de chargement dans ce contexte contraint.
Ressource future : La publication de benchmarks standardisés pour le TTPTW permet à la communauté de recherche de comparer et d'améliorer les algorithmes pour ce problème complexe.

En résumé, les auteurs proposent une solution robuste (DSEA) capable de naviguer dans un espace de recherche restreint et complexe, surpassant les méthodes de l'état de l'art en garantissant la faisabilité et en optimisant le profit.