Hyperheuristiques pour des problèmes ...
Document type :
Thèse
Title :
Hyperheuristiques pour des problèmes d’optimisation en logistique
English title :
Hyperheuristics in Logistics
Author(s) :
Danach, Kassem [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Thesis director(s) :
Frédéric Semet
Shahin Gelareh
Shahin Gelareh
Defence date :
2016-12-21
Jury president :
Laetitia Jourdan [Président]
Adnan Yassine [Rapporteur]
Reza Abdi [Rapporteur]
Adnan Yassine [Rapporteur]
Reza Abdi [Rapporteur]
Jury member(s) :
Laetitia Jourdan [Président]
Adnan Yassine [Rapporteur]
Reza Abdi [Rapporteur]
Adnan Yassine [Rapporteur]
Reza Abdi [Rapporteur]
Accredited body :
Ecole Centrale de Lille
Doctoral school :
École doctorale Sciences pour l'ingénieur (Lille)
NNT :
2016ECLI0025
Keyword(s) :
Métaheuristique
Heuristique
Hyperheuristique
Matheuristique
Apprentissage par renforcement
Problème de localisation des concentrateurs
Problème d’ordonnancement de workover
Règles d’association
Heuristique
Hyperheuristique
Matheuristique
Apprentissage par renforcement
Problème de localisation des concentrateurs
Problème d’ordonnancement de workover
Règles d’association
English keyword(s) :
Metaheuristic
Heuristic
Hyperheuristic
Matheuristic
Reinforcement learning
Hub location problem
Workover rig shceduling problem
Association rules
Heuristic
Hyperheuristic
Matheuristic
Reinforcement learning
Hub location problem
Workover rig shceduling problem
Association rules
HAL domain(s) :
Mathématiques [math]/Combinatoire [math.CO]
French abstract :
Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche ...
Show more >Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche alternative consiste soit à utiliser des métaheuristiques ou des matheuristiques qui reposent en partie sur des méthodes exactes. Dans le contexte de l'optimisation combinatoire, nous nous intéressons des heuristiques permettant de choisir les heuristiques appliquées au problème traité. Dans cette thèse, nous nous concentrons sur l'optimisation à l’aide d’hyperheuristiques pour des problèmes logistiques. Nous proposons un cadre hyperheuristique qui effectue une recherche dans l'espace des algorithmes heuristiques et apprend comment changer l'heuristique courante systématiquement tout au long du processus de telle sorte qu'une bonne séquence d'heuristiques permet d’obtenir des solutions de haute qualité. Nous étudions plus particulièrement deux problèmes en logistique pour lesquels nous proposons des HHs: un problème de planification d’interventions sur des puits de forage et un problème conjoint de localisation de hubs et de routage. Ensuite, nous comparons les performances de plusieurs HH décrites dans la littérature pour le second problème abordé reposant sur différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, une approche de Q-Learning et un algorithme de colonie de fourmis. Les résultats numériques prouvent l'efficacité de HHs pour les deux problèmes traités, et la pertinence d'inclure l'information venant d’une relaxation de Lagrangienne pour le deuxième problème.Show less >
Show more >Le succès dans l'utilisation de méthodes exactes d’optimisation combinatoire pour des problèmes de grande taille est encore limité à certains problèmes ou à des classes spécifiques d'instances de problèmes. Une approche alternative consiste soit à utiliser des métaheuristiques ou des matheuristiques qui reposent en partie sur des méthodes exactes. Dans le contexte de l'optimisation combinatoire, nous nous intéressons des heuristiques permettant de choisir les heuristiques appliquées au problème traité. Dans cette thèse, nous nous concentrons sur l'optimisation à l’aide d’hyperheuristiques pour des problèmes logistiques. Nous proposons un cadre hyperheuristique qui effectue une recherche dans l'espace des algorithmes heuristiques et apprend comment changer l'heuristique courante systématiquement tout au long du processus de telle sorte qu'une bonne séquence d'heuristiques permet d’obtenir des solutions de haute qualité. Nous étudions plus particulièrement deux problèmes en logistique pour lesquels nous proposons des HHs: un problème de planification d’interventions sur des puits de forage et un problème conjoint de localisation de hubs et de routage. Ensuite, nous comparons les performances de plusieurs HH décrites dans la littérature pour le second problème abordé reposant sur différentes méthodes de sélection heuristique telles que la sélection aléatoire, la fonction de choix, une approche de Q-Learning et un algorithme de colonie de fourmis. Les résultats numériques prouvent l'efficacité de HHs pour les deux problèmes traités, et la pertinence d'inclure l'information venant d’une relaxation de Lagrangienne pour le deuxième problème.Show less >
English abstract : [en]
Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics ...
Show more >Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics that rely on exact methods in some ways. In the context of combinatorial optimization, we are interested in heuristics to choose heuristics invoked to solve the addressed problem. In this thesis, we focus on hyperheuristic optimization in logistic problems. We focus on proposing a hyperheuristic framework that carries out a search in the space of heuristic algorithms and learns how to change the incumbent heuristic in a systematic way along the process in such a way that a good sequence of heuristics produces high quality solutions. We propose HHs for two problems in logistics: the workover rig scheduling problem and the hub location routing problem. Then, we compare the performances of several HHs described in the literature for the latter problem, which embed different heuristic selection methods such as a random selection, a choice function, a Q-Learning approach, and an ant colony based algorithm. The computational results prove the efficiency of HHs for the two problems in hand, and the relevance of including Lagrangian relaxation information for the second problem.Show less >
Show more >Success in using exact methods for large scale combinatorial optimization is still limited to certain problems or to specific classes of instances of problems. The alternative way is either using metaheuristics or matheuristics that rely on exact methods in some ways. In the context of combinatorial optimization, we are interested in heuristics to choose heuristics invoked to solve the addressed problem. In this thesis, we focus on hyperheuristic optimization in logistic problems. We focus on proposing a hyperheuristic framework that carries out a search in the space of heuristic algorithms and learns how to change the incumbent heuristic in a systematic way along the process in such a way that a good sequence of heuristics produces high quality solutions. We propose HHs for two problems in logistics: the workover rig scheduling problem and the hub location routing problem. Then, we compare the performances of several HHs described in the literature for the latter problem, which embed different heuristic selection methods such as a random selection, a choice function, a Q-Learning approach, and an ant colony based algorithm. The computational results prove the efficiency of HHs for the two problems in hand, and the relevance of including Lagrangian relaxation information for the second problem.Show less >
Language :
Anglais
Collections :
Source :
Files
- https://tel.archives-ouvertes.fr/tel-01485160/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-01485160/document
- Open access
- Access the document
- https://tel.archives-ouvertes.fr/tel-01485160/document
- Open access
- Access the document
- document
- Open access
- Access the document
- Danach_Kassem_DLE.pdf
- Open access
- Access the document