Date : 2006
Editeur / Publisher : [S.l.] : [s.n.] , 2006
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : Le problème de collectes et livraisons consiste à déterminer les tournées d'une flotte de véhicules devant satisfaire un ensemble de demandes de transport. L'application réelle étudiée dans cette thèse est le transport par hélicoptère du personnel de compagnies pétrolières. Ce problème fait partie des problèmes de collectes et livraisons (pick-up and delivery problem–PDP). Dans une première partie, nous donnons une définition et une classification de ces problèmes, puis nous décrivons les problèmes plus particulièrement étudiés dans cette thèse. Un état de l'art des principaux travaux dans ce domaine termine cette première partie. Dans un deuxième temps, des méthodes approchées sont proposées. Nous présentons tout d'abord des méthodes visant à minimiser la durée totale des tournées. Il s'agit de méthodes d'insertion et d'amélioration, et d'une metaheuristique plus performante de type algorithme mémétique. Ensuite nous présentons un algorithme de type NSGA-II (Non-dominated sorting genetic algorithm) pour résoudre une variante bi-objectif du problème dans lequel la durée totale des tournées doit être minimisée tout en satisfaisant les demandes les plus urgentes en priorité. Enfin, la troisième partie est dédiée aux méthodes de résolution exactes. Tout d'abord le problème mono-objectif est modélisé par un programme linéaire. Puis, un modèle de recouvrement résolu par la technique de génération de colonnes est proposé. Cette technique, utilisant un algorithme de programmation dynamique, est améliorée par l'inclusion d'une recherche taboue répétitive. Toutes ces approches sont testées sur des jeux de données réelles et aléatoires qui en démontrent l'intérêt
Résumé / Abstract : The pick-up and delivery problem (PDP) is the one of finding a set of optimal routes for a fleet of vehicles in order to serve a set of transportation requests. The specific application studied in this thesis is the personnel transportation within a set of oil platforms by one helicopter. This research work is developed in three parts. The first one introduces the different existing types of pick-up and delivery problems. The studied problem is fully described and a literature review of existing solution methods is presented. In the second part, approximate solution methods are proposed in order to minimise the total travel duration of the routes. Greedy and local search methods, as well as a metaheuristic of the type of memetic algorithms are presented. Then a bi-objective version that minimize the total duration satisfying the most urgent transportation requests in priority is solved. The proposed method was inspired in a Non-dominated Sorting Genetic Algorithm (NSGA-II). The third part deals with exact methods. The problem is first modelled as a linear program. Then a covering model solved by a column generation technique is presented. A first technique using a dynamic programming algorithm is improved with a taboo search with restart. All algorithms are tested on randomly generated instances as well as on real instances provided by a petroleum company, this demostrating the interest of the use the method developed.