La tâche de la livraison des marchandises

Dans cet article, nous verrons comment Flexport utilise les mathématiques et la science des données pour résoudre les problèmes de livraison et livrer les marchandises à temps au coût le plus bas possible.

Prenons un scénario spéculatif: le transitaire a dix départs et un vol de destination pour tout envoi. La seule décision à prendre est de savoir si chaque envoi doit être affecté à ce vol unique. Si nous n'affectons pas de charge spécifique au vol, supposons qu'il soit possible de la déplacer d'une autre manière.

Chaque envoi a un volume et un coût, et le vol est limité en volume. Vous pouvez le considérer comme un problème de sac à dos simplifié. Donc, il y a 1024-1 = 1023 solutions possibles (nous n'enverrions pas l'avion complètement vide).

Nous pourrions créer une feuille de calcul pour répertorier la solution entière et choisir la plus rentable. Mais que se passe-t-il si vous avez les mêmes dix départs, mais deux vols? Il s'agit de 59 049 solutions en seulement 10 expéditions.

Un grand transitaire a plus de dix départs et, bien sûr, plus de deux vols au choix, ce qui conduit à des milliards à des milliards de solutions possibles. Parmi eux, seuls des millions sont réalisables, ce qui signifie que la méthode traditionnelle du tableur peut trouver au moins une solution réalisable. Mais nous n'avons pas seulement besoin de solutions réalisables. Nous avons besoin des meilleures solutions optimales. Comment les trouver parmi d'innombrables possibilités? Une réponse consiste à utiliser la programmation entière.

