RL et Mathematical Programming : Optimisation des tâches d'entreprise

Optimisation : L'apprentissage par renforcement et la programmation mathématique se rencontrent

Pendant des décennies, les méthodes classiques de programmation mathématique ont constitué la pierre angulaire de l'automatisation et de l'optimisation des processus métier tels que le routage, la planification de la production et la logistique. Cependant, avec les avancées de l'intelligence artificielle, notamment en apprentissage par renforcement (RL), une question cruciale se pose : ces nouveaux paradigmes peuvent-ils surpasser ou du moins compléter les approches traditionnelles pour résoudre des problèmes d'optimisation complexes ? Cet article explore le potentiel du RL en optimisation combinatoire, en analysant à la fois les stratégies intégrées et les solutions autonomes, et se penche sur un exemple logistique spécifique.

Le RL en optimisation combinatoire : approches hybrides et autonomes

Les progrès en apprentissage par renforcement sont largement attribués aux tests itératifs, où chaque tâche devient un terrain d'expérimentation pour l'affinement du modèle. Cette approche par essais et erreurs a permis au RL de s'adapter aux problèmes d'optimisation combinatoire (OC), caractérisés par un vaste espace de solutions possibles. En OC, le RL est utilisé de deux manières principales : comme composant pour améliorer les algorithmes existants et comme technologie autonome pour trouver des solutions. Cela ouvre de nouveaux horizons pour surmonter les complexités computationnelles et améliorer l'adaptabilité des systèmes.

Intégrer le RL aux méthodes d'optimisation traditionnelles

L'intégration du RL avec les méthodes d'optimisation classiques permet de tirer parti des forces de chaque approche. Le RL apporte l'adaptabilité et la capacité d'apprendre de l'expérience, tandis que les algorithmes classiques offrent une convergence garantie et des heuristiques éprouvées. Cette approche hybride aborde efficacement les problèmes où les méthodes purement classiques rencontrent une croissance exponentielle de la complexité.

Les principales stratégies d'intégration comprennent :

Le RL comme générateur de solutions initiales : Un agent de RL apprend à créer des solutions initiales de haute qualité, qui sont ensuite affinées par des méthodes exactes, telles que la méthode de séparation et évaluation (branch and bound) ou la programmation linéaire. Cela réduit considérablement le temps de recherche d'une solution optimale, par exemple, dans le problème du voyageur de commerce (TSP), où le RL peut rapidement suggérer un itinéraire quasi-optimal.
Algorithmes hybrides avec recherche locale : Le RL identifie les directions prometteuses d'amélioration, tandis que les heuristiques locales (par exemple, 2-opt, 3-opt) effectuent des modifications spécifiques. L'agent apprend à sélectionner les opérations les plus efficaces dans l'état actuel, réduisant ainsi la charge computationnelle et accélérant la convergence.
Le RL pour l'adaptation des paramètres métaheuristiques : Les algorithmes métaheuristiques (par exemple, les algorithmes génétiques, le recuit simulé) ont de nombreux paramètres ajustables. Un agent de RL peut ajuster dynamiquement ces paramètres pendant le processus de résolution, optimisant, par exemple, les probabilités de croisement et de mutation dans un algorithme génétique en fonction des progrès actuels.
Le RL hiérarchique pour la décomposition de problèmes : Les problèmes complexes sont décomposés en sous-problèmes, chacun résolu par un agent de RL individuel ou un algorithme classique. Par exemple, au niveau supérieur, le RL pourrait regrouper des villes dans un TSP, tandis qu'au niveau inférieur, des méthodes exactes optimisent les itinéraires au sein de chaque groupe.
Le RL dans la séparation et évaluation (Branch and Bound) : Dans cette méthode, le RL peut être utilisé pour sélectionner la prochaine branche à explorer, évaluer le potentiel des nœuds ou élaguer l'espace de recherche en prédisant des bornes, augmentant ainsi l'efficacité de l'algorithme.

Optimisation Combinatoire Neuronale (OCN) : implémentations modernes et limites

