Amélioration des performances du schéma de la génération de colonnes : application aux problèmes de tournées de véhicules / Nora Touati ; sous la dir. de Anass Nagih

Date :

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

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : français / French

Décomposition (mathématiques)

Relaxation, Méthodes de (mathématiques)

Programmation dynamique

Nagih, Anass (Directeur de thèse / thesis advisor)

Université Sorbonne Paris Nord (Bobigny, Villetaneuse, Seine-Saint-Denis ; 1970-....) (Organisme de soutenance / degree-grantor)

Relation : Amélioration des performances du schéma de la génération de colonnes : application aux problèmes de tournées de véhicules / Nora Touati ; sous la direction de Anass Nagih / Lille : Atelier national de reproduction des thèses , 2008

Résumé / Abstract : La génération de colonnes est une méthode dédiée à la résolution de problèmes d'optimisation combinatoire de grande taille. Les méthodes utilisant cette approche de résolution ont souvent des problèmes de convergence, particulièrement quand elles sont utlisées pour résoudre des problèmes pratiques, de grandes dimensions. Nous nous intéressons dans cette thèse à l'accéleration de la méthode de génération de colonnes. Nous proposons des téchniques de diversification pour diminuer le nombre total de colonnes généreés ainsi que le temps de résolution des problèmes maîtres.Nous nous intéressons également à la résolution éfficace des sous-problèmes en utilisant des techniques de réoptimisation, mais aussi en proposant des améliorations de la méthode de programmation dynamique. Les approches sont validées expérimentalement sur le problème de tournées de véhicules avec fénêtre de temps.

Résumé / Abstract : Columgeneration algorithms are instrumental in many areas of applied optimization where linear programs with an enormous number of variables need to be solued. Although success fully used in many applications, this method suffers from well-known "instability" issues, that somewhat limit its efficiency. This work focuses on accelerating strategies in a column generation algorithm. We propose some diversifiication methods in order to decrease the total number of generated columns and then master problems resolution time. We interest also to solving efficiently the pricing problems, by proposing an improning approch based on reoptimization principle and a new variant of the dynamic programming algorithm. The effectiveness of these approches is validated on vehicule routing problem with time windows