Optimisation des tournées de collecte de déchets en Apport Volontaire

Télécharger le fichier original (Mémoire de fin d’études)

Horizon multi périodique et gestion de stocks

Si les premiers problèmes de tournées de véhicules (Vehicle Routing Problem (VRP)) avaient pour ob-jectif de définir l’itinéraire optimal d’une flotte de véhicules sur un horizon mono périodique, il existe de nombreux travaux et variantes dits multi périodiques. On distingue principalement deux classes de pro-blèmes multi périodiques : les problèmes dits périodiques et les problèmes avec gestion de stocks.
Le problème de tournées périodiques (Periodic Vehicle Routing Problem (PVRP)) introduit en 1974 par Beltrami et Bodin [29] a pour objectif d’établir un ensemble de tournées de véhicules dont les clients sont susceptibles d’être collectés plusieurs fois sur l’horizon considéré. Dans l’exemple présenté par Beltrami et Bodin [29], une flotte de véhicules doit collecter un parc de conteneurs de déchets dont certains ont besoin d’être collectés trois fois par semaine avec deux jours d’écart entre chaque collecte. Il ne reste ainsi que deux motifs de planning possibles : {lundi,mercredi,vendredi} et {mardi,jeudi,samedi}. L’objectif de ce problème est de planifier les jours de collecte des conteneurs et les routes des véhicules associées avec un coût minimum (nombre de véhicules, distances). Les problèmes Periodic Vehicle Routing Problem (PVRP) sont souvent utilisés pour optimiser une planification de service régulier (collecte, livraison…) parmi un ensemble de motifs prédéterminés et répétables à l’infini. Une très grande partie des transports sont aujourd’hui organisés avec cette régularité, car elle simplifie l’organisation opérationnelle des entreprises et des usagers. On peut entre autres considérer le ramassage de déchets [29, 10, 148, 118] ou de lait [52] ainsi que le réapprovisionnement régulier de stocks [21, 85, 77, 84]. Une très large partie des travaux et applications liés aux problèmes d’optimisation de transport périodique a été consignée dans un récent état de l’art de Campbell et Wilson [43].
La seconde classe principale de problèmes multi périodiques regroupe les problèmes de tournées avec gestion de stocks (Inventory Routing Problem (IRP)), dont les clients / destinataires possèdent un stock de ressources évoluant sur les différentes périodes de l’horizon. Contrairement à notre problème, qui concerne la collecte de produits, la plupart des problèmes décrits dans la littérature concernent la livraison. Dans le problème classique d’IRP, le décideur (transporteur) intègre la planification des véhicules et la gestion du niveau de stock de l’ensemble des points à servir. Ce problème est généralement utilisé dans un contexte d’organisation Vendor-Managed Inventory où un fournisseur livre un ensemble de clients en s’assurant que leurs stocks ne soient jamais vides. Cette organisation permet aux clients de ne pas se soucier de leur stock de consommables et apporte au fournisseur un levier important d’économie en décidant du planning de livraison et des quantités à livrer. La première formulation de ce sujet par Bell et al. [26] traite de la livraison de gaz à destination d’entreprises et propose une résolution du problème grâce à une approche

ÉTAT DE L’ART ET CLASSIFICATION DU PROBLÈME