L'optimisation combinatoire neuronale (OCN) représente un domaine qui fusionne les réseaux neuronaux avec les exigences de l'optimisation combinatoire. Les OCN sont particulièrement efficaces pour les problèmes dynamiques nécessitant une génération rapide de solutions et dans les scénarios où les méthodes traditionnelles s'avèrent trop lentes. Cependant, les capacités actuelles des OCN sont encore limitées, et elles ne constituent pas un solveur universel pour tous les problèmes. Leur application réussie est souvent associée à des contextes académiques ou à des problèmes à petite échelle avec des contraintes spécifiques.

Exemples de problèmes qui peuvent théoriquement être résolus à l'aide de l'OCN (avec des réserves concernant la taille et les conditions) :

Problème du voyageur de commerce (TSP) : Trouver l'itinéraire le plus court qui visite un ensemble donné de villes exactement une fois. Les OCN peuvent utiliser des réseaux de pointeurs (Pointer Networks) ou des réseaux neuronaux graphiques (GNN) pour générer des permutations.
Problème de tournées de véhicules (VRP) : Optimiser les itinéraires pour une flotte de véhicules, en tenant compte des contraintes de capacité ou de fenêtres de temps.
Problème du sac à dos : Sélectionner des articles avec une valeur maximale sous des contraintes de poids/volume.
Problème de couverture d'ensemble : Choisir un ensemble minimal d'ensembles qui couvrent tous les éléments.
Ordonnancement d'atelier (Job-Shop Scheduling) : Allouer des opérations à des machines pour minimiser le temps total d'achèvement.
Coloration de graphe : Minimiser le nombre de couleurs pour les sommets adjacents, utilisé dans la planification.
Problème de localisation d'installations : Placement optimal d'entrepôts ou de stations de recharge.
Optimisation de la chaîne d'approvisionnement : Planifier l'approvisionnement, la production et la livraison en tenant compte des incertitudes.
Problème d'affectation : Correspondance optimale des agents aux tâches, comme les taxis aux passagers.
Problème SAT : Déterminer la satisfiabilité des formules booléennes.

Malgré ces exemples, un écart significatif existe entre les capacités théoriques du RL dans les formulations classiques et leur application pratique. Combler cet écart nécessite davantage de recherche et de développement.

Exemple pratique : Optimisation des arrêts de ravitaillement dans le transport de marchandises avec le RL

Considérons un problème pratique du domaine de la logistique : l'optimisation des coûts de carburant dans le transport de marchandises. Les dépenses de carburant constituent une part importante des coûts opérationnels, atteignant souvent jusqu'à un tiers des dépenses totales. La planification stratégique des arrêts de ravitaillement le long d'un itinéraire peut réduire considérablement ces coûts, compte tenu des variations de prix dans les différentes stations-service. Souvent, ce processus est délégué aux chauffeurs qui ne sont pas toujours axés sur la minimisation des coûts, ce qui crée un potentiel d'optimisation significatif.

Tâche métier : Déterminer les emplacements optimaux des arrêts de ravitaillement (stations-service) et les volumes de carburant le long d'un itinéraire, en minimisant les coûts totaux tout en respectant plusieurs contraintes :

Niveau de carburant minimum : À tout moment sur l'itinéraire, le niveau de carburant dans le réservoir ne doit pas descendre en dessous d'un seuil spécifié.
Capacité du réservoir : Le volume de carburant ne doit pas dépasser la capacité maximale du réservoir.
Niveau de carburant final : À la fin de l'itinéraire, le réservoir doit contenir au moins une quantité de carburant seuil.
Volume de ravitaillement minimum : Le ravitaillement doit être économiquement viable, ce qui signifie que le volume doit dépasser un minimum défini.

Pour l'application du RL, l'espace de solution continu du volume de ravitaillement est discrétisé. Par exemple, cinq options de ravitaillement sont considérées : 0 %, 25 %, 50 %, 75 % et 100 % de l'espace disponible dans le réservoir. Cela simplifie la gestion des états en RL sans déformer significativement les résultats à des fins de recherche.

Formalisation du problème en programmation non linéaire

Le problème de l'optimisation de la sélection des stations-service et des volumes de ravitaillement peut être formalisé comme un problème de programmation non linéaire. Les composants suivants sont introduits :

Indices :

i — indices des stations-service.

Constantes :

