Learning to Solve Orienteering Problem with Time Windows and Variable Profits

Cet article propose DeCoST, une méthode d'apprentissage en deux étapes qui découple efficacement les variables discrètes et continues pour résoudre le problème d'orientation avec fenêtres de temps et profits variables, surpassant les solveurs actuels en qualité de solution et en rapidité d'exécution.

L'essentiel

🚀 Le Dilemme du Camionneur de Glaces : Comment faire le meilleur choix ?

Imaginez que vous êtes le responsable d'une flotte de camions de glaces dans une grande ville. Votre objectif est simple : gagner le plus d'argent possible en vendant des glaces à différents endroits.

Mais la réalité est compliquée, comme le décrit ce papier de recherche (publié à la conférence ICLR 2026) :

1. Le temps est limité : Vous avez un budget de temps fixe (par exemple, 4 heures).
2. Les clients ont des horaires : Certains clients ne sont disponibles que entre 14h et 15h (fenêtres de temps). Si vous arrivez à 15h01, vous ne pouvez pas vendre.
3. Le profit dépend du temps passé : Plus vous restez longtemps avec un client, plus vous vendez de glaces (et plus vous gagnez). Mais si vous restez trop longtemps, vous n'aurez pas le temps d'aller voir les autres clients.

C'est ce qu'on appelle le Problème d'Orientation avec Fenêtres de Temps et Profits Variables. C'est un casse-tête mathématique énorme où il faut décider :

• Quels clients visiter ? (Décision discrète : Oui ou Non).
• Combien de temps rester chez chacun ? (Décision continue : 2 minutes ? 10 minutes ?).

Le problème, c'est que ces deux décisions sont liées comme les deux faces d'une pièce : si vous décidez de rester longtemps chez le client A, vous n'aurez peut-être plus le temps d'aller chez le client B, qui aurait pu être très rentable.