par relaxation lagrangienne. Deux politiques de réapprovisionnement sont principalement utilisées dans la littérature. La politique Maximum level policy (ML) laisse le choix de la quantité à livrer à chaque visite, mais ne permet pas de dépasser un niveau maximum de stock client. La politique dite Order-Up-to policy (OU) impose quant à elle de remplir l’intégralité du stock lors du passage d’un véhicule chez le client. La gestion du niveau minimum de remplissage d’un stock diffère également si nous interdisons le dépassement du seuil ou pénalisons financièrement la situation (avec ou sans rattrapage du stock négatif). Un classement de l’ensemble de ces caractéristiques est proposé par Coelho et al. [53] à l’occasion du trentenaire des premières études sur le sujet.
Une modélisation du problème d’Inventory Routing Problem (IRP) OU avec stocks non négatifs et un seul véhicule est proposé par Archetti et al. [14] ainsi qu’une résolution exacte par Branch & Cut (B&C). Dans cette version classique du problème, le dépôt (fournisseur) produit une quantité connue de matière à chaque période du planning et chaque nœud du réseau (fournisseur, clients) subit un coût de stockage proportionnel à la quantité de produits restant dans le stock à la fin de chaque période. Une formulation plus efficace est proposée par Solyah et Süral [144] permettant de résoudre optimalement des instances de soixante clients sur un horizon de trois périodes et quinze clients sur un horizon de douze périodes. Une version de ce problème avec plusieurs véhicules est étudiée par Coelho et Laporte [57, 56] ainsi que Adulyasak et al. [1] qui proposent également une méthode B&C.
De nombreuses approches heuristiques et métaheuristiques du problème d’IRP ont été publiées. Dror et al. [66, 67, 68] proposent et comparent de nombreuses méthodes de construction de solutions heuristiques en décomposant le problème en deux phases. Premièrement, un modèle d’affectation des clients sur les pé-riodes est utilisé, puis la résolution d’un problème de voyageur de commerce (Traveling Salesman Problem (TSP)) pour chaque période est effectué par un algorithme de type Clark & Wright (C&W) et recherche locale. Cette approche requiert que les clients ne soient affectés qu’une seule fois au cours de l’horizon. La séparation des décisions de planning et de routing est à la base des méthodes de clustering proposées par Anily et Federgruen [11] et Campbell et Savelsbergh [42], ainsi que Aghezzaf et al. [3, 128] avec une résolution par génération de colonnes. La plupart des méthodes de résolution avancées reposent sur des mé-thodes de recherche à voisinage. Bertazzi et al. [32] proposent un algorithme de recherche locale adaptée au problème d’IRP OU. Une approche hybride par recherche tabou est proposée par Archetti et al. [13] et testée sur des instances de deux cents clients sur un horizon de six périodes. Ribeiro et Lourenço [129] proposent une méthode de recherche itérative (Iterative Local Search (ILS)) pour résoudre un problème d’IRP dont les demandes sont déterministes et stochastiques. Un algorithme adaptatif à voisinages larges (Adaptive Large Neighborhood Search (ALNS)) est proposé par Coelho et al. [54, 55] pour le problème avec transbordement (possibilité de transférer des produits entre clients). Elbek et Wøhlk [70] décomposent un problème de collecte de déchets avec apports stochastiques dans les conteneurs et optimisent chaque période de l’horizon par une recherche à voisinage variable (Variable Neighborhood Search (VNS)). Geiger et Sevaux [78, 79] proposent une méthode de génération du front de Pareto du problème d’IRP bi objectif séparant les coûts de stockage et routing.
Les principales variantes des problèmes de routing mono périodiques possèdent leur équivalent avec gestion de stocks, comme les flottes de véhicules hétérogènes [47, 57, 123], des productions et demandes stochastiques [74, 82] ou plusieurs produits [146, 47]. Le problème de Production-Routing introduit par Chandra [45] et Fisher [46] permet de gérer le planning de production du fournisseur en plus de son stock. Cette variante étudiée entre-autres par Archetti et al. [15], Boudia et Prins [36] et Adulyasak et al. [2], permet de gérer de manière optimale le coût de stockage du fournisseur. Une variante intégrant un coût de production initial (setup-up costs) est introduite par Javid et al. [4, 5].
Pour finir, un ensemble de variantes de problèmes de tournées avec gestion des stocks maritimes (Ma-ritime Inventory Routing Problem (MIRP)) considère la production et consommation de ressources dans les stocks de manière continue. L’horizon temporel n’est pas discrétisé en périodes comme la version tradi-tionnelle de l’IRP du fait des temps de trajets des transporteurs maritimes (heures ou jours). La quantité de produits disponibles dans un nœud fournisseur ou restant chez un client dépendra du temps d’arrivée d’un véhicule (méthanier ou pétrolier par exemple). Une méthode de résolution du MIRP avec un seul produit est proposée par Christansen et al. [50, 51] et Christiansen [49]. Hwang [91] propose quant à lui de ré-soudre le problème multiproduit. Un état de l’art des différents sujets de recherche associés aux problèmes de transport maritime avec gestion de stocks est proposé par Papageorgiou et al. [121] qui regroupent les principales instances utilisées dans la littérature.

