Utilisateur:BiblioEILdrone/Brouillon

Nouvelles extensions du problème de tournées de véhicules pour la livraison du dernier kilomètre (livraison par drone)

Introduction[modifier | modifier le code]

Les nouvelles extensions du problème de tournées de véhicules pour la livraison du dernier kilomètre (livraison par drone) représentent l'avenir de la recherche en matière d'optimisation du dernier kilomètre. C'est pourquoi avec l'évolution des techniques et des moyens de livraison de nouveaux questionnements apparaissent autour du problème de tournées de véhicules.

Ce problème présente un aspect majeur dans la livraison du dernier kilomètre. Aujourd'hui ces problématiques sont au cœur des enjeux car ils ont des implications à la fois économiques mais aussi écologiques. De nombreuses solutions sont désormais à l'étude afin de solutionner ces problèmes majeurs. Les technologies ont évolué et l'une d'elle s’est particulièrement distingué, la livraison par drone. La livraison par drone peut aujourd'hui représenter une solution au problème de tournées de véhicules pour la livraison du dernier kilomètre afin d'acheminer un colis vers sa destination finale.

L’opportunité de l’utilisation des drones dans la livraison bouscule totalement la vision actuelle de la livraison, en effet les drones, contrairement aux transporteurs de colis habituels (camion, utilitaire, fourgon ...) ne se limitent pas à des routes mais à tout l'espace aérien, ce qui représente des parcours optimums et un gain de temps considérable. Cependant, les récents problèmes de législation autour des drones remettent en question leur utilisation. De plus, les drones actuels possèdent certaines limites telles que l'autonomie de leurs batteries, la distance qu'ils peuvent parcourir avant de perdre le signal du contrôleur qui les dirige et le poids qu'ils sont capable de déplacer. Tous ces facteurs représentent aujourd'hui les nouveaux piliers de de la livraison optimisée par drone.

Présentation du problème de tournées de véhicules[modifier | modifier le code]

Le problème de tournées de véhicule est une classe de problème de recherche opérationnelle et d'optimisation. Ce problème consiste à déterminer une séquence idéale de visite de clients ou de segments routiers pour construire les itinéraires des véhicules. L'objectif de ce problème est de minimiser le coup de livraison des colis. Ces livraisons sont limitées par différents contraintes :

contraintes de capacité : Les véhicules ont une capacité limitée (quantité, taille, poids), ce qui amène des problèmes de bin packing ;
contraintes liées aux ressources et aux clients : disponibilité, localisation ;
tournées de véhicules avec fenêtre de temps : Pour chaque client on impose une fenêtre de temps dans laquelle la livraison doit être effectuée ;
tournées de véhicules avec collecte et livraison : Un certain nombre de marchandises doivent être déplacées de sites de collecte vers des sites de livraisons.

La solution de ce problème peut vite devenir laborieux lorsque plusieurs des contraintes précédentes s'accumulent, par exemple, les contraintes de capacité et les tournées avec collecte et livraison interagissent et la capacité du véhicule doit être prise en compte lors de la création de la tournée.

Les applications du problème de tournées de véhicules sont les suivantes :

livraison de particuliers
livraison de professionnels
tournées de soins
tournées d'affichage
réparation ou maintenance de matériel
tournée de commerciaux

Modélisation du problème[modifier | modifier le code]

Un ensemble de véhicule d’une certaine capacité, au départ d’un dépôt doit assurer un parcours entre plusieurs client ou villes ayant requis la livraison d’une certaine quantité de colis. Une tournée est définie par l’ensemble des clients qu’un véhicule doit visiter. Chaque tournée doit commencer et finir au dépôt, et un client ne doit être visité qu’une seule fois.

Synthèse des nouvelles extensions du VRP ayant comme domaine d'application la logistique du dernier kilomètre[modifier | modifier le code]

Classification des extensions selon l'objectif et les contraintes métiers[modifier | modifier le code]

Synthèse des principales méthodes de résolution (exactes / approchées)[modifier | modifier le code]

Définitions[modifier | modifier le code]

Les méthodes exactes, appelées aussi méthodes complètes, permettent de trouver la solution optimale d'un problème d'optimisation en explorant exhaustivement l'ensemble des solutions. Cependant, le temps de calcul a tendance à augmenter si la taille du problème à résoudre augmente elle aussi.

Les méthodes approchées permettent de traiter des problèmes de taille importantes mais elles sont incomplètes : elles permettent de trouver des bonnes solutions mais ne garantissent en aucun cas l'optimalité de celles-ci. Les méthodes approchées sont composées de heuristiques et de métaheuristiques. Une heuristique est une méthode de calcul mathématique qui fournit une solution rapidement, elle est généralement définie pour un seul problème. Une métaheuristique est une heuristique évoluée car elle peut être généralisée à plusieurs problèmes.