🧠 La Solution : DeCoST (Le Chef d'Orchestre en Deux Temps)

Les méthodes actuelles sont soit trop lentes (elles calculent tout parfaitement mais prennent des heures), soit trop rapides mais imparfaites (elles font des erreurs de calcul).

Les auteurs proposent une nouvelle méthode appelée DeCoST. Imaginez que c'est un chef d'orchestre qui dirige une équipe en deux étapes distinctes mais coordonnées :

Étape 1 : Le Brouillon Rapide (Le "Découplage")

Au lieu d'essayer de tout calculer d'un coup (ce qui est impossible à faire rapidement), DeCoST sépare le problème en deux :

• Le Routage (Le Plan de Route) : Une intelligence artificielle (un réseau de neurones) regarde la carte et dit : "Ok, on va aller chez A, puis B, puis C".
• L'Estimation du Temps (Le Service) : En même temps, elle devine à peu près combien de temps on va passer chez chacun.

C'est comme si vous dessiniez un itinéraire rapide sur un bout de papier en disant : "Je vais passer 5 min ici, 10 min là". Ce n'est pas parfait, mais c'est un bon point de départ.

Étape 2 : Le Perfectionnement Mathématique (L'Optimisation)

Une fois le trajet (A -> B -> C) figé, le problème devient beaucoup plus simple. Il ne reste plus qu'à ajuster les temps de service pour maximiser les ventes.

• Ici, DeCoST utilise un outil mathématique très puissant (de la programmation linéaire) qui trouve la solution parfaite pour ce trajet précis en quelques millisecondes.
• C'est comme si, une fois la route tracée, un super-calculateur ajustait exactement la durée de chaque arrêt pour ne pas perdre une seconde de temps.

Le résultat ? On obtient un trajet intelligent et des temps d'arrêt parfaitement calibrés, le tout très rapidement.

🎯 L'Innovation Clé : Le "Radar de Profit" (pTAR)

Comment apprendre à l'IA à faire un bon brouillon (Étape 1) si elle ne sait pas encore faire le calcul parfait (Étape 2) ?

Les chercheurs ont inventé un indicateur spécial appelé pTAR (Profit-Weighted Time Allocation Ratio).

• L'analogie : Imaginez que vous apprenez à un enfant à faire des courses. Au début, il ne sait pas combien de temps passer dans chaque magasin.
• Au lieu de lui dire "Tu as fait une erreur", vous lui donnez un radar de profit : "Regarde, tu as gagné beaucoup d'argent pour peu de temps de déplacement ici, mais tu as perdu du temps à aller chercher quelque chose de peu cher là-bas".
• Ce radar permet à l'IA d'apprendre, par essai et erreur, à équilibrer le temps de trajet et le temps de service dès le début, sans avoir besoin de solutions parfaites pour s'entraîner.

🏆 Pourquoi c'est génial ?

1. Vitesse Éclair : Sur des problèmes avec 500 clients, DeCoST est 20 à 45 fois plus rapide que les meilleurs algorithmes actuels (comme les méthodes de recherche locale), tout en trouvant de meilleures solutions.
2. Qualité Supérieure : Il gagne plus d'argent (ou de points) que les méthodes traditionnelles.
3. Polyvalence : Cette méthode fonctionne bien sur des petits problèmes (50 clients) comme sur des gros (500 clients).

En Résumé

Ce papier propose une nouvelle façon de résoudre des problèmes de logistique complexes. Au lieu de chercher à tout faire parfaitement en même temps (ce qui est trop lent), DeCoST :

1. Trace une route intelligente rapidement.
2. Ajuste mathématiquement les temps d'arrêt pour le maximum de profit.
3. Apprend de ses erreurs grâce à un "radar de profit" pour devenir de plus en plus fort.

C'est comme passer d'un conducteur qui regarde sa montre et panique, à un pilote de course qui a une stratégie parfaite et un ordinateur de bord qui ajuste tout en temps réel. 🏎️💨

Résumé technique

Titre : DeCoST : Apprentissage pour résoudre le problème d'orientation avec fenêtres de temps et profits variables

1. Le Problème : OPTWVP

L'article s'attaque au Problème d'Orientation avec Fenêtres de Temps et Profits Variables (OPTWVP). C'est une variante complexe du problème de routage de véhicules (VRP) et du problème d'orientation (OP), caractérisée par deux défis majeurs :

• Profits Variables : Contrairement aux problèmes classiques où le profit d'un nœud est fixe, ici le profit dépend linéairement du temps de service alloué ($f(d_i, p_i) = p_i \cdot d_i$). Plus on sert longtemps un nœud, plus le profit est élevé, mais cela consomme le budget de temps global.
• Fenêtres de Temps : Chaque nœud n'est accessible que dans un intervalle de temps spécifique $[s_i^-, s_i^+]$.
• Couplage Discret-Continu : Le problème nécessite de décider simultanément :
  1. Quels nœuds visiter et dans quel ordre ? (Décision discrète : routage).
  2. Combien de temps servir à chaque nœud ? (Décision continue : allocation de service).
     Ces deux composantes sont fortement couplées : le choix du chemin affecte les fenêtres de temps disponibles pour le service, et la durée du service affecte la faisabilité du chemin restant. Les méthodes existantes (heuristiques ou NCO) peinent à optimiser ce couplage efficacement.

2. Méthodologie : Le Framework DeCoST

Les auteurs proposent DeCoST (DEcoupled discrete-Continuous optimization with Service-time-guided Trajectory), un framework d'optimisation en deux étapes basé sur l'apprentissage par renforcement (RL) et la programmation linéaire.

A. Architecture Globale (Deux Étages)
L'approche vise à découpler les variables discrètes (chemin) et continues (temps de service) tout en maintenant une coordination apprenable entre elles.

• Étape 1 : Décodage Parallèle (Construction de la trajectoire)

  • Un décodeur parallèle génère simultanément le chemin $\tau$ et une estimation initiale des temps de service $\hat{d}$.
  • Encodage Spatial : Utilisation de biais d'attention basés sur les distances entre les nœuds (inspiré de Graphormer) pour mieux comprendre la structure du graphe.
  • Masquage de Faisabilité : Un masque dynamique exclut les nœuds qui violeraient les contraintes de temps (fenêtres de temps ou dépassement du budget total), garantissant que la trajectoire générée est réalisable dès le départ.
  • Décodeur de Temps de Service (STD) : Prédit le ratio de temps de service initial pour chaque nœud visité.

• Étape 2 : Optimisation des Temps de Service (STO)

  • Une fois le chemin discret $\tau$ fixé par l'étape 1, le problème d'allocation des temps de service devient un problème d'optimisation convexe (Programmation Linéaire - LP).
  • Un algorithme spécifique, STO (Service Time Optimization), résout ce sous-problème de manière parallèle et efficace pour obtenir les temps de service optimaux $d^*$ et le profit maximal associé.
  • Théorème de Optimalité : Les auteurs prouvent mathématiquement (Théorème 4.1) que l'algorithme STO garantit une solution globalement optimale pour l'allocation des temps de service étant donné un chemin fixe.

B. Mécanisme d'Apprentissage et Supervision
Pour entraîner le modèle, les auteurs utilisent une perte REINFORCE combinée à une supervision spécifique :

• Indice de Supervision Répulsif (pTAR) : Ils introduisent le Profit-weighted Time Allocation Ratio (pTAR), défini comme le rapport entre le profit total pondéré et le temps de trajet.
• Fonction de Perte : Une perte de supervision ($L_{pTAR}$) est ajoutée pour encourager le modèle à prédire des temps de service initiaux ($\hat{d}$) qui se rapprochent de l'optimum global ($d^*$) trouvé à l'étape 2. Cela évite la convergence prématurée vers des optima locaux conditionnels et permet au modèle d'apprendre une estimation structurelle à long terme.

3. Contributions Clés

1. Framework DeCoST : Première approche basée sur l'apprentissage capable de décomposer et de coordonner efficacement les décisions de routage discrètes et d'allocation de service continues pour l'OPTWVP.
2. Optimisation Globale à Deux Étages : Combinaison d'un solveur constructif neuronal (pour le chemin) et d'un solveur LP exact (STO) pour les temps de service, prouvant l'optimalité de la seconde étape.
3. Mécanisme de Feedback (pTAR) : Introduction d'un indicateur de supervision qui guide l'apprentissage du décodeur de temps de service vers des stratégies globalement efficaces, améliorant la qualité de la solution finale.
4. Performance et Efficacité : Démonstration que la méthode surpasse les algorithmes méta-heuristiques de pointe et les méthodes NCO existantes en termes de qualité de solution et de vitesse d'inférence.

4. Résultats Expérimentaux

Les expériences ont été menées sur des instances OPTWVP de différentes tailles ($n=50, 100, 500$) et fenêtres de temps variées, comparées à :

• Gurobi (Solveur exact B&C).
• ILS (Recherche locale incrémentale, méta-heuristique SOTA).
• POMO et GFACS (Méthodes NCO de référence).

Résultats Principaux :

• Qualité de Solution : DeCoST obtient des écarts d'optimalité (Gap) très faibles par rapport à Gurobi (ex: 1.06% pour $n=50$ vs 4.34% pour ILS). Il surpasse systématiquement les autres méthodes NCO et heuristiques.
• Efficacité Computationnelle :
  • DeCoST est 20 à 45 fois plus rapide que l'algorithme ILS pour des instances de taille moyenne.
  • Sur des instances de 500 nœuds, DeCoST trouve une solution de haute qualité en 1,3 secondes, contre 8,8 secondes pour ILS.
  • Accélération d'inférence jusqu'à 6,6x par rapport aux méthodes de construction classiques.
• Robustesse : Les analyses de sensibilité et les ablations montrent que chaque composant (Encodage Spatial, STO, perte pTAR) est essentiel, le module STO apportant le gain de performance le plus significatif.
• Généralisation : La méthode fonctionne également bien sur le jeu de données standard Solomon100 et s'étend au problème d'équipe (Team OPTWVP).

5. Signification et Impact

Ce travail est significatif car il comble un vide important dans l'optimisation combinatoire neuronale (NCO) : la gestion efficace des problèmes hybrides discret-continu.

• Praticité : En découpant le problème complexe en une étape de routage (apprise) et une étape d'allocation de ressources (résolue exactement), DeCoST offre une solution à la fois rapide et de haute qualité, adaptée aux applications temps réel comme la logistique, la planification robotique et la maintenance industrielle.
• Innovation Algorithmique : La preuve d'optimalité de l'étape 2 et l'utilisation d'un signal de supervision "répulsif" (pTAR) pour guider l'apprentissage du premier étage constituent des avancées méthodologiques pour les problèmes de routage avec contraintes complexes.

En résumé, DeCoST représente un état de l'art pour les problèmes de routage avec profits variables et fenêtres de temps, offrant un compromis supérieur entre la qualité de la solution et le temps de calcul par rapport aux méthodes existantes.