Thesis of Yihan Liu

Optimisation de problème de tournées de véhicules de service à domicile

La performance logistique des entreprises et l’optimisation des transports sont devenues un grand problème ces dernières années. La planification et l’optimisation des services constituent en particulier un nouveau défi. Afin d’accroître la productivité et de réduire les coûts de la logistique, ce travail de recherche contribue à l’optimisation d’un problème de tournées de service à domicile multidépôt, multi-période avec fenêtres de temps de vie réelle. Le problème vient d’un contexte réaliste et est formulé comme un modèle en Mixed Integer Programming (MIP). Les résultats avec Cplex montrent que ce problème ne peut être résolu par des méthodes exactes dans un délai raisonnable pour une utilisation pratique. Par conséquent, nous introduisons des heuristiques. Premièrement, les heuristiques de recherche locales sont utilisées pour résoudre le problème. Les solutions réalisables initiales sont générées par une heuristique de construction et plusieurs heuristiques de recherche locales sont appliquées pour obtenir des solutions dans un temps de calcul assez court. Ensuite, nous proposons un algorithme génétique avec une nouvelle représentation du chromosome et de nouveaux opérateurs génétiques pour le problème abordé. Enfin, nous considérons un algorithme génétique avec contrôle de la diversité pour problèmes à grande échelle. Les solutions infaisables sont prises en compte dans la population et la contribution à la diversité fait partie de l’évaluation afin d’éviter une recherche prématurée. Ces méthodes ont été mises en oeuvre avec succès pour optimiser le problème de tournées.

Jury

Directeur de thèse : M. Abdelkader EL KAMEL, Ecole Centrale de Lille Rapporteurs : M. Khaled MELLOULI, IHEC Carthage Mme Shaoping WANG, Beihang University (BUAA) Membres : M. Pierre BORNE, Ecole Centrale de Lille M. Khaled MESGHOUNI, Ecole Centrale de Lille M. Dumitru POPESCU, Université Polytechnique de Bucarest Mme Zhuoyue SONG, Beijing Institute of Technology (BIT) Mme Liming ZHANG, University of Macau

Thesis of the team OSL defended on 27/06/2017