Livraison du dernier kilomètre à partir de plusieurs dépôts en Python

Modélisation mathématique, solution et visualisation à l'aide de PuLP et VeRoViz

Avec la croissance rapide des achats en ligne, les entreprises sont confrontées à des demandes toujours croissantes de livraison rapide et à faible coût. Livraison au dernier kilomètre fait référence à l'étape finale de la chaîne d'approvisionnement, où les colis sont livrés depuis un dépôt jusqu'à la porte du client. Il s’agit d’un problème tactique complexe qui implique de déterminer conjointement comment attribuer les colis aux camions et comment acheminer les camions vers les clients. C'est aussi un problème très coûteux, avec estimations récentes plaçant la livraison du dernier kilomètre à 53 % du coût total d’expédition. Cela souligne la nécessité de générer des plans de livraison efficaces.

La forme classique de ce problème implique un dépôt unique (généralement un entrepôt) à partir duquel tous les camions sont chargés et expédiés pour leurs livraisons. Une version plus complexe implique plusieurs dépôts proches les uns des autres, par exemple lorsque les chaînes de vente au détail livrent à partir de magasins. Dans ce cas, un client donné peut être desservi par plus d’un dépôt, l’entreprise doit donc également déterminer quels dépôts expédieront à quels clients. Parfois, aucun dépôt ne disposera de tous les articles de la commande d'un client, ce qui nécessitera que la commande soit répartie entre plusieurs dépôts.

Ci-dessous, nous verrons comment modéliser et résoudre ce problème multi-dépôt plus complexe en utilisant programmation entière (PI). Ce problème présente les aspects suivants :

1. Il existe un ensemble de camions, de dépôts, de clients et de produits.
2. Chaque client a commandé une quantité spécifique de chaque produit, et chaque dépôt dispose d'une certaine quantité de chaque produit disponible.
3. Chaque camion est basé dans exactement un dépôt (ce qui signifie que son itinéraire commence et se termine toujours à sa base). De plus, les camions ne doivent pas nécessairement être identiques : chaque camion peut avoir une capacité de volume et un coût par kilomètre différents.

L'objectif est de déterminer simultanément 1) les produits à expédier de chaque dépôt à chaque client, 2) comment attribuer les colis aux camions, et 3) comment acheminer chaque camion vers ses clients, le tout de manière à atteindre le total le plus bas. frais de livraison possibles.

Nous allons implémenter et résoudre un modèle IP avec Pulpe et utilise VerRoViz pour visualiser les itinéraires des camions. Pour commencer, nous importons les bibliothèques nécessaires :

Un exemple de scénario

Une entreprise de meubles possède deux dépôts dans la région de Fredericksburg, en Virginie, avec huit commandes clients à livrer. Les données et la carte sont présentées ci-dessous. Remarque: La nœudsArray variable a été préparée avec le Outil d'esquisse VeRoViz, qui permet la création graphique de données de localisation et les exportations vers Python.

Modéliser le problème

Bien qu’il existe plusieurs façons d’aborder ce problème, nous allons construire et résoudre un modèle de programmation en nombres entiers. Cela donne une spécification mathématique précise du problème et permet de résoudre de manière optimale des instances de problème de taille modérée à l'aide de solveurs disponibles dans le commerce (bien que cela dépasse notre portée, les instances plus grandes ne peuvent souvent pas être résolues rapidement avec des solveurs disponibles dans le commerce et nécessitent des solutions spéciales). -algorithmes de solution conçus). Nous commençons par les entrées du modèle :

Ensuite, nous définissons nos variables de décision :

Enfin, nous définissons le modèle d'optimisation :

Dans ce modèle, la fonction objectif (1) que l'on souhaite minimiser est simplement la somme de tous les frais de déplacement engagés. Les contraintes de (2) garantissent que pour chaque emplacement, si un camion particulier arrive à l'emplacement, alors le camion part également. Les contraintes de (3) garantissent qu'aucun camion ne quitte un dépôt qui n'est pas sa base. Les contraintes de (4) garantissent que chaque client obtient tous les produits qu'il a commandés. Les contraintes de (5) garantissent qu'aucun sous-circuit ne se produit sur aucun itinéraire. Puisqu’un groupe d’emplacements formant un circuit aura le même nombre d’arêtes que de nœuds, nous évitons que cela se produise dans chaque sous-ensemble non vide possible de clients pour chaque camion. Les contraintes de (6) garantissent que pour chaque dépôt et produit, le nombre total d'unités de produit chargées sur des camions et expédiées aux clients depuis ce dépôt ne dépasse pas la disponibilité au dépôt. Les contraintes de (7) garantissent qu'aucune unité d'un produit n'est chargée sur un camion et expédiée à un client à moins que le camion ne rende visite au client. Les contraintes de (8) garantissent que pour chaque camion, le volume total de produits chargés à bord ne dépasse pas sa capacité. Enfin, les contraintes de (9-10) précisent les domaines des variables de décision (binaires pour les variables de décision). x variables ; entier non négatif pour le u variables).

Pour plus de facilité et de réutilisabilité, nous allons créer une fonction Python pour construire des instances de ce modèle pour des données d'entrée spécifiques en utilisant Pulpe:

Résoudre l'exemple de problème de scénario

Maintenant que le modèle est formulé, nous pouvons l’utiliser pour trouver une solution optimale pour notre scénario. Ci-dessous, nous utilisons le solveur CBC inclus avec Pulpe. Cela peut prendre 15 à 45 secondes pour trouver une solution optimale. Si vous avez accès au plus puissant CPLEX solveur, vous pouvez utiliser les lignes commentées à la place pour obtenir une solution beaucoup plus rapidement.

L'exécution de ceci nous donne le message de sortie suivant :

Extraction et visualisation des itinéraires des camions

Nous devons maintenant extraire les itinéraires des camions à partir des variables de décision dans le modèle résolu. Pour chaque camion, nous souhaitons connaître ses arrêts et quels produits livrer à chaque arrêt. Pour obtenir ces informations, nous devons passer au crible les variables de décision non nulles.

Ceci construit les itinéraires de camions suivants :

A noter que le client C1 reçoit la visite de deux camions (T2 et T4) — d'où une commande fractionnée. Compte tenu des demandes simultanées des clients et des ressources disponibles, cela s’avère être une décision optimale. Cela peut également être nécessaire lorsque, par exemple, une commande contient un ensemble d'articles introuvables dans un seul dépôt.

Visualiser les itinéraires des camions

Comme dernière étape, nous utilisons VerRoViz pour créer une belle visualisation des itinéraires des camions :

Conclusion

Bien que de nombreuses variantes de ce problème soient possibles, cet exemple illustre comment nous pouvons modéliser et résoudre un tel problème en utilisant la programmation en nombres entiers. Il montre également comment Python peut être utilisé pour regrouper des composants puissants tels que Pulpe ainsi que le VerRoViz pour créer rapidement des systèmes d’aide à la décision utiles. Bonne livraison !

Le code source peut être consulté dans un cahier ici ou téléchargé ici.

Livraison du dernier kilomètre à partir de plusieurs dépôts en Python republié à partir de la source https://towardsdatascience.com/last-mile-delivery-from-multiple-depots-in-python-26c4325407b4?source=rss—-7f60cf5620c9—4 via https:// versdatascience.com/feed

<!–

->