Optimisation par essaims particulaires pour la logistique urbaine

Les activités économiques jouent un rôle indispensable pour le progrès de la société humaine. Les caractéristiques de base de ces activités sont la fabrication et la consommation de marchandises. Avec la mondialisation des échanges, l’origine et la destination des marchandises peuvent être très éloignées géographiquement. Par ailleurs, avec le développement du e-commerce, la livraison à domicile s’est beaucoup développée ces dernières années, impliquant de nombreux flux de marchandises en zones urbaines. Le choix d’un mode efficace pour transporter les marchandises de l’origine à la destination est donc devenu un sujet très important. Dans ce contexte, le transport en zone urbaine attire de plus en plus l’attention des chercheurs puisqu’il génère de nombreux problèmes et nuisances qui peuvent impacter le quotidien de chaque citoyen. Les enjeux qui en découlent sont par exemple réduire les coûts de transport, les émissions de gaz à effet de serre, la pollution sonore, ou encore la congestion.

Les travaux rapportés dans cette thèse étudient environ deux problématiques de planification représentatives du transport en zone urbaine. Pour la première, il s’agit de livrer divers clients à partir d’un ensemble fini de dépôts de marchandises. Des applications correspondantes peuvent être la collecte du lait ou la livraison des journaux. Dans la littérature, le problème scientifique associé est le Location Routing Problem (LRP), dans lequel le choix du dépôt et la planification des tournées sont déterminés pour satisfaire la demande des clients en respectant les contraintes imposées. Nos travaux s’intéressent en particulier à une variante capacitaire du LRP. Dans la seconde problématique, chaque demande de transport est caractérisée par un couple origine-destination qui lui est propre. Une application associée peut être le transport (collecte et livraison) du courrier dans une même ville. Dans la littérature, le problème scientifique associé s’appelle le Pickup and Delivery Problem (PDP). Dans cette thèse, une variante de PDP est étudiée en considérant l’aspect sélectif qui consiste à ne pas visiter tous les clients, ainsi que l’aspect collaboratif qui autorise que les véhicules transfèrent les marchandises au niveau d’un point de transfert. Pour ces différents cas, divers objectifs peuvent être envisagés, tels que minimiser la distance parcourue, ou minimiser le nombre de véhicules utilisés.

La logistique urbaine 

La chaîne logistique se définit comme un réseau d’installations qui regroupent les processus d’approvisionnement en composants, de fabrication, et de distribution des produits. Dans ce cadre, la logistique urbaine, appelée aussi la logistique du dernier kilomètre, s’occupe de livrer des produits aux clients finaux. Ce processus est souvent le plus coûteux dans la chaîne logistique. En effet, la circulation des marchandises est difficile et complexe dans l’espace urbain où une grande partie de la consommation est rassemblée. Cela nécessite un acheminement efficace des produits pour répondre à différents enjeux :

— économique : il s’agit d’optimiser le remplissage des camions afin d’utiliser le moins de véhicules possible ;
— environnemental : le but est de diminuer l’émission de gaz à effet serre (CO2) en minimisant la distance parcourue ;
— sociétal : on souhaite notamment limiter la congestion en planifiant des tournées pour éviter les heures de pointe ; en particulier, il faut tenir compte des problèmes d’accessibilité, en considérant les zones à accès restreint telles que les hyper centres, ainsi que les horaires de livraison (livraison des magasins la nuit ou tôt le matin).

De nombreuses variantes du CVRP sont étudiées dans la littérature, notamment le VRP with time windows (VRPTW) dans lequel une fenêtre temporelle de visite est associée à chaque client [Dror 1994] et [Ticha et al. 2017]. Un véhicule ne peut arriver après la date correspondant à la borne supérieure de cette fenêtre. S’il arrive avant la borne inférieure, il devra attendre l’ouverture du site. Une autre variante connue du VRP est le Vehicle Routing Problem with Backhauls (VRPB). Ce problème a été initialement introduit par [Deif & Bodin 1984]. L’ensemble des sites y est divisé en deux sous-ensembles, celui des clients pour lesquels une certaine quantité de marchandises est à livrer, et celui des fournisseurs pour lesquels une quantité donnée de marchandises est à collecter. Dans ce problème, toutes les livraisons doivent être effectuées avant toute collecte. Plusieurs études et synthèses ont été proposées sur ce type de variante (voir la synthèse récente de [Koç & Laporte 2018] pour la plus récente). En particulier, [Parragh et al. 2007] ont identifié 4 classes de problèmes  :
— Vehicle Routing Problem with Clustered Backhauls (VRPCB) [Bortfeldt et al. 2015], [Belloso et al. 2015] : un site ne peut être à la fois client et fournisseur. Par ailleurs, toutes les livraisons doivent être faites avant les collectes ;
— Vehicle Routing Problem with Mixed linehauls and Backhauls (VRPMB) [Belmecheri et al. 2009], [Pinto et al. 2015] : la différence avec la première classe est que les opérations de livraison et de collecte peuvent être mixées ;
— Vehicle Routing Problem with Simultaneous Delivery and Pickup (VRPSDP) [Dethloff 2002], [Chen & Wu 2006] : ici un site peut être à la fois client et fournisseur, mais il ne peut être visité qu’une seule fois, ce qui implique que la livraison et la collecte sur ce site doivent être faites en même temps ;
— et VRP with Divisible Delivery and Pickup (VRPDDP) [Salhi & Nagy 1999], [Nagy et al. 2013], [Gribkovskaia et al. 2001] : on relaxe la contrainte de passage unique aux sites présente dans la troisième classe de problèmes.