c_i — volume de consommation de carburant entre les stations-service i-1 et i.
p_i — coût du ravitaillement à la station-service i.
v_min — volume minimum de ravitaillement à une station-service.
s_0, s_n — volume de carburant dans le réservoir au début et à la fin de l'itinéraire.
s_lb, s_ub — volume de carburant minimum et maximum dans le réservoir.
w — montant de la pénalité pour violation du niveau de carburant minimum.

Variables :

s_i — volume de carburant dans le réservoir à la i-ème station-service après ravitaillement (réel).
v_i — volume de ravitaillement à la i-ème station-service (réel).
q_i — pourcentage de ravitaillement à la i-ème station-service (entier, de 0 à 4 pour 0 %, 25 %, 50 %, 75 %, 100 %).
b_i — indicateur de ravitaillement à la i-ème station-service (binaire).
z_i — ampleur de la violation du niveau de carburant minimum (réel).

Fonction objectif : Minimiser les coûts totaux de carburant et les pénalités pour les violations du niveau de carburant minimum :

min Σ (p_i v_i + w z_i) pour tout i dans l'ensemble des stations-service.

Contraintes :

Équilibre du carburant : s_i = s_{i-1} - c_i + v_i pour tout i. Cette équation reflète le changement de volume de carburant dans le réservoir après avoir conduit à la station-service suivante et fait le plein.
Multiplicité du ravitaillement : v_i = 0.25 q_i (s_ub - s_{i-1} + c_i) pour tout i. Définit le volume de ravitaillement comme une fraction de l'espace disponible dans le réservoir.
Niveau de carburant minimum : s_{i-1} - c_i + z_i >= s_lb pour tout i. Garantit qu'il y a suffisamment de carburant pour atteindre la prochaine station-service, en autorisant une pénalité z_i pour les violations.
Carburant en fin de parcours : s_{|I|} - c_{|I|+1} >= s_n. Exige un certain volume de carburant à la fin de l'itinéraire.
Ravitaillement minimum : v_i >= v_min * b_i pour tout i. Garantit que le ravitaillement n'a lieu que pour un volume suffisant.
Indicateur de ravitaillement : q_i <= 4 * b_i pour tout i. Relie le pourcentage de ravitaillement à un indicateur binaire, montrant si le ravitaillement a eu lieu.

Dans cette formulation, une contrainte "souple" est utilisée pour le volume de carburant minimum, permettant au modèle de s'adapter aux conditions réelles où une adhésion stricte à toutes les contraintes pourrait être impossible. Cela améliore la fiabilité opérationnelle du modèle. L'application de l'apprentissage par renforcement à un problème aussi complexe avec un espace d'action discret et des pénalités pour les violations permet de trouver des stratégies efficaces qui pourraient être difficiles à obtenir avec des méthodes purement classiques, en particulier lors de la mise à l'échelle à des centaines de stations-service et de prix dynamiquement changeants.

Points clés à retenir

Le RL complète, il ne remplace pas les méthodes classiques : L'apprentissage par renforcement ne vise pas à supplanter complètement les méthodes d'optimisation traditionnelles, mais plutôt à s'intégrer à elles, améliorant leur efficacité ou résolvant des problèmes où les approches classiques rencontrent des limitations.
Les stratégies hybrides sont essentielles : Les approches les plus prometteuses sont les algorithmes hybrides où le RL génère des solutions initiales, adapte les paramètres métaheuristiques ou décompose les problèmes, tandis que les méthodes exactes affinent les détails.
L'OCN étend les capacités mais a des limites : L'optimisation combinatoire neuronale montre un potentiel pour résoudre des problèmes complexes, mais elle est actuellement limitée par la taille et la spécificité des problèmes, nécessitant davantage de recherche pour la généralisation.
Applicabilité pratique en logistique : L'optimisation des arrêts de ravitaillement pour le transport de marchandises est un excellent exemple de la manière dont le RL peut être appliqué pour réduire les coûts opérationnels, offrant des stratégies plus flexibles et économiquement avantageuses par rapport à la gestion manuelle.
Discrétisation pour le RL : La conversion de variables continues en variables discrètes (par exemple, les volumes de ravitaillement) est une méthode efficace pour adapter les problèmes commerciaux du monde réel aux algorithmes d'apprentissage par renforcement, simplifiant la gestion des états et des actions de l'agent.

— Editorial Team