Tournées avec dépôts intermédiaires

Nous considérons dans les problèmes classiques de VRP et IRP un unique dépôt depuis lequel les vé-hicules commencent et finissent leurs tournées. Ces derniers possèdent une capacité initiale et ne peuvent réapprovisionner leur contenu pendant leur tournée. Les travaux de thèse de Huang [87] ainsi que les pa-piers joints de Bard et al. [22, 23] introduisent la notion de dépôts intermédiaires (Satellite Facilities (SF) également nommé dans la littérature Intermediate Facilities (IF)). Cet aspect permet aux véhicules de livrai-son de se réapprovisionner en cours de tournée dans un ou plusieurs nœuds du réseau avant de continuer à livrer les clients ou dans le cas d’une collecte, correspondant à notre problème, de vider son contenu dans des exutoires intermédiaires. Bard et al. proposent donc une méthode de B&C pour résoudre le problème de VRP-SF [22] avant d’intégrer cette approche dans une méthode de décomposition du problème de tour-nées avec gestion des stocks (IRP-SF) [23]. Ils intègrent entre autres dans leur approche des techniques de construction (Clark & Wright (C&W)) et une méthode appelée Greedy Randomized Adaptive Search Procedure (GRASP). La première étude du problème de PVRP-IF proposée par Angelelli et Speranza [10] repose sur une recherche tabou et est issue d’un problème de collecte de déchets. Sevilla et Simon [139] sont les premiers à intégrer le respect de fenêtres de temps avec dépôts intermédiaires (VRPIFTW) et proposent une heuristique de clustering améliorée par un système de colonie de fourmis. Les travaux de Sahoo et al. [136] ainsi que Kim et al. [98] à partir de 2005 décrivent le problème de Waste Collection VRP with Time Windows (WCVRPTW), dans lequel les véhicules de collecte (homogènes) peuvent vider leur contenu dans un exutoire intermédiaire, à l’image du problème étudié par Angelelli et Speranza [10]. Kim et al. utilisent un algorithme de recuit simulé (Simulated Annealing (SA)) sur des instances comprenant 102 à 2100 points de collecte. Benjamin et Beasley proposent au travers d’une thèse [9] et d’un article [30] de résoudre le pro-blème de WCVRPTW et des variantes intégrant des contraintes métier (pause réglementaire des chauffeurs) via de nombreuses procédures de construction et deux métaheuristiques basées sur une méthode recherche tabou et un algorithme VNS. Une approche ALNS est proposée par Buhrkal et al [40] tandis qu’un algo-rithme de clustering est étudié par Liu et He [107] avec pour conséquence une séparation nette des tournées en secteurs de ramassage. Cette approche est également explorée par Boukachour et al. [37] qui y associent une recherche par colonie de fourmis. Ombuki-Berman et al [135, 119] proposent de résoudre le problème de WCVRP-TW multi objectif en intégrant notamment la notion de consistance de tournées, permettant de répartir de manière homogène la charge de chaque véhicule et rendre les tournées plus disjointes (se croi-sant peu). Ils proposent une résolution par un algorithme génétique (Genetic Algorithm (GA)). Markov et al [109] intègrent enfin une flotte de véhicules hétérogènes dans ce problème et appliquent une solution par recherche locale pour résoudre ce problème très riche.
L’optimisation problèmes de tournées avec dépôts multiples (Multi-Depot Vehicle Routing Problem (MDVRP)) diffère de la notion de dépôts intermédiaires. En effet, le problème de MDVRP est composé de véhicules pouvant partir de dépôts différents. Dans la version classique du MDVRP, les véhicules doivent revenir à leur dépôt de départ. Une approche exacte est proposée par Laporte et al. [104] et des algorithmes heuristiques sont étudiés par Tillman et al. [149, 151, 152], Renaud et al. [131, 132] et Cordeau et al. [59]. Une variante de ce problème de livraison appelée Multi-Depot Vehicle Routing Problem with Inter-Depot Routes et étudiée par Crevier et al [60] intègre la notion de dépôts intermédiaires, mais ne fait pas de distinction entre les dépôts. Les véhicules peuvent donc partir et passer par n’importe quel dépôt, mais doivent toujours revenir à leur point de départ en fin de tournée. L’approche proposée génère un ensemble de routes par recherche recherche tabou puis sélectionne un sous-ensemble de ces routes par résolution mathématique d’un problème de partition.

