Optimisation de problème de tournées de véhicules de service à domicile / Yihan Liu ; sous la direction de Abdelkader El Kamel

Date :

Type : Livre / Book

Type : Thèse / Thesis

Langue / Language : anglais / English

Algorithmes génétiques

Heuristique

Problème de tournées de véhicules

Logistique (gestion)

Transport -- Planification

Métaheuristiques

El Kamel, Abdelkader (1965-....) (Directeur de thèse / thesis advisor)

Borne, Pierre (Président du jury de soutenance / praeses)

Mellouli, Khaled (Rapporteur de la thèse / thesis reporter)

Wang, Shaoping (Rapporteur de la thèse / thesis reporter)

Mesghouni, Khaled (1968-....) (Membre du jury / opponent)

Popescu, Dumitru (1944-....) (Membre du jury / opponent)

École centrale de Lille (1872-2019) (Organisme de soutenance / degree-grantor)

École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) (Ecole doctorale associée à la thèse / doctoral school)

Centre de Recherche en Informatique, Signal et Automatique de Lille (Laboratoire associé à la thèse / thesis associated laboratory)

Résumé / Abstract : 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 multi-dé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 œuvre avec succès pour optimiser le problème de routage.

Résumé / Abstract : The logistics performance of enterprises and the optimization of transportation have become a great issue in recent years. Field force planning and optimization is a new challenge for the service sector. In order to increase productivity and reduce cost of logistics, this research contributes to the optimization of a real-life multi-depot multi-period field service routing problem with time window. The problem is abstracted from the realistic problem and formulated as a Mixed Integer Programming (MIP) model. Computational results with Cplex show that this problem cannot be solved by exact methods in reasonable time for practical use. First, local search heuristics are used for solving the problem. Initial feasible solutions are generated by a constructive heuristic and several local search heuristics are applied to obtain solutions in a very short computing time. Then we propose a genetic algorithm with new representation of chromosome and new genetic operators for the addressed problem. Finally we consider a genetic algorithm with diversity control to deal with large scale problems. Infeasible solutions are taken account in the population and the diversity contribution is part of the evaluation to avoid premature of search. These methods have been successfully implemented to the optimization of the routing problem