La programmation entière est une sous-section de l'optimisation discrète, un domaine d'étude des opérations liées à la minimisation de certaines fonctions objectives soumises à des contraintes. Nous voulons minimiser les coûts totaux, à condition que les marchandises soient livrées à temps aux bons endroits, empilées dans ULD (Unit Load Device - un moyen d'emballage des marchandises). Nous nous efforçons de trouver une solution optimale, mais en pratique, nous ne pouvons parfois pas y parvenir. Dans ce cas, nous sommes satisfaits d'une bonne ou proche solution. Ici, nous nous limitons à un modèle simple dans lequel la solution optimale est réalisable.

La première étape pour résoudre ce problème consiste à se tourner vers la littérature. La communauté scientifique s'occupe du transit de fret depuis de nombreuses années. Nous avons trouvé plusieurs œuvres qui rappellent très bien notre problème. Nous avons repris bon nombre des concepts et de la notation suivants de ces travaux et remercions les auteurs pour leur contribution à ce domaine.

Nous commençons par définir la fonction objectif. Pour minimiser les coûts, nous devons comprendre le concept de poids standard. En bref, le poids standard est le poids minimum avec lequel le transitaire accepte de travailler, quel que soit le poids réellement offert. Nous avons le poids total, le poids standard et les probabilités de surcharge et, inversement, de poids insuffisant. Le poids standard multiplié par le facteur de sous-pondération est une sous-estimation, nous pouvons donc ignorer la sous-pondération et nous concentrer sur le coefficient de surcharge multiplié par la surcharge elle-même.

La fonction objective est de minimiser le coût total, défini comme le poids total de tous les biens attribués par ULD, multiplié par le facteur de charge. Par exemple, si ULD1 a 100 kilogrammes de congestion et que le taux de congestion pour ULD1 est de 4 $ par kilogramme, alors le coût total de ULD 1 sera de 400 $. Donc, nous avons besoin d'une notation pour être en surpoids et pour sa valeur.

Laisser être$$$y_j^E$  est le poids de ULD j supérieur à la norme et$$$c_j^E$  - facteur de coût pour le même ULD. Nous devons calculer$$$y_j^Ec_j^E$ pour tous$$$j$ . Si$$$j \in {1, 2, 3}$ , alors la fonction objectif sera$$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$ . Il s'effondre pour$$$\sum y_j^Ec_j^E$ . Nous voulons minimiser la valeur, donc notre objectif final:

$$

$$\text{min} \sum_{j} y^E_j c^E_j$$

La valeur pour $$$c_j^E$pas une valeur calculée. Ce paramètre est obtenu à partir d'une feuille de calcul ou d'une base de données. Mais$$$y_j^E$ nous avons défini comme le poids total de surcharge pour ULD$$$j$ , que nous pouvons calculer comme le poids total de toutes les fournitures attribuées par ULD (notons-le$$$y_j$ ), moins le poids standard de cet ULD. Le poids standard est spécifique au type ULD et est également un paramètre. Laisser être$$$U_j^P$  est le poids standard pour ULD$$$j$ en kilogrammes. Ensuite, le poids supplémentaire pour ULD$$$j$ défini comme$$$y_j^E=y_j-U_j^P$ .
Le poids total de l'ULD, bien sûr, dépend des poids attribués à l'ULD et de leur poids. Par conséquent, nous avons besoin d'une expression pour le calculer, y compris les détails mentionnés ci-dessus.

Il s'agit simplement de la somme des poids attribués par ULD. Comment indiquer qu'un lot de marchandises a été affecté à un ULD spécifique? Pour ce faire, nous n'avons pas besoin d'un paramètre, mais d'une variable de solution. Une variable de décision est quelque chose que le solveur peut contrôler tout en minimisant la fonction objectif.

Laissez le paramètre$$$g_i$ représente le poids brut de la charge$$$i$ en kilogrammes.
Par exemple,$$$g_4=500$ signifie que la cargaison 4 pèse 500 kilogrammes.

Laisser être$$$x_{i, j}$  est une variable de décision prenant la valeur 1, si expédition$$$i$ attribué ULD$$$j$ et$$$0$ sinon. Ainsi, lorsque nous voulons compter toutes les expéditions attribuées par ULD 3, nous pouvons parcourir toutes les variables$$$x_{i, j}$ , où$$$j=3$ . Si nous avions 4 envois et que les numéros d'envoi 1 et 3 étaient attribués à ULD 3, cela ressemblerait à ceci:

$$

$$x_{1,3} + x_{2,3} + x_{3,3} + x_{4,3} = 1 + 0 + 1 + 0 = 2$$

Mais nous avons besoin du poids total, pas de la quantité. Pour l'obtenir, vous pouvez simplement multiplier chaque variable de solution par un paramètre de poids. Puisque la variable de décision prend la valeur 0, si aucun poids ne lui est attribué, ce poids est réinitialisé et n'est pas inclus dans le total. Supposons que les poids des cargaisons de un à quatre soient 10, 50, 25 et 5. Le poids total dans ULD 3 sera alors:

$$

$$g_1x_{1,3} + g_2x_{2,3} + g_3x_{3,3} + g4x_{4,3} = (10)(1) + (50)(0) + (25)(1) + (5)(0) = 10 + 25 = 35$$

Écrivons ce calcul du poids total en général. Déterminer le poids total de l'ULD$$$j$ comme $$$y_j$. alors$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$, et $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. Nous pouvons réduire cela en utilisant la notation de sommation$$$y_1 = \sum g_ix_{i, 1}$ et $$$y_2=\sum g_ix_{i, 2}$. Puisque nous voulons que cela soit vrai pour tous les possibles$$$j$, nous utilisons le signe "pour tous": $$$\forall$. Cela nous donne la forme finale de notre limite de poids total:

$$

$$y_j=\sum_{i \in I}g_ix_{i,j} \forall j \in J$$

Poids supplémentaire

Maintenant que nous avons le poids total, nous pouvons appliquer notre formule pour la charge supplémentaire:

$$

$$y_j^E = y_j-U_j^P \quad \forall j \in J$$

Par exemple, si $$$y_1=1500$et et $$$U_1^P=1000$puis poids supplémentaire $$$y_1^E = 1500 - 1000 = 500$kilogrammes. Multipliez cela par le facteur de coût pour obtenir le résultat en dollars. À première vue, cela peut sembler suffisant, mais qu'en est-il du cas où le poids total de la cargaison entière pour ULD ne dépasse pas le poids standard? Dans ce cas, si nous utilisions la formule «en l'état», le poids de surcharge serait un nombre négatif. Par exemple, si le poids standard est de 1650 kilogrammes et que le poids total attribué est de 1000 kilogrammes, alors surcharge = 1000–1650 = -650. La fonction objectif multiplie ce nombre par un facteur de surcharge et nous obtenons un nombre négatif. Comme si le transporteur nous payait des frais de port inférieurs au coût d'un poids standard.

Voici ce que nous voulons vraiment:$$$\text{max}(y_j^E, 0)$.
C'est la même chose que de simplement mettre 0 pour une variable, ce qui est aussi simple que de créer une contrainte$$$y_j^E>=0$.

$$$y_j^E >= y_j - U_j^P \quad \forall j \in J$, $$$y_j^E >= 0 \quad \forall j \in J$

Nous avons donc implémenté la fonction max () dans la programmation mathématique: a = max (b, c), c'est-à-dire a> = b && a> = c. Regardons nos définitions.
Fonction objective:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: Rapport de surcharge ULD $$$j$
$$$y_j^E$: Surcharge ULD $$$j$; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: Poids standard ULD $$$j$
$$$g_i$: Poids brut à l'expédition $$$i$
$$$x_{i, j}$: variable de décision; $$$x_{i, j}=1$si expédition $$$i$attribué par ULD $$$j$, $$$0$autrement.
$$$y_j$: poids total de tous les envois désignés par ULD $$$j$; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Chaque charge doit voler

À ce stade, nous pourrions l'écrire en Python et l'envoyer au solveur. Si nous faisions cela, nous constaterions que le solveur n'a attribué aucune livraison à aucun vol, et nous pouvons rapidement comprendre pourquoi: la meilleure façon de minimiser la fonction objectif est de ne pas accumuler de coûts. Cela conduit à la restriction suivante: chaque lot doit être affecté à un certain ULD. Nous étendrons cela à chaque cargaison qui devrait être affectée à un et un seul ULD, bien qu'en réalité nous puissions diviser la cargaison en plusieurs ULD et même plusieurs vols.

Cela signifie que$$$x_{i, j}$ne peut être que 1 pour une seule valeur de $ j $. Par exemple, si nous envisageons l'expédition 13, alors$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. Nous voulons appliquer cette restriction pour chaque expédition.$$$i$ (que nous écrivons comme $$$\forall i\in I$), et nous pouvons réduire l'addition à l'aide de l'opérateur de sommation ($$$\sum$), notre dernière limite est donc:

$$

$$\sum_{j \in J} x_{i, j}=1\quad\forall i \in I$$

Compte tenu de cette limitation, le solveur commencera réellement à affecter des envois aux vols, mais il répartira simplement les envois entre tous les vols disponibles jusqu'à ce que les poids soient atteints. Le solveur placerait alors chaque envoi restant dans un ULD avec le moindre coût supplémentaire. À l'exclusion du volume ou du poids de cet ULD. Ainsi, les restrictions supplémentaires suivantes sont le volume et le poids.

Limites de volume et de poids

Décidons $$$U_j^M$comme charge utile maximale en kilogrammes de ULD $$$j$et $$$U_j^$comme volume maximum en mètres cubes ULD $$$j$. Décidons$$$v_i$et le volume en mètres cubes de cargaison $$$i$. Pour limiter le modèle à la capacité de charge maximale et au volume maximal, nous avons les conditions:

$$

$$y_j<=U_j^M \quad \forall j \in J$$

$$

$$\sum_{i \in I} x_{i,j} v_ i <= U_j^V \quad \forall j \in J$$

Un vétéran de l'industrie se rendra immédiatement compte que ce n'est pas vrai. Pourquoi? Parce que ces restrictions traitent la cargaison comme si elle pouvait être versée, comme de l'eau, dans n'importe quel volume. En réalité, les charges sont rigides ou ont d'autres restrictions, telles que l'empilement. 10 mètres cubes de fret ne peuvent pas être emballés dans un volume arbitraire égal exactement à 10 mètres cubes. Pour faire face à ces cas, vous devez résoudre le problème de l'emballage en conteneurs. Nous vérifions si certains volumes rentreront dans d'autres, mais cela dépasse le cadre de cet article.

Maintenant, le solveur attribue l'expédition ULD, en respectant le poids et le volume maximum tout en minimisant le coût total. Mais il y a un autre problème: nous n'avons rien dit sur la nomination des articles et le respect des dates de livraison. En fait, vous devez prendre en compte quatre horodatages lors de l'attribution d'un envoi: l'

heure à laquelle l'envoi est réellement prêt à être consolidé avec d'autres envois dans l'ULD et à charger sur le vol. Utilisons$$$Q_i^-$pour représenter l'heure à laquelle l'envoi est prêt $$$i$.
Le délai de déchargement des marchandises à destination est déconsolidé et disponible pour réception, en règle générale, depuis le terminal de fret. Utilisons $ Q_i ^ + $ pour représenter le délai de livraison$$$i$.
Heure à laquelle tout le fret doit être livré au terminal de fret pour être chargé sur le vol. Utilisons$$$T_j^ -$pour représenter le temps de détourage de la cargaison ULD $ j $.
Heure d'arrivée du vol: c'est l'heure à laquelle la cargaison sur le vol devient disponible à l'entrepôt de destination. Utilisons$$$T_j^+$ pour représenter l'heure d'arrivée du vol ULD $$$j$

Source et destination

Présentez un autre ensemble $$$J_i$, que nous définissons comme un ensemble de vols, dont la source et la destination coïncident avec le départ et la réception du fret $$$i$. En d'autres termes, si le départ 85 est de Hong Kong et destination à Londres, alors $ J_ {85} $ est l'ensemble de tous les ULD avec départ de Hong Kong et destination à Londres.
Maintenant, nous pouvons utiliser$$$j \in J_i$ pour obtenir un kit ULD qui correspond à la route commerciale maritime $$$i$ou nous pouvons utiliser $$$j \notin J_i$pour obtenir un ensemble d'ULD qui ne correspond pas. Pour interdire la liaison du fret à ULD, qui ne correspond pas à sa source et à sa destination, nous limitons simplement$$$x_{i,j} = 0$pour tous ces vols. La restriction est entièrement décrite comme suit:

$$

$$\sum_{j \notin J_i} x_{i,j}=0 \quad \forall i \in I$$

Heure de livraison

Lorsque vous travaillez avec des horodatages dans l'optimisation, il est pratique de présenter les moments nécessaires sous forme de temps Unix. Avantages de l'approche:

1. Enregistrement des dates sous forme de nombres.
2. Pas besoin de gérer les fuseaux horaires.
3. Le solveur utilise des comparaisons directes plus-moins.

Le vol doit arriver avant l'heure de livraison:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Veuillez noter que, tout comme pour la restriction ci-dessus sur le départ et la destination, nous avons indiqué que cette restriction ne s'applique qu'à l'ULD de l'ensemble $$$J_i$où $$$J_i$ est un ensemble d'ULD qui correspondent à l'envoi et à la réception de l'envoi $$$i$. C'est tout! Regardons l'ensemble du modèle.

Modèle complet

En vertu de ces restrictions, le solveur attribue les articles ULD de la manière la moins coûteuse, chaque cargaison étant livrée du bon point de départ à la bonne destination. Bien sûr, la cargaison est livrée à temps et sans surcharger les articles en volume ou en poids.

Paramètres

$$$I$: Un ensemble de tous les envois. Un envoi soumis$$$i$
$$$J$: Un ensemble de tous les ULD. L'ULD individuel est en minuscules$$$j$.
$$$J_i$: Un ensemble de tous les ULD correspondant à l'expéditeur et au destinataire $$$i$.
$$$g_i$: Poids brut à l'expédition $$$i$en kilogrammes.
$$$v_i$: Volume en mètres cubes d'expédition $$$i$
$$$c_j^E$: Rapport de surcharge ULD $$$j$en dollars américains par kilogramme
$$$U_j^M$: Capacité de poids maximale ULD $$$j$en kilogrammes
$$$U_j^V$: Puissance surround maximale ULD $$$j$en mètres cubes
$$$U_j^P$: Poids standard ULD $$$j$en kilogrammes

$$$T_j^-$: Délai de livraison autorisé au terminal ULD $$$j$.
$$$T_j^+$: Heure d'arrivée ULD $$$j$.
$$$Q_i^-$: Délai de livraison $$$i$. 
$$$Q_i^+$: Délai de livraison $$$i$.

Variables de décision et fonction objective:
$$$y_j$: Poids total ULD $$$j$
$$$y_j^E$: Surcharge ULD $$$j$en kilogrammes.
$$$x_{i,j}$: 1 si envoi $$$i$attribué par ULD $$$j$0 sinon.

Fonction cible

$$

$$\text{Minimize} \sum y_j^Ec_j^E$$

Limites

$$$y_j$ - poids total des envois sur ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
Le poids supplémentaire jE est max (0, yj-UjP):
$$$y_j^E >=y_j-U_j^P \quad \forall j \in J$
$$$y_j^E >=0 \quad \forall j \in J$
Chaque livraison doit être affectée exactement à 1 ULD: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ ne peut pas dépasser le poids maximum: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$ne peut pas dépasser la capacité maximale: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Prochaines étapes

Cet article décrit la programmation mathématique sous-jacente à l'objectif de la charge du vol. Mais écrire des mathématiques ne suffit pas. L'étape suivante consiste à implémenter le programme, probablement en AML, comme Pyomo, ou en utilisant sa propre API de solveur, par exemple, Python Gurobi API. Après cela, le développeur écrira un code pour transférer les paramètres de tous les départs et vols disponibles. Ensuite, l'instance de modèle est envoyée au solveur. Le solveur définit les valeurs des variables de décision de manière optimale. Ensuite, le développeur doit faire quelque chose avec les valeurs des variables de décision.