Le problème de tournées de véhicules

Le problème de tournées de véhicules

Organisation de la thèse

Cette thèse est organisée en 4 chapitres: Dans le premier chapitre, nous présentons un état de l’art sur la chaîne logistique en général et la logistique de distribution et de transport en particulier. Nous allons nous concentrer sur les trois activités décrites ci-dessus en donnant une définition détaillée avec une formulation mathématique et en explicitant les variantes les plus connues de chaque problème. Enfin, nous terminerons ce chapitre en décrivant les outils utilisés pour la résolution des problèmes d’optimisation des chaînes logistiques. Dans le deuxième chapitre, nous allons aborder le problème de localisation-routage à grande échelle avec contrainte de capacité en proposant un nouvel algorithme de résolution. L’algorithme est composé de deux grandes phases combinant la recherche Tabou avec le recuit simulé. Dans cette méthode, la recherche Tabou est consacrée pour le sous-problème de routage et le sousproblème de localisation est résolu en utilisant le recuit simulé. Dans le troisième chapitre, nous allons étudier le problème de routage avec gestion de stock multi-périodes, multi-produits et multi-véhicules en développant une heuristique de type GRASP. Cette méthode se compose de deux phases : une heuristique gloutonne randomisée utilisée pour construire une solution faisable de bonne qualité et une recherche locale. Comme recherche locale dans le GRASP, nous allons utiliser la métaheuristique recherche Tabou. Dans le quatrième chapitre, nous présenterons une contribution pour une nouvelle variante du problème d’élaboration des tournées de véhicules à savoir le problème de routage de navettes et de taxis. Il s’agit d’un problème industriel qui concerne le transport de personnel. Le but est de transporter un ensemble de passagers depuis leurs arrêts de bus vers un dépôt central en 2 3. Organisation de la thèse utilisant une flotte de véhicules hétérogènes. Pour résoudre le problème, nous proposerons deux méthodes, à savoir une recherche Tabou et une méthode de type GRASP. Enfin, nous terminerons cette thèse avec une conclusion générale par rapport aux résultats obtenus et un ensemble de perspectives pour des futurs trava

La chaîne logistique

La logistique a pour origine un mot grec qui indique l’art du raisonnement et du calcul [80, 77]. La notion de logistique a été utilisée en premier lieu dans le domaine militaire en référant à tout ce qui est nécessaire à l’application sur le terrain des décisions tactiques et stratégiques. Après la fin de la seconde guerre mondiale et avec la grande évolution du marché industriel vint ce que l’on appelle la logistique industrielle [77, 64]. Dans la littérature, plusieurs définitions ont été données à la chaîne logistique, dans ce qui suit nous présentons quelques-unes : Lee et Billington (1993) [67] : La chaîne logistique est « un réseau d’installations qui assure les fonctions d’approvisionnements en matières premières, de transformation de ces matières premières en composants puis en produits finis, et de distribution des produits finis aux clients » . Teigen et Barbuceanu (1996) [97] : « La chaîne logistique est un réseau de fournisseurs, d’entreprises, de dépôts, de centres de distribution et de détaillants, au travers desquels les matières premières sont acquises, transformées, et délivrées aux clients ». Mentzer et al. (2001) [73] : « Une chaîne logistique est un groupe d’au moins trois entités directement impliquées dans les flux amonts et avals de produits, de services, de finances et/ou d’informations, qui vont d’une source jusqu’au client ». Ganeshan et Harisson (1995) [41] : « Une chaîne logistique est le réseau des moyens de production et de distribution qui assurent les tâches d’approvisionnement en matières premières, la transformation de ces matières premières en produits semi finis et en produits finis, et la distribution de ces produits finis aux clients ». A partir de ces définitions nous pouvons constater que la chaîne logistique est un ensemble de maillons reliés entre eux et qui collaborent pour accomplir un travail bien déterminé. 1.2.2 Objectifs et enjeux Dans un environnement de plus en plus concurrentiel, les entreprises doivent être capables de livrer le bon produit dans la bonne quantité au bon endroit au bon moment et avec un coût minimal [64, 103]. Pour faire face à ce défi, l’entreprise doit adopter une bonne politique de gestion de sa chaîne logistique dont l’objectif principal est d’augmenter le gain global en maximisant les profits et en minimisant les coûts, y compris les coûts de fabrication, de transaction, de transport, de stockage, etc. Dans [67], les auteurs ont annoncé : « La bataille pour dominer le marché ne sera pas une bataille d’entreprises mais de chaînes logistiques ». En effet, l’importance des chaînes logistique provient de toutes les possibilités qu’elles offrent aux entreprises pour générer des gains supplémentaires ce qui permet aux entreprises de résister plus efficacement face aux pressions concurrentielles, et c’est pour cela que l’entreprise qui va réussir dans la gestion de sa chaîne logistique va dominer les autres. 1.2.3 Structure générale d’une chaîne logistique En prenant la définition de [41], la chaîne logistique a un ensemble de fonctions principales, qui consistent en l’achat des matières premières, la production, le stockage, la distribution et la 5 1.3. Le transport et la distribution dans la chaîne logistique vente des produits finis. Dans la figure 1.1 nous présentons un exemple d’une chaîne logistique en indiquant l’emplacement de chaque fonction dans la chaîne