I.1. Modélisation du problème[modifier | modifier le code]

Comme affirmé dans l’introduction, le problème est une extension du problème du voyageur de commerce. Dans le problème du voyageur de commerce avec drones, on considère un ensemble de lot de consommateurs et chacun d’entre eux doit être servi exactement une fois, soit par un camion, soit par un drone. Autant, le camion et le drone doivent partir et revenir à un unique dépôt une seule fois.

Pour chaque tour du camion, il peut effectuer plusieurs sorties du drone. Chaque sortie du drone se compose de trois nœuds : le nœud de lancement, le nœud représenté par le drone et le nœud de retour comme suit :

· Le nœud de lancement peut être un dépôt ou un emplacement client (nœud).

· Le nœud du drone est un emplacement client desservi par un drone.

· Après avoir desservi le client, le drone aura soit ce qu’on appelle un « rendez-vous » avec le camion chez le prochain emplacement du client, soit il retourne au dépôt. Les deux véhicules doivent s’attendre au point de rendez-vous afin d’effectuer ce que l’on appelle un « mouvement de synchronisation »

Une fois en vol, le drone doit aller vers un client et retourner vers le camion ou vers le dépôt dans la limite de son niveau de batterie. Un tuple est sélectionné si et seulement si cette limite d’endurance est respectée. Il y a aussi le temps nécessaire au chauffeur du camion pour lancer et récupérer le drone. L’objectif étant de minimiser le temps de trajet du camion ainsi que du drone. A partir de l’hypothèse où on a seulement une tournée avec les camions (figure 1), la deuxième figure montre le scénario où les clients sont trop loin du dépôt et en dehors de l’endurance du drone.

D’autre part, la troisième figure illustre le cas où des clients sont dans la portée du drone, cependant, le drone peut démarrer directement du dépôt, déposer le colis chez un des clients et aller vers le point de rendez-vous pendant que le camion continue à livrer les autres clients. A la fin, le drone, après avoir été lancé à partir du camion et servi un client, peut directement revenir au dépôt comme son endurance lui permet de le faire.

Une solution du problème du voyageur de commerce avec drones est un assemblage de petits trajets, dont chacun peut ou peut ne pas contenir une livraison par drones. Dans le cas où on peut utiliser le drone, le trajet contient non seulement une sortie de drone mais aussi une liste de clients que le camion doit servir durant le temps où le drone effectue sa sortie pour livrer le client.

I.1. Tournée d’un drone[modifier | modifier le code]

Une tournée de drone est définie comme : ({i,j,k} , {O}) où :

· {i,j,k} est une sortie de drone : un tuple représentant trois points : le point « i « de lancement (point de départ), le point « j » de livraison du client et finalement le point de rendez-vous « k »

· O est une liste de nœuds que le camion peut emprunter entre i et k (pendant que le drone effectue une livraison). Cette liste peut être vide, cela signifiant que le camion et le drone effectueront un trajet en « triangle »

I.1. Approche « cluster-first »[modifier | modifier le code]

L’approche cluster-first est une méthode de résolution utilisant la programmation linéaire en nombre entiers. Soit N = {1,…,n} une liste de clients à livrer. Soit 0 et n+1 un seul et même dépôt physique. La liste de tous les nœuds du graphe est représenté par V = {0,…,n+1}.

Soit Ω la liste de tous les chemins possibles que peut prendre le drone au sein de V. On rappelle que l’on sélectionne un tuple si et seulement si la capacité de la batterie du drone le permet.

Soit u_ir appartenant à {0,1} égal à 1 si un client i appartenant à N apparaît dans {O} de tournée de drone r appartenant à Ω dans la solution finale. Pareillement, d_ir appartenant à {0,1} est égal à 1 si le client i appartenant à N est un nœud de drone de tournée r appartenant à Ω. De plus, t_ir appartenant à {0,1} est égal à 1 si le client i appartenant à V apparaît soit au point de lancement i ou au point de rendez-vous k d’une tournée de drone r appartenant à Ω.

Nous avons aussi la variable de décision λ_r appartenant à {0,1} si la tournée de drone r appartenant à Ω est sélectionné dans la solution finale. Soit p_r le profit que l’on obtient si on choisit la tournée r.

A partir des notations, paramètres et variables ci-dessus, nous pouvons obtenir la formulation en PLNE suivante :

· Max Σ p_r λ_r (1)

· Σ u_ir λ_r <= 1 pour tout i appartenant à N (2)

· Σ t_ir λ_r <= 2 pour tout i appartenant à V (3)

· Σ d_ir λ_r <= 1 pour tout i appartenant à N (4)

