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. / 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.
| Identifer | oai:union.ndltd.org:theses.fr/2016ECLI0025 |
| Date | 21 December 2016 |
| Creators | Danach, Kassem |
| Contributors | Ecole centrale de Lille, Semet, Frédéric, Gelareh, Shahin |
| Source Sets | Dépôt national des thèses électroniques françaises |
| Language | English |
| Detected Language | French |
| Type | Electronic Thesis or Dissertation, Text |
Page generated in 0.002 seconds