Table des matières

Table des figures VI
Liste des tableaux VII
Introduction générale 1
1 Contexte de la thèse .
2 Problématiques et contributions
3 Organisation de la thèse .
Chapitre 1 Etat de l’art sur la chaîne logistique: localisation, routage et gestion
de stock
1.1 Introduction
1.2 La chaîne logistique .
1.2.1 Définitions .
1.2.2 Objectifs et enjeux
1.2.3 Structure générale d’une chaîne logistique
1.2.4 Niveaux de décisions dans une chaîne logistique .
1.3 Le transport et la distribution dans la chaîne logistique .
1.3.1 Problème de localisation .
1.3.1.1 Le problème de localisation sans contrainte de capacité (Uncapacitated Facility LocationProblem, UFLP) .
1.3.1.2 Modèle mathématique .
1.3.1.3 Les variantes du problème de localisation sans contrainte de capacité . .
1.3.2 Le problème de tournées de véhicules .
1.3.2.1 Le problème du voyageur de commerce .
1.3.2.2 Définition du problème VRP
1.3.2.3 Formulation mathématique .
1.3.2.4 Quelques variantes du VRP
1.3.3 La gestion de stock
1.3.4 Intégration entre les problèmes .
1.3.4.1 Problème de localisation-routage (Location Routing Problem
(LRP))
1.3.4.2 Problème de tournées avec gestion de stock (Inventory Routing
Problem (IRP)) .
1.4 Les outils pour l’optimisation de la chaîne logistique
1.4.1 Méthodes exactes
1.4.2 Méthodes approchées .
1.4.2.1 Heuristiques .
1.4.2.2 Metaheuristiques .
1.4.2.3 Algorithmes à performance garantie
1.4.2.4 Approches hybrides . .
1.5 Conclusion
Chapitre 2 Algorithme en deux phases pour le problème de localisation-routage
avec contrainte de capacité
2.1 Introduction .
2.2 Un état de l’art .
2.3 Modèle mathématique pour le CLRP
2.4 Méthodologie de la solution .
2.4.1 La première phase
2.4.1.1 L’Heuristique d’Insertion (HI) .
2.4.1.2 La recherche Tabou (TS)
2.4.2 La deuxième phase
2.4.2.1 Recuit simulé (Simulated Annealing (SA)) .
2.4.3 Algorithme complet (2-SH) .
2.5 Expérimentation .
2.5.1 Réglage des paramètres .
2.5.2 Le jeu de données
2.5.3 Résultats et discussion
2.6 Conclusion
Chapitre 3 Résolution de problème de routage avec gestion de stock à base de la
méthode GRASP 
3.1 Introduction .
3.2 Revue de la littérature
3.3 Définition du problème
3.3.1 Hypothèses
3.3.2 Notations
3.3.3 Le modèle mathématique
3.4 Méthodologie de solution .
3.4.1 Vue générale sur l’algorithme
3.4.2 Prétraitement
3.4.3 Solution initiale pour GBH .
3.4.4 Procédure gloutonne randomisée (GRP)
3.4.4.1 Notations
3.4.4.2 Les phases de GRP .
3.4.5 Recherche Tabou
3.4.5.1 Structure de voisinage
3.4.5.2 Le moteur de sélection .
3.4.5.3 La liste Tabou
3.4.6 La gestion de stock
3.5 Expérimentation
3.5.1 Réglage des paramètres .
3.5.2 Jeu de données .
3.5.3 Résultats et comparaison avec B&C
3.5.4 L’analyse du comportement de GBH
3.5.5 Les résultats de GBH sur les instances de MMIRP-SD
3.6 Conclusion
Chapitre 4 Algorithmes pour le problème de routage de navettes et de taxis
4.1 Introduction .
4.2 Définition du problème
4.2.1 Contraintes & fonction objectif
4.3 Méthodologie de la solution .
4.3.1 L’idée principale .
4.3.1.1 Difficultés .
4.3.1.2 L’approche proposée .
4.3.1.3 Motivation
4.3.1.4 Procédure de réparation .
4.3.2 Algorithmes pour le CTSSP
4.3.2.1 Recherche Tabou
4.3.2.2 GRASP .
4.4 Expérimentation
4.4.1 Réglage des paramètres
4.4.2 La procédure de génération de jeu de données
4.4.3 Les résultats de TS .
4.4.4 La comparaison entre TS, GRASP et GRASP-LP .
4.4.5 La méthode GRASP-LP sur les instances de VRP et d’OVRP .
4.4.5.1 La méthode GRASP-LP sur les instances de VRP
4.4.5.2 La méthode GRASP-LP sur les instances d’OVRP .
4.5 Conclusion
Conclusion générale
Bibliographie

Télécharger le rapport complet