Hyperheuristiques pour des problèmes d’optimisation en logistique

Abstract

Le succès dans l’utilisation de méthodes exactes dans l’optimisation combinatoire à grande échelle est encore limité à certains problèmes, et peut-être des classe sspécifiques d’instances de problèmes. Le moyen alternatif consiste soit à utiliser des métaheuristiques ou des mathématiques qui utilisent des méthodes exactes à certains égards. Le concept d’hyperheuristique (HH) est une généralisation de celle des métaheuristiques. Dans le contexte de l’optimisation combinatoire, nous nous intéressons à l’heuristique pour choisir l’heuristique. Les deux catégories hyperheuristiques principales de la classification précédente sont: 1) la sélection heuristique, qui considère une méthode pour sélectionner des heuristiques à partir d’un ensemble d’heuristiques existantes, et 2) la génération heuristique qui consiste à générer de nouvelles heuristiques à partir des composantes des heuristiques existantes.

Dans cette thèse, nous nous concentrons sur l’optimisation hyperheuristique des problèmes logistiques. Nous présentons une revue de littérature détaillée sur les termes origine, concept, domaine d’application, etc. Ensuite, deux problèmes logistiques ont été choisis pour lesquels nous avons proposé HH. Sur la base de la structure générale d’une solution réalisable et en exploitant les informations cachées dans les données d’entrée, nous définissons un ensemble d’heuristiques possibles pour chaque problème. Nous nous concentrons ensuite sur la proposition d’un cadre hyperheuristique qui effectue une recherche dans l’espace des algorithmes heuristiques et apprend comment changer l’heuristique en place d’une manière systématique le long du processus de telle sorte qu’une bonne séquence d’heuristiques produit des solutions de haute qualité. Notre cadre hyperheuristique est équipé d’un mécanisme d’apprentissage qui apprend l’environnement et guide la transition d’une heuristique historique à une autre jusqu’à ce que l’algorithme global se termine.

Le premier problème abordé est le problème d’ordonnancement de la plateforme de workover (WRSP), qui consiste à trouver le meilleur horaire pour un certain nombre de plates-formes de workover pour minimiser la perte de production, associée à un grand nombre de puits en attente de maintenance. Un algorithme d’hyperheuristique de sélection est proposé, qui est guidé par un mécanisme d’apprentissage conduisant à un choix approprié de mouvements dans l’espace des heuristiques qui sont appliquées pour résoudre le problème. Nos expériences numériques sont menées sur des exemples d’une étude de cas de Petrobras, la Société nationale brésilienne du pétrole, et ont été comparées avec une méthode exacte prouvant son efficacité.

Le deuxième problème est une variante du problème de routage d’emplacement de concentrateur, qui cherche à diviser les noeuds en moyeux et rayons. Deux HH différentes ont été appliquées à deux variantes de ce problème, qui sont dérivées d’un problème d’acheminement de localisation de concentrateur de capacité d’allocation unique et diffèrent principalement dans la définition de la capacité. Dans le premier, le nombre de rayons pouvant être attribué à chaque hub est limité; Tandis que dans la seconde, c’est le volume de l’écoulement circulant sur la voie du rayon-niveau. De plus, cinq relaxations lagrangiennes (LR) ont été proposées pour le premier problème afin d’utiliser certains résultats pendant le processus de HH. Les résultats de calcul prouvent l’efficacité de HH et la pertinence d’inclure l’information LR. Enfin, nous comparons les performances de plusieurs HH proposées dans la littérature pour le problème précédemment abordé, avec différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, Q-Learning et la colonie de fourmis.

Date of Award	21 Dec 2016
Original language	French
Awarding Institution	École centrale de Lille
Supervisor	Frédéric Semet (Supervisor), Shahin Gelareh (Supervisor) & Wissam Khalil (Supervisor)