Soutenance de thèse de Thanh Tan DOAN (équipe SLP)

Thanh Tan DOAN, doctorant au sein de l’équipe SLP, soutiendra sa thèse intituée « Problème de routage de véhicules avec des contraintes supplémentaires imposées à différents groupes de clients » / « Vehicle routing problems with additional constraints imposed on different groups of customers »

vendredi 2 juillet 2021 à 14h sur Zoom
https://univ-nantes-fr.zoom.us/j/93293101779?pwd=M2ZOdmNOcXdJOElKRER4QmdmRTVWZz09 (ID de réunion : 932 9310 1779 / Code secret : 489264)

Jury :
– Directeur de thèse : Nathalie BOSTEL, Professeur des Universités, Université de Nantes
– Co Directeur de thèse :Minh Hoang HA, Lecturer, Phenikaa University (Vietnam)
– Rapporteurs : Nicolas JOZEFOWIEZ Professeur des Universités, Université de Lorraine ; Dominique FEILLET Professeur, Ecole des Mines de Saint-Etienne (CMP Gardanne)
– Examinateurs : Andréa DUHAMEL Professeur des Universités, Université Le Havre Normandie ; Jorge MENDOZA Professeur agrégé, HEC Montréal (Canada)

Résumé : Le problème de routage de véhicules est l’un des problèmes les plus étudiés en optimisation combinatoire. Au cours des 60 dernières années, un effort considérable de la communauté de recherche universitaire a été consacré pour combler le fossé entre la résolution de problèmes académique et pratique en prenant en compte des contraintes de plus en plus réalistes. Dans de nombreux problèmes du monde réel, les clients qui ont besoin d’un service pourraient être divisés en différents groupes selon leur nature, catégorie, importance ou priorité, etc. Des contraintes supplémentaires sont alors imposées à chaque groupe de clients avec des buts différents, comme le respect d’un ordre de livraison ou la satisfaction d’un niveau minimum de demande. Dans cette recherche, nous considérons trois problèmes qui sont : 1) Problème de routage de véhicule avec règle de priorité assouplie (VRPRPR), 2) Problème de voyageur de commerce en cluster avec règle de priorité assouplie(CTSP-d), et 3) Problème de routage de véhicule en cluster souple (SoftCluVRP). Ces problèmes partagent une caractéristique commune de fournir un service de groupe aux clients et avec des contraintes supplémentaires pour personnaliser le service. Pour le premier problème, nous étendons et améliorons un modèle précédent et introduisons une métaheuristique basée sur la recherche adaptative à voisinage large (ALNS). Nous présentons également un nouvel ensemble d’instances qui simule différentes situations dans l’application du problème avec une méthode pour traiter les contraintes supplémentaires imposées. Pour le deuxième problème, nous présentons de nouveaux modèles et une métaheuristique basée sur la recherche locale itérative (ILS). Pour le troisième problème, nous avons introduit différentes formulations et métaheuristiques basées sur la recherche de voisinage variable (VND). Des expériences sont menées sur chaque problème et comparées aux études précédentes pour illustrer les performances du contenu proposé.

Mots-clés : VRP, TSP, métaheuristique, priorité client, règle de priorité assouplie, contraintes de niveau de service
——————————————————————————————————————————————————————————————————————-
Abstract: The vehicle Routing Problem is one of the most studied problems in combinatorialoptimization. In the last 60 years, an extensive effort of academic research community has been devoted to fill the gap between academic and practical problem solving by considering more and more realistic constraints. In many real-world problems, customers who require service could be divided into different groups according to their nature, category, importance, or priority, etc. Additional constraints are then imposed on each group of customers with different purposes such as delivery order or minimum demand satisfaction level. In this research, we consider three problems that are: 1) Vehicle Routing Problem with Relaxed Priority Rule (VRP-RPR), 2) Clustered Traveling Salesman Problem with Relaxed Priority Rule (CTSP-d), and 3) Soft Cluster Vehicle
Routing Problem (SoftCluVRP). These problems share a common feature of providing group-based service to customers and with additional constraints to customize service.
For the first problem, we extend and improve a previous model and introduce an Adaptive Large Neighborhood Search (ALNS)-based metaheuristic. We also present a new instance set that simulates different situations in applying the problem with a method to deal with additional constraints imposed. For the second problem, we present new models and an Iterated Local Search (ILS)-based metaheuristic. For the third problem, we introduced different formulations and a Variable Neighborhood Search (VND)-based metaheuristic. Experiments are conducted on each problem and compare with previous studies to illustrate the performance of proposed content.

Keywords: VRP, TSP, metaheuristic, customer priority, relaxed priority rule, service level constraints