Table des matières

1 Introduction
I Planification tactique d’un réseau de collecte de déchets
2 Description et résolution du problème d’optimisation des flux tactiques mono périodique
2.1 Présentation du problème d’optimisation des flux
2.1.1 Producteurs de déchets
2.1.2 Sites de transfert
2.1.3 Exutoires
2.1.4 Clients finaux
2.1.5 Activités et campagnes
2.1.6 Moyens de transport
2.1.7 Objectifs et décisions
2.2 État de l’art de la problématique
2.3 Modélisation du MC-MMFP-T
2.3.1 Notations
2.3.2 Multimodalité
2.3.3 Variables
2.3.4 Fonction objectif
2.3.5 Contraintes
2.4 Expérimentations et résultats
2.4.1 Résolution des instances générées
2.4.2 Résolution d’un cas réel
2.5 Développements logiciels
2.6 Conclusion
3 Description et résolution du problème tactique multi-périodique
3.1 Limites d’une approche mono périodique
3.1.1 Saisonnalité
3.1.2 Capacités de transfert et activités
3.2 Modélisation du problème
3.2.1 Présentation du problème
3.2.2 Modélisation
3.3 Expérimentations et résultats
3.4 Conclusions et perspectives
II Optimisation des tournées de collecte de déchets en Apport Volontaire
4 Description du problème de tournées déterministe
4.1 Description du problème
4.1.1 Périodes et horizon
4.1.2 Conteneurs
4.1.3 Produits et quantités
4.1.4 Dépôt
4.1.5 Exutoires
4.1.6 Véhicules
4.1.7 Objectifs et pénalités
4.1.8 Décisions et solution
4.2 État de l’art et classification du problème
4.2.1 Horizon multi périodique et gestion de stocks
4.2.2 Tournées avec dépôts intermédiaires
4.2.3 Flottes hétérogènes fixes
4.2.4 Fenêtres de temps multiples
4.2.5 Problèmes multiproduits
4.2.6 Classification du problème
4.3 Formulation mathématique
4.3.1 Notations
4.3.2 Variables
4.3.3 Fonction objectif
4.3.4 Contraintes
4.3.5 Amélioration du modèle
4.4 Conclusion
5 Résolution du problème de tournées déterministe
5.1 Approche ALNS globale
5.1.1 Choix de la méthode
5.1.2 Représentation d’une solution
5.1.3 Algorithme principal
5.1.4 Opérateurs de destruction
5.1.5 Opérateurs de réparation
5.1.6 Sélection adaptative des opérateurs
5.1.7 Acceptation de solution
5.1.8 Détection de convergence
5.2 Faisabilité d’une opération
5.3 Expérimentations et résultats
5.3.1 Résolution du VRPTW
5.3.2 Résolution de l’IRP
5.3.3 Résolution complète
5.3.4 Expérimentations en cas réel
5.4 Conclusion
6 Caractérisation du problème opérationnel stochastique
6.1 L’apport irrégulier en déchet
6.2 Étude de l’aléa de remplissage
6.3 Évolution du problème de tournées avec gestion des stocks
6.3.1 Espérance de coût de débordement d’un conteneur
6.3.2 Espérance de coût de débordement d’un véhicule
6.4 Conclusion
7 Résolution du problème opérationnel stochastique
7.1 État de l’art
7.2 Adaptation de l’approche ALNS
7.2.1 Débordement de véhicules
7.2.2 Débordement de conteneurs
7.3 Expérimentations
7.3.1 Simulation de cas réels
7.3.2 Simulation sur des aléas réduits
7.4 Conclusions et perspectives
8 Conclusions générales
Liste des Acronymes
Liste des tableaux
Table des figures
Glossaire
Bibliographie