• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Thèses
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail

Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems

Recherche Locale, structures de données et Recherche Monte-Carlo pour les problèmes d'optimisation combinatoire Multi-Objectif

Cornu, Marek (2017), Local Search, data structures and Monte Carlo Search for Multi-Objective Combinatorial Optimization Problems, doctoral thesis prepared under the supervision of Cazenave, Tristan; Vanderpooten, Daniel, Université Paris Dauphine

View/Open
2017PSLED043.pdf (4.323Mb)
Type
Thèse
Date
2017-12-18
Metadata
Show full item record
Author(s)
Cornu, Marek
Under the direction of
Cazenave, Tristan; Vanderpooten, Daniel
Abstract (FR)
De nombreux problèmes d'optimisation combinatoire considèrent plusieurs objectifs, souvent conflictuels. Cette thèse s'intéresse à l'utilisation de méthodes de recherche locale, de structures de données et de recherche Monte-Carlo pour la recherche de l'ensemble des solutions efficaces de tels problèmes, représentant l'ensemble des meilleurs compromis pouvant être réalisés en considération de tous les objectifs.Nous proposons une nouvelle méthode d'approximation appelée 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combinant les concepts de recherche locale Pareto (PLS) et de décomposition. La PLS est une descente de recherche locale adaptée au multi-objectif, et la décomposition consiste en la subdivision du problème multi-objectif en plusieurs problèmes mono-objectif. Deux méthodes d'optimisation mono-objectif sont considérées: la recherche locale itérée et la recherche Monte-Carlo imbriquée. Deux modules principaux sont intégrés à 2PIPLS/D. Le premier généralise et améliore une méthode existante et génère un ensemble initial de solutions. Le second réduit efficacement l'espace de recherche et permet d'accélérer la PLS sans négliger la qualité de l'approximation générée. Nous introduisons aussi deux nouvelles structures de données gérant dynamiquement un ensemble de solutions incomparables, la première est spécialisée pour le cas bi-objectif et la seconde pour le cas général.2PIPLS/D est appliquée au Problème du Voyageur de Commerce bi-objectif et tri-objectif et surpasse ses concurrents sur les instances testées. Ensuite, 2PIPLS/D est appliquée à un nouveau problème avec cinq objectifs en lien avec la récente réforme territoriale d'agrandissement des régions françaises.
Abstract (EN)
Many Combinatorial Optimization problems consider several, often conflicting, objectives. This thesis deals with Local Search, data structures and Monte Carlo Search methods for finding the set of efficient solutions of such problems, which is the set of all best possible trade-offs given all the objectives.We propose a new approximation method called 2-Phase Iterated Pareto Local Search based on Decomposition (2PIPLS/D) combining the notions of Pareto Local Search (PLS) and Decomposition. PLS is a local search descent adapted to Multi-Objective spaces, and Decomposition consists in the subdivision of the Multi-Objective problem into a number of Single-Objective problems. Two Single-Objective methods are considered: Iterated Local Search and Nested Monte Carlo Search. Two main components are embedded within the 2PIPLS/D framework. The first one generalizes and improves an existing method generating an initial set of solutions. The second one reduces efficiently the search space and accelerates PLS without notable impact on the quality of the generated approximation. We also introduce two new data structures for dynamically managing a set of incomparable solutions. The first one is specialized for the bi-objective case, while the second one is general.2PIPLS/D is applied to the bi-objective and tri-objective Traveling Salesman Problem and outperforms its competitors on tested instances. Then, 2PIPLS/D is instantiated on a new five-objective problem related to the recent territorial reform of French regions which resulted in the reassignment of departments to new larger regions.
Subjects / Keywords
Optimisation combinatoire multi-Objectif; Méta-Heuristique; Recherche locale; Structures de données; Décomposition; Recherche Monte-Carlo; Problème du Voyageur de Commerce; Multi-Objective combinatorial optimization; Meta-Heuristic; Local search; Data structures; Decomposition; Monte Carlo search; Traveling Salesman Problem
JEL
C15 - Statistical Simulation Methods: General

Related items

Showing items related by title and author.

  • Thumbnail
    Résolution de problèmes d'optimisation combinatoire mono et multi-objectifs par énumération ordonnée 
    Belhoul, Lyes (2014-12) Thèse
  • Thumbnail
    Approches de résolution exacte et approchée en optimisation combinatoire multi-objectif, application au problème de l'arbre couvrant de poids minimal 
    Lacour, Renaud (2014-07) Thèse
  • Thumbnail
    Représentations discrètes de l'ensemble des points non dominés pour des problèmes d'optimisation multi-objectifs 
    Jamain, Florian (2014-06) Thèse
  • Thumbnail
    Règles de dominance pour la recherche de solutions Choquet-optimales en optimisation combinatoire multi-objectifs 
    Fouchal, Hugo; Galand, Lucie; Lesca, Julien; Perny, Patrice (2012) Communication / Conférence
  • Thumbnail
    Multiobjective optimization for complex systems 
    Kerberenes, Antoine (2021-12-03) Thèse
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo