Partenaires

CNRS
Ministère de l'Enseignement Supérieur et de la Recherche
Ecole Centrale de Lille
Université de Lille 1
CRIStAL

« janvier 2017 »
L M M J V S D
26 27 28 29 30 31 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 1 2 3 4 5


Rechercher

Sur ce site

Sur le Web du CNRS


Accueil du site > A noter

Soutenance de Thèse : Sixtine BINART

Titre de la Thèse  :

"Optimisation de tournées de service en temps réel"

Date  :

Vendredi 28 mars 2014 - 14 h 30 - Amphithéâtre Poirier - Ecole Centrale de Lille

Le jury est composé de :

Directeurs de Thèse : Nicolaï CHRISTOV et Michel GENDREAU

Co-directeur de Thèse : Frédéric SEMET

Rapporteurs : François LOUVEAUX et Daniele VIGO

Membres : Dominique FEILLETLouis-Martin ROUSSEAU et Gilles PESANT

Membre invité : Pierre DEJAX

Résumé :

Les tournées de service concernent l’organisation de déplacement de personnels vers des clients afin d’effectuer différentes activités techniques ou commerciales. Ces tournées peuvent devoir répondre à des objectifs et faire face à des contraintes nombreuses et complexes. Lors de la planification et de l’exécution de tournées de service mono-période, les entreprises sont confrontées aux aléas des temps de service et de parcours. C’est pourquoi, dans cette thèse, nous nous intéressons à une variante du problème de tournées de service, dans laquelle les temps de parcours et de service sont stochastiques. Il s’agit du problème de tournées de service multi-dépôt, incluant fenêtres de temps, temps de service et de parcours stochastiques avec priorité entre les clients (distinction clients obligatoires / clients optionnels). Afin de résoudre cette problématique, nous proposons trois méthodes différentes. Dans la première méthode, nous construisons d’abord des routes contenant uniquement des clients obligatoires puis nous procédons à l’insertion des clients optionnels. La deuxième méthode est une méthode approchée basée sur la génération de colonnes consistant à générer un ensemble de routes de bonne qualité pour chaque véhicule puis à en sélectionner une par véhicule. La dernière méthode est un algorithme de branch and price basé sur la deuxième méthode. Le sous-problème consiste à générer des routes réalisables pour un véhicule donné, tandis que le problème maître permet de sélectionner des routes en s’assurant que la priorité des clients est respectée. Après chacune de ces méthodes, afin d’évaluer la qualité de ces solutions face aux aléas, nous utilisons un algorithme de programmation dynamique et procédons à un ensemble de simulations du déroulement des tournées en temps réel. Nous avons testé ces méthodes sur des problèmes dont les données sont issues du milieu industriel.

PhD Thesis Tiltle :

Real-time optimization of technician tours

Abstract :

The field service routing problem consists in assigning the visits of technicians to clients in order to satisfy their requests for service activities such as maintenance. When planning service routes, companies have to face hazardous travel and service times. Therefore, in this thesis, we deal with a variant of the single-period field service routing problem in which travel and service times are stochastic. It is the field service routing problem with multiple depots, time windows, stochastic travel and service times and priority within customers (distinguishing mandatory and optional customers). To solve this problem, we propose three different methods. In the first one, we first build routes containing only mandatory customers and then, we insert optional customers in these routes. The second one is a heuristic method based on column generation consisting in generating a set of valuable routes for each vehicle and then in selecting one route per vehicle. The last method is a branch and price algorithm, based on the second method, in which the subproblem consists in finding feasible routes for a given vehicle, whereas the master problem consists in selecting routes while ensuring that customer’s priority is respected. After each of these methods, in order to evaluate the quality of these solutions regarding stochasticity, we use a dynamic programming algorithm and we proceed to a set of simulations of the real-time execution of the service activities over the period. All our experimentations have been made on problems coming from realistic data.