· Σ u_ir λ_r + Σ t_ir λ_r + Σ d_ir λ_r <= 1 pour tout i appartenant à N (5)

L’objectif est de maximiser le profit du choix d’une tournée de drone parmi Ω. La contrainte (2) assure que chaque nœud apparaît entre chaque tournée de drone au plus une fois. De la même manière, la contrainte (4) garantit que chaque nœud apparaisse comme un nœud de drone au plus une fois. La contrainte (2) affirme que chaque nœud peut apparaître comme un nœud terminal (i ou k dans la tournée de drone) au plus deux fois. Par exemple on a deux tournées de drones {0,1,5} at {5,2,4}, on ne peut pas avoir le nœud 5 qui apparaît comme premier ou dernier nœud d’autres tournées. Finalement, la contrainte (5) couple u_ir, t_ir, d_ir, pour assurer que chaque nœud peut seulement avoir un seul rôle (nœud terminal ou nœud de drone intermédiaire).

I.1. Méthodes Heuristiques[modifier | modifier le code]

I.1.a. Algorithme 1 : Heuristique Cluster First – Route Second[modifier | modifier le code]

Donnée : Instance

Résultat : Solution

· TournéeDrones <- RésoudrePLNE(Instance) ;

· EntréePVC <- ConstruireEntréePVC(TournéeDrones,Instance) ;

· SolutionPVC <- RésoudrePVC(EntréePVC) ;

· Solution <- CréerSolutionAPartirdePVC(SolutionPVC,Instance) ;

· Retourner Solution ;

I.1.b. Algorithme 2 : ConstruireEntréePVC[modifier | modifier le code]

Données : TournéeDrone, Instance

Résultat : fichierDeSortie

· NoeudsRestants <- Tous les nœuds qui ne sont pas dans la tournée du drone ;

· NoeudsPVC <- NoeudsRestants ;

· Pour Chaque tournée de drone faire :

o Définir un nœud n qui rassemble tous les nœuds de i à k du camion ;

o Distance de n à partir de tout nœud <- (distance de i vers ce nœud + distance de i à k allant à travers tous les nœuds dans O) ;

· Générer un fichierDeSortie

· Retourner fichierDeSortie

I.1.c. Algorithme 3 : Heuristique Cluster First – Route Second[modifier | modifier le code]

Donnée : Entrée

Résultat : Solution

· SolutionPVC <- RésoudrePVC(Entrée) ;

· TournéeDrones <- RésoudrePLNEAvecSolutionPVC(SolutionPVC) ;

· EntréePVC <- ConstruireEntréePVC(TournéeDrones,Instance) ;

· SolutionPVC <- RésoudrePVC(EntréePVC) ;

· Solution <- CréerSolutionAPartirDePVC(SolutionPVC,Instance) ;

· Retourner Solution ;

I.2. Méthodes métaheuristiques[modifier | modifier le code]

I.2.a. Recuit simulé[modifier | modifier le code]

L’algorithme du recuit simulé est une métaheuristique itérative basée sur l’algorithme de Monte Carlo conçu dans les années 80 et a été maintes et maintes utilisé fois afin de trouver des solutions au problème du voyageur de commerce ainsi que d’autres problèmes d’optimisations. Cette méthode vient du constat que le refroidissement naturel de certains métaux ne permet pas aux atomes de se placer dans la configuration la plus solide. La configuration la plus stable est atteinte en maîtrisant le refroidissement et en le ralentissant par un apport de chaleur externe ou bien par isolation.

Chaque permutation de nœuds dans une tournée du problème du voyageur de commerce est une configuration du système statistique, où la longueur d’un aller-retour représente son énergie dans cette configuration particulière. Par contre les grands systèmes à une température donnée s’approchent spontanément d’un état d’équilibre avec une énergie minimale par rapport à la température actuelle. Le système démarre à une température très élevée. En simulant son changement de configuration et en diminuant progressivement la température, il est possible de trouver des progressions des valeurs d’énergies moyennes nettement plus faibles, ce qui permet au système de réduire progressivement la consommation d’énergie.

Cela signifie qu’il est possible de parcourir l’espace des solutions en générant des solutions voisines de la solution actuelle. Celles-ci sont générées au moyen de différents types de mouvements effectués sur le chemin actuel.

Afin d’accepter de nouvelles solutions, on fonctionne de la manière suivante : Alors qu’un meilleur circuit est toujours accepté, un pire est accepté en fonction de probabilités sur la différence de qualité et un paramètre de température.

On fait diminuer la température selon un programme de refroidissement au fur et à mesure que l’algorithme progresse, afin de modifier la nature de la recherche, permettant d’abord d’accepter plusieurs mauvaises solutions et petit à petit commencer à accepter les meilleures solutions. De cette façon l’algorithme échappe au problème du « maximum local » et va converger vers le vrai maximum.

