Recherche locale et structures de voisinages pour des problèmes de tournées de véhicules : algorithmes séquentiels et parallèles / César Augusto De Sousa Vale Rego ; sous la dir. de Catherine Roucairol

Date :

Editeur / Publisher : [S.l.] : [s.n.] , 1996

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Optimisation combinatoire

Algorithmes parallèles

Circuits de distribution

Classification Dewey : 005

Roucairol, Catherine (1947-.... ; mathématicienne) (Directeur de thèse / thesis advisor)

Université de Versailles-Saint-Quentin-en-Yvelines (1991-....) (Organisme de soutenance / degree-grantor)

Relation : Recherche locale et structures de voisinages pour des problemes de tournees de vehicules : algorithmes sequentiels et paralleles / Cesar Rego / Grenoble : Atelier national de reproduction des thèses , 1996

Résumé / Abstract : Cette thèse concerne l'étude, développement et évaluation de structures de voisinage efficaces vis-à-vis de leur utilisation dans des méthodes de recherche locale, ou plus générique dans les metaheuristiques. Nous introduisons plusieurs structures de voisinage pour générer des mouvements composés pour des problèmes de tournées de véhicules provenant autant de la littérature que d'applications réelles. Concernant le premier groupe de problèmes nous proposons des structures de voisinage fondées sur l'idée de chaînes d'éjection. Nous considérons donc des chaînes éjectant des noeuds, arcs ou plus génériquement des sous chemins. De plus, différentes techniques de parallélisation sont utilisées pour mieux explorer l'espace de recherche ainsi que pour accélérer l'évaluation d'une chaîne d'éjection