Pickup and Delivery Problem (PDP)

Dans un Pickup and Delivery Problem (PDP), les marchandises sont collectées chez leurs fournisseurs, et sont livrées chez leur clients. Le rôle (fournisseur ou client) peut être joué par n’importe quel site dans une tournée. Ce problème peut être vu comme une généralisation du VRP dans lequel les dépôts sont les fournisseurs et les sites sont leurs clients .

Le PDP a été initialement introduit sous le nom de GPDP (General Pickup and Delivery Problem) [Savelsbergh & Sol 1995]. Il a été étudié intensivement pour la raison que beaucoup d’applications réelles peuvent lui être associées : l’entretien des plates-formes pétrolières et gazières offshore [Gribkovskaia et al. 2006], la conception des routes de cargo [Brønmo et al. 2007], les services de transport pour les personnes en situation de handicap ou les personnes âgées [Madsen et al. 1995], [Borndörfer et al. 1999] et [Rekiek et al. 2006]. Pour plus d’informations, voir le livre [Toth & Vigo 2014] et les articles de synthèse [Savelsbergh & Sol 1995], [Parragh et al. 2007] et [Parragh et al. 2008]. Nous ne présentons pas ici le modèle mathématique du PDP car sa forme basique est identique à celle du VRP .

Dans le cas de transports directs entre fournisseurs et clients, deux sous-catégories peuvent être distinguées en fonction du type de demande :
— demande appairée : A une demande appairée, on associe un couple qui contient un point d’origine (fournisseur) et un point de destination (client). Autrement dit, les marchandises demandées par un client doivent strictement être approvisionnées par un unique fournisseur couplé ;
— demande non appairée : Au contraire du premier cas, la demande d’un client peut être approvisionnée par n’importe quel fournisseur (sous réserve qu’il puisse fournir les produits requis).

Tournées avec transferts versus multi-échelons

Le terme transfert se rencontre souvent dans le contexte du PDP, et le problème scientifique s’appelle le Pickup and Delivery Problem with Transfers (PDPT). Un transfert est un site intermédiaire, qui pourrait être un entrepôt, un commerce, un parking. Dans la littérature, le coût d’utilisation de ces sites de transfert n’est souvent pas pris en compte. Les bénéfices apportés par l’introduction de transferts s’accompagnent également d’une augmentation de la complexité du problème. Cette complexité est liée aux contraintes supplémentaires induites, de type contraintes de précédence, entre les dates de passage des véhicules qui s’échangent la marchandise en ces points. L’article de synthèse [Drexl 2012] recense ces contraintes de précédence dans des problèmes de tournées de véhicules. Une formulation formelle en MILP du PDPT a été initialement proposée par [Cortés et al. 2010].

Table des matières

Introduction générale
1 État de l’art
1.1 La logistique urbaine
1.2 Planification de tournées
1.2.1 Vehicule Routing Problem (VRP)
1.2.2 Pickup and Delivery Problem (PDP)
1.2.3 Tournées avec transferts versus multi-échelons
1.2.4 Location Routing Problem (LRP)
1.3 Méthodes de résolution
1.3.1 Méthodes exactes
1.3.2 Méthodes approchées
1.4 Résolution du LRP
1.5 Résolution du PDP
1.6 Conclusion
2 Résolution du CLRP
2.1 Introduction
2.2 Formulation du CLRP
2.3 Méthode approchée basée sur la PSO
2.3.1 Choix d’une méthode
2.3.2 Les principes des essaims particulaires (Particle Swarm Optimization)
2.3.3 Codage
2.3.4 Décodage
2.3.5 Recherche locale
2.3.6 Particle Swarm Optimization Hybridée
2.4 Expérimentations et résultats
2.4.1 Instances
2.4.2 Environnement de test
2.4.3 Justification des composantes de la méthode
2.4.4 Comparaison avec des méthodes de la littérature
2.5 Conclusion
3 Résolution d’un PDP sélectif
3.1 Introduction
3.2 Modélisation mathématique
3.3 Résolution par hybridation de méthodes approchées
3.3.1 Concepts basiques sur l’optimisation multi-objectifs
3.3.2 Optimisation par essaims particulaires multi-objectifs
3.3.3 Sélection d’un leader
3.3.4 Représentation d’une solution
3.3.5 Décodage d’une particule : construction des tournées
3.3.6 Amélioration par recherche locale
3.3.7 Particle Swarm Optimization Hybridée
3.4 Expérimentation et résultats
3.4.1 Instances
3.4.2 Paramétrage
3.4.3 Validation des recherches locales
3.4.4 Comparaison avec la littérature
3.5 Conclusion
4 Extension au PDP sélectif avec transferts
4.1 Introduction
4.2 Modélisation
4.2.1 Caractéristiques du SPDPT
4.3 Validation du modèle
4.3.1 Premier jeu d’instances
4.3.2 Approche lexicographique
4.3.3 Intérêt des transferts dans les problèmes sélectifs
4.3.4 Impacts du profit et du temps de service
4.4 Méthode approchée
4.4.1 Codage et décodage
4.4.2 HPSO et recherche locale
4.5 Évaluation de HPSO
4.5.1 Instances
4.5.2 Métriques
4.5.3 Paramétrage
4.6 Stratégies de choix d’un leader
4.7 Validation des recherches locales
4.8 Expérimentation
4.8.1 Résultats pour le premier jeu d’instances
4.8.2 Résultats pour le deuxième jeu d’instances
4.9 Conclusion
Conclusion générale
Bibliographie

Télécharger le rapport complet