L’algorithme se présente comme suit :

· Générer une solution initiale s0

· Soit une solution s = s* = s0

· Choisir aléatoirement une solution à partir de s pour avoir s_nouveau

· Si la probabilité d’acceptation de s_nouveau est plus grande qu’un nombre généré aléatoirement, on choisit s = s_nouveau

· Si la fonction objective en prenant la nouvelle solution est plus petite que celle avec s*, on met à jour s* = s_nouveau

· Mettre à jour la température

· Si le critère d’arrêt n’est pas atteint, recommencer à partir de l’étape 3

Le critère d’arrêt de l’algorithme peut être défini de plusieurs manières, des exemples incluent le fait d’atteindre un nombre fixe d’itérations, dépasser un certain temps, ne pas améliorer la fonction objective (ne pas trouver de meilleure solution) pour un certain nombre d’itérations, etc…

I.2.b. Algorithme de colonies de fourmis[modifier | modifier le code]

L’algorithme de colonie de fourmis est une métaheuristique itérative qui s’inspire du comportement des fourmis en quête de nourriture pour la colonie. Ce genre de fourmis déposent un type spécial de phéromone sur le terrain pour indiquer les chemins favorables à suivre par d’autres fourmis. La métaheuristique maintient cette idée pour résoudre les problèmes d’optimisation combinatoire. Pour le problème du voyageur de commerce, cet algorithme se traduit par un certain nombre de solutions au problème généré par des fourmis artificiels (ou des agents) se déplaçant sur le graphe de l’instance. Chaque bord du graphe a une valeur liée de phéromone qui peut être lue et modifiée par les fourmis. A chaque itération, un nombre différent de fourmis construisent une solution chacune en marchant de nœud en nœud sans visiter les nœuds précédemment visités. La sélection du nœud pour construire la solution est régie par un mécanisme stochastique guidé par la phéromone : Plus il y a de phéromone présente dans l’un des bords sortant de ce sommet et allant vers un sommet non-visité, plus il est probable que la fourmi va traverser ce bord. A la fin de chaque itération, les valeurs de phéromone sur les bords sont mises à jour afin de favoriser les futures fourmis à construire de nouvelles solutions similaires aux meilleures précédemment construit.

Pour le problème du voyageur de commerce avec drones, l’approche avec l’algorithme de colonies de fourmis voudrait que l’on ait deux types de phéromones, une pour le camion et une autre pour les trajets du drone :

· Initialiser les paramètres de la structure : nombre de fourmis par itération, position initiale des fourmis dans les nœuds et les valeurs initiales des phéromones

· Générer les nouvelles solutions.

· Améliorer les solutions trouvées (optimales)

· Augmenter la valeur des phéromones associées à des solutions vraisemblables et diminuer celles qui ne le sont pas

· Si la condition d’arrêt n’est pas atteinte, revenir à l’étape 2.

Références[modifier | modifier le code]

(en) Boualem Rabta, Christian Wankmüller et Gerald Reiner, A drone fleet model for last-mile distribution in disaster relief operations, Austria, 2018.
(en) Chase C. Murray et Amanda G. Chu, The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery, USA, 2015.
(en) Emine Es Yurek et H. Cenk Ozmutlu, A decomposition-based iterative optimization algorithm for traveling salesman problem with drone, Turkey, 2018.
(en) Yulia Vakulenkoa, Poja Shamsb, Daniel Hellströma et Klas Hjorta, Service innovation in e-commerce last mile delivery: Mapping the e-customer journey, Sweden.
(en) Jarotwan KOIWANIT, Analysis of environmental impacts of drone delivery on an online shopping system, Thailand, 2018.
(en) Youngmin Choi et Paul M. Schonfeld, Ph.D. (Corresponding Author), Optimization of Multi-package Drone Deliveries Considering Battery Capacity, USA, 2016.
(en) OPTIMIZATION OF DRONE-ASSISTED PARCEL DELIVERY, 2016.
(en) Nils Boysen, Dirk Briskorn, Stefan Fedtke et Stefan Schwerdfeger, Drone delivery from trucks: Drone scheduling for given truck routes, 2018.
(en) Minh Hoang Ha, Modélisation et résolution de problèmes généralisés de tournées de véhicules, Nantes, 2012.
(en) Seyed Mahdi Shavarani, Mazyar Ghadiri Nejad, Farhood Rismanchian et Gokhan Izbirak, Application of hierarchical facility location problem for optimization of a drone delivery system: a case study of Amazon prime air in the city of San Francisco, London, 2017.
(en) James F. Campbell, Juan Zhang et Don Sweeney, Strategic Design for Delivery with Trucks and Drones, St. Louis, 2017