/
0/5

0 avis

Méthodes d'extraction pour la résolution de problèmes d'optimisation combinatoire


Type de document : Thèse
Langue : français -- anglais

Responsabilité(s) :


Responsabilité(s) secondaire (s) :
Université de soutenance : Université de Technologie de Compiègne

Numéro national de thèse : 2011COMP1985

Spécialité : Technologies de l'information et des systèmes

Lieu d'édition : Compiègne
Editeur : UTC
Année de publication : 2011


Domaine (s) :


Sujets :


Mots clés :

Indice LC : QA402.5
Indice Dewey : 519.3
Code domaine du SUDOC : 510

Résumé français :

  • Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes d'optimisation difficiles. Notre idée centrale pour procéder à l'élaboration d'heuristiques et métaheuristiques efficaces est d'exploiter les sous-structures du problème à traiter pour lesquelles la résolution est plus facile. Nous avons introduit une approche de résolution basée sur une méthode d'extraction. Nous avons ainsi traité efficacement un problème particulier de tournées avec profits (TOP) grâce à une propriété de dominance des tournées saturées. Une approche similaire a permis de traiter le problème de la clique maximum en utilisant des métaheuristiques avancées avec des schémas heuristiques hybrides. Nous avons également montré l'utilité et l'efficacité des méthodes développées comme l'heuristique de destruction/construction dans un contexte industriel. Il s'agit de la planification des visites pour relever les compteurs d'eau avec l'introduction du radio-relevé.

Résumé anglais :

  • In this thesis, we focused on the development of heuristic solutions for solving NP-Hard combinatorial optimization problems. Our main idea is to exploit substructures of the problems for which the resolution is polynomial. We introduced a new resolution approach, called extraction method. Based this method and on a dominance property of saturated tours, we proposed two effective algorithms for solving the Team Orienteering Problem (TOP). Using the same principle, we proposed an advanced hybrid metaheuristic for the Maximum Clique Problem. We have also shown the effectiveness of the developed methods such as destruction/ construction heuristic with an industrial application. The application consists of optimizing the process of organizing water meter readings during the transition to the automatic reading technology.

Autre(s) titre(s) : Extraction methods for solving combinatorial optimization problems


Consulter en ligne

Suggestions

Du même auteur

Subgraph extraction and metaheuristics for the maximum clique problem | Moukrim, Aziz

Subgraph extraction and metaheuristics for the maximum clique problem / Moukrim, Aziz - Dang, Duc-Cuong - Springer Science & Business Media, 2012

The maximum clique problem involves finding the largest set of pairwise adjacent vertices in a graph. The problem is classic but still attracts much attention because of its hardness and its prominent applications. Our work is bas...

Source : Ressources électroniques

EXTR|EXTR

Méthodes d'extraction pour la résolution de problèmes d'optimisation combinatoire | Dang, Duc-Cuong. Auteur

Méthodes d'extraction pour la résolution de problèmes d'optimisation combinatoire / Dang, Duc-Cuong. Auteur - [s.n.], 2011

Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes d'optimisation difficiles. Notre idée centrale pour procéder à l'élaboration d'heuristiques et métaheuristiques efficaces est d'exploiter les sou...

Source : Catalogue

A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints | Moukrim, Aziz

A simulated annealing algorithm for the vehicle routing problem with time windows and synchronization constraints / Moukrim, Aziz - Dang, Duc-Cuong - Afifi, Sohaib - Springer Verlag, 2013

This paper focuses on solving a variant of the vehicle routing problem (VRP) in which a time window is associated with each customer service and some services require simultaneous visits from different vehicles to be accomplished....

Source : Ressources électroniques

EXTR|EXTR

Du même sujet

Méthodes d'extraction pour la résolution de problèmes d'optimisation combinatoire | Dang, Duc-Cuong. Auteur

Méthodes d'extraction pour la résolution de problèmes d'optimisation combinatoire / Dang, Duc-Cuong. Auteur - [s.n.], 2011

Dans cette thèse, nous nous sommes intéressés à la résolution approchée de problèmes d'optimisation difficiles. Notre idée centrale pour procéder à l'élaboration d'heuristiques et métaheuristiques efficaces est d'exploiter les sou...

Source : Catalogue

Selective and co-modal transport | Amarouche, Youcef (19..-....). Auteur

Selective and co-modal transport : models and algorithms / Amarouche, Youcef (19..-....). Auteur, 2019

Dans cette thèse nous nous intéressons au développement de nouvelles méthodes de résolution pour des problèmes de tournées de véhicules dans des systèmes de logistique urbaine dans un contexte de co-modalité. Plus précisément, nou...

Source : Ressources électroniques

THES|THES

Selective vehicle routing problem | Yahiaoui, Ala-Eddine (19..-....). Auteur

Selective vehicle routing problem : cluster and synchronization constraints / Yahiaoui, Ala-Eddine (19..-....). Auteur, 2018

Le problème de tournées de véhicules (Vehicle Routing Problem - VRP) est un problème d'optimisation combinatoire utilisé généralement pour modéliser et résoudre des différents problèmes rencontrés dans les systèmes logistiques et ...

Source : Ressources électroniques

THES|THES

Chargement des enrichissements...

Avis des lecteurs