Die Aufgabe der Lieferung von Waren

In diesem Beitrag werden wir sehen, wie Flexport mithilfe von Mathematik und Datenwissenschaft Lieferprobleme löst und Waren pünktlich zu möglichst geringen Kosten liefert.

Stellen Sie sich ein spekulatives Szenario vor: Der Spediteur hat zehn Abflüge und einen Zielflug für jede Sendung. Die einzige Entscheidung, die getroffen werden muss, ist, ob jede Sendung diesem einzelnen Flug zugeordnet werden soll. Wenn wir dem Flug keine bestimmte Last zuweisen, nehmen wir an, dass es möglich ist, ihn auf andere Weise zu bewegen.

Jede Sendung hat Volumen und Kosten, und das Flugvolumen ist begrenzt. Sie können sich das als vereinfachtes Rucksackproblem vorstellen. Es gibt also 1024-1 = 1023 mögliche Lösungen (wir würden das Flugzeug nicht vollständig leer senden).

Wir könnten eine Tabelle erstellen, um die gesamte Lösung aufzulisten und die rentabelste auszuwählen. Aber was ist, wenn Sie die gleichen zehn Abflüge haben, aber zwei Flüge? Dies sind 59.049 Lösungen in nur 10 Sendungen.

Ein großer Spediteur hat mehr als zehn Abflüge und natürlich mehr als zwei Flüge zur Auswahl, was zu Billionen bis Billionen möglicher Lösungen führt. Unter diesen sind nur Millionen machbar, was bedeutet, dass die traditionelle Tabellenkalkulationsmethode mindestens eine praktikable Lösung finden kann. Wir brauchen aber nicht nur machbare Lösungen. Wir brauchen die besten und optimalen Lösungen. Wie findet man sie unter unzähligen Möglichkeiten? Eine Antwort ist die Verwendung der Ganzzahlprogrammierung.

Die ganzzahlige Programmierung ist ein Unterabschnitt der diskreten Optimierung, ein Bereich der Untersuchung von Operationen im Zusammenhang mit der Minimierung einiger objektiver Funktionen, die Einschränkungen unterliegen. Wir wollen die Gesamtkosten minimieren, vorausgesetzt, die Waren werden pünktlich an die richtigen Orte geliefert, gestapelt in ULD (Unit Load Device - ein Mittel zum Verpacken von Waren). Wir streben nach einer optimalen Lösung, aber in der Praxis können wir sie manchmal nicht erreichen. In diesem Fall sind wir mit einer guten oder engen Lösung zufrieden. Hier beschränken wir uns auf ein einfaches Modell, in dem die optimale Lösung erreichbar ist.

Der erste Schritt zur Lösung dieses Problems besteht darin, sich der Literatur zuzuwenden. Die wissenschaftliche Gemeinschaft befasst sich seit vielen Jahren mit der Spedition. Wir haben mehrere Werke gefunden, die sehr an unser Problem erinnern. Wir haben viele der folgenden Konzepte und Notationen aus diesen Werken übernommen und danken den Autoren für ihren Beitrag zu diesem Bereich.

Wir beginnen mit der Definition der Zielfunktion. Um die Kosten zu minimieren, müssen wir das Konzept des Standardgewichts verstehen. Kurz gesagt, das Standardgewicht ist das Mindestgewicht, mit dem der Spediteur arbeiten möchte, unabhängig davon, welches Gewicht tatsächlich angeboten wird. Wir haben Gesamtgewicht, Standardgewicht und Chancen für Überlastungen und umgekehrt Untergewicht. Das Standardgewicht mal das Untergewicht ist eine Unterschätzung, daher können wir das Untergewicht ignorieren und uns auf den Überlastungsfaktor multipliziert mit der Überlast selbst konzentrieren.

Die Zielfunktion besteht darin, die Gesamtkosten zu minimieren, definiert als das Gesamtgewicht aller von ULD zugewiesenen Waren, multipliziert mit dem Auslastungsfaktor. Wenn ULD1 beispielsweise 100 kg Überlastung aufweist und die Überlastungsrate für ULD1 4 USD pro Kilogramm beträgt, betragen die Gesamtkosten für ULD 1 400 USD. Wir brauchen also eine Notation, um übergewichtig zu sein und um ihren Wert zu ermitteln.

Lassen$$$y_j^E$  - Gewicht ULD j über Standard und $$$c_j^E$ - Kostenfaktor für dieselbe ULD. Wir müssen rechnen$$$y_j^Ec_j^E$ für alle $$$j$. Wenn$$$j \in {1, 2, 3}$dann wird die Zielfunktion sein $$$y_1^Ec_1^E+y_2^Ec_2^E+y_3^Ec_3^E$. Es bricht zusammen$$$\sum y_j^Ec_j^E$. Wir wollen den Wert minimieren, also unser Endziel:

$$

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

Wert für $$$c_j^E$kein berechneter Wert. Dieser Parameter wird aus einer Tabelle oder Datenbank abgerufen. Aber$$$y_j^E$ Wir haben das Gesamtüberlastgewicht für ULD definiert $$$j$, die wir als Gesamtgewicht aller von ULD zugewiesenen Lieferungen berechnen können (bezeichnen Sie es $$$y_j$) abzüglich des Standardgewichts dieser ULD. Das Standardgewicht ist spezifisch für den ULD-Typ und auch ein Parameter. Lassen$$$U_j^P$  ist das Standardgewicht für ULD $$$j$in Kilogramm. Dann die Menge an zusätzlichem Gewicht für ULD$$$j$ definiert als $$$y_j^E=y_j-U_j^P$.
Das Gesamtgewicht der ULD hängt natürlich davon ab, welche Gewichte der ULD zugewiesen sind und wie schwer sie sind. Daher benötigen wir einen Ausdruck, um ihn zu berechnen, einschließlich der oben genannten Details.

Dies ist einfach die Summe der von ULD zugewiesenen Gewichte. Wie kann angegeben werden, dass eine Warencharge einer bestimmten ULD zugeordnet wurde? Dazu benötigen wir keinen Parameter, sondern eine Lösungsvariable. Eine Entscheidungsvariable kann der Löser steuern und gleichzeitig die Zielfunktion minimieren.

Lassen Sie den Parameter$$$g_i$ repräsentiert das Bruttogewicht $$$i$in Kilogramm.
Zum Beispiel,$$$g_4=500$bedeutet, dass eine Ladung von 4 500 Kilogramm wiegt.

Lassen$$$x_{i, j}$  - eine Entscheidungsvariable mit dem Wert 1 beim Versand $$$i$von ULD zugewiesen $$$j$, und $$$0$sonst. Wenn wir also alle von ULD 3 zugewiesenen Sendungen zählen möchten, können wir alle Variablen durchlaufen$$$x_{i, j}$wo $$$j=3$. Wenn wir 4 Sendungen hätten und die Sendungsnummern 1 und 3 ULD 3 zugewiesen würden, würde dies folgendermaßen aussehen:

$$

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

Aber wir brauchen das Gesamtgewicht, nicht die Menge. Um es zu erhalten, können Sie einfach jede Lösungsvariable mit einem Gewichtungsparameter multiplizieren. Da die Entscheidungsvariable den Wert 0 annimmt, wird dieses Gewicht zurückgesetzt und nicht in die Summe einbezogen, wenn ihr kein Gewicht zugewiesen ist. Angenommen, die Gewichte für die Ladungen eins bis vier betragen 10, 50, 25 und 5. Dann beträgt das Gesamtgewicht in ULD 3:

$$

$$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$$

Schreiben wir diese Berechnung des Gesamtgewichts im Allgemeinen. Bestimmen Sie das Gesamtgewicht der ULD$$$j$ wie $$$y_j$. Dann$$$y_1=g_1x_{1,1}+g_2x_{2,1}+ … + g_ix_{i, 1}$, und $$$y_2=g_1x_{1,2}+g_2x_{2,2} +…+ g_ix_{i, 2}$. Wir können dies mithilfe der Summationsnotation reduzieren$$$y_1 = \sum g_ix_{i, 1}$ und $$$y_2=\sum g_ix_{i, 2}$. Da wir wollen, dass dies für alle möglichen gilt$$$j$verwenden wir das Zeichen "für alle": $$$\forall$. Dies gibt uns die endgültige Form unserer Gesamtgewichtsgrenze:

$$

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

Extra Gewicht

Nachdem wir das Gesamtgewicht haben, können wir unsere Formel für die zusätzliche Last anwenden:

$$

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

Zum Beispiel wenn $$$y_1=1500$und und $$$U_1^P=1000$dann zusätzliches Gewicht $$$y_1^E = 1500 - 1000 = 500$Kilogramm. Multiplizieren Sie dies mit dem Kostenfaktor, um das Ergebnis in Dollar zu erhalten. Auf den ersten Blick mag dies ausreichend erscheinen, aber wie sieht es aus, wenn das Gesamtgewicht der gesamten Ladung für ULD das Standardgewicht nicht überschreitet? In diesem Fall wäre das Überlastgewicht eine negative Zahl, wenn wir die Ist-Formel verwenden würden. Wenn beispielsweise das Standardgewicht 1650 Kilogramm und das zugewiesene Gesamtgewicht 1000 Kilogramm beträgt, ist Überlast = 1000–1650 = -650. Die Zielfunktion multipliziert diese Zahl mit einem Faktor für Überlastungen und wir erhalten eine negative Zahl. Als ob der Spediteur uns für den Versand weniger als die Kosten eines Standardgewichts bezahlt hätte.

Folgendes wollen wir wirklich:$$$\text{max}(y_j^E, 0)$.
Dies entspricht dem Setzen von 0 für eine Variable, was so einfach ist wie das Erstellen einer Einschränkung$$$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$

Also haben wir die Funktion max () in die mathematische Programmierung implementiert: a = max (b, c), dh a> = b && a> = c. Schauen wir uns unsere Definitionen an.
Zielfunktion:$$$\text{min} \sum_{j} y^E_j c^E_j$
$$$c_j^E$: ULD-Überlastungsverhältnis $$$j$
$$$y_j^E$: ULD-Überlastung $$$j$;; $$$y_j^ = y_j - U_j^P$
$$$U_j^P$: Standardgewicht ULD $$$j$
$$$g_i$: Brutto-Versandgewicht $$$i$
$$$x_{i, j}$: Entscheidungsvariable; $$$x_{i, j}=1$wenn Versand $$$i$von ULD zugewiesen $$$j$, $$$0$sonst.
$$$y_j$: Gesamtgewicht aller von ULD bezeichneten Sendungen $$$j$;; $$$y_j=\sum_{i \in I}g_ix_{i,j} \quad \forall j \in J$

Jede Ladung muss fliegen

Zu diesem Zeitpunkt könnten wir dies in Python schreiben und an den Solver senden. Wenn wir dies tun würden, würden wir feststellen, dass der Löser jedem Flug keine Lieferungen zugewiesen hat, und wir können schnell verstehen, warum: Der beste Weg, die Zielfunktion zu minimieren, besteht darin, keine Kosten zu akkumulieren. Dies führt zu folgender Einschränkung: Jede Charge muss einer ULD zugeordnet werden. Wir werden dies auf jede Fracht ausweiten, die nur einer ULD zugeordnet werden soll, obwohl wir die Fracht in Wirklichkeit in mehrere ULD und sogar mehrere Flüge aufteilen können.

Es bedeutet das$$$x_{i, j}$kann nur 1 für einen einzelnen Wert von $ j $ sein. Wenn wir zum Beispiel den Versand von 13 in Betracht ziehen, dann$$$x_{13,1}+x_{13,2}+ x_{13,3}+ … + x_{13, J}=1$. Wir möchten diese Einschränkung für jede Sendung anwenden.$$$i$ (was wir schreiben als $$$\forall i\in I$), und wir können die Addition mit dem Summationsoperator reduzieren ($$$\sum$), also ist unsere letzte Einschränkung:

$$

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

Angesichts dieser Einschränkung beginnt der Löser tatsächlich, Sendungen Flügen zuzuweisen, verteilt die Sendungen jedoch einfach auf alle verfügbaren Flüge, bis die Gewichte erreicht sind. Der Löser würde dann jede verbleibende Sendung mit den geringsten zusätzlichen Kosten in eine ULD legen. Ohne das Volumen oder Gewicht dieser ULD. Die folgenden zusätzlichen Einschränkungen betreffen also Volumen und Gewicht.

Volumen- und Gewichtsbeschränkungen

Lass uns entscheiden $$$U_j^M$als maximale Nutzlast in Kilogramm ULD $$$j$und $$$U_j^$als maximales Volumen in Kubikmetern ULD $$$j$. Lass uns entscheiden$$$v_i$und das Volumen in Kubikmetern Fracht $$$i$. Um das Modell auf die maximale Tragfähigkeit und das maximale Volumen zu beschränken, haben wir folgende Bedingungen:

$$

$$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$$

Ein Branchenveteran wird sofort erkennen, dass dies nicht der Fall ist. Warum? Weil diese Einschränkungen die Ladung so behandeln, als ob sie wie Wasser in ein beliebiges Volumen gegossen werden könnte. In der Realität sind Lasten starr oder haben andere Einschränkungen, wie z. B. Stapeln. 10 Kubikmeter Fracht können nicht in einem beliebigen Volumen von genau 10 Kubikmetern verpackt werden. Um diese Fälle zu bewältigen, müssen Sie das Problem der Verpackung in Behältern lösen. Wir prüfen, ob bestimmte Volumes in andere passen, dies geht jedoch über den Rahmen dieses Artikels hinaus.

Jetzt weist der Löser die Sendung ULD zu, wobei das maximale Gewicht und Volumen berücksichtigt und gleichzeitig die Gesamtkosten minimiert werden. Es gibt aber noch ein anderes Problem: Wir haben nichts über die Ernennung der Artikel und die Einhaltung der Liefertermine gesagt. Tatsächlich gibt es vier Zeitstempel, die Sie beim Zuweisen einer Sendung berücksichtigen müssen: Die

Zeit, zu der die Sendung tatsächlich bereit ist, sich mit anderen Sendungen in der ULD zu konsolidieren und den Flug zu laden. Lassen Sie uns verwenden$$$Q_i^-$um die Zeit darzustellen, zu der die Sendung fertig ist $$$i$.
Der Zeitpunkt, bis zu dem die Waren am Bestimmungsort entladen werden müssen, wird entkonsolidiert und steht in der Regel am Frachtterminal zur Verfügung. Verwenden wir $ Q_i ^ + $, um die Lieferfrist darzustellen$$$i$.
Die Zeit, bis zu der die gesamte Fracht zum Laden auf den Flug zum Frachtterminal geliefert werden muss. Lassen Sie uns verwenden$$$T_j^ -$um die Schnittzeit der Ladung ULD $ j $ darzustellen.
Flugankunftszeit: Dies ist die Zeit, bis zu der die Fracht auf dem Flug im Ziellager verfügbar ist. Lassen Sie uns verwenden$$$T_j^+$ um die Ankunftszeit des ULD-Fluges darzustellen $$$j$

Quelle und Ziel

Stellen Sie einen weiteren Satz vor $$$J_i$, die wir als eine Reihe von Flügen definieren, deren Quelle und Ziel mit dem Abflug und dem Empfang von Fracht zusammenfallen $$$i$. Mit anderen Worten, wenn Abflug 85 von Hongkong und Ziel in London ist, dann ist $ J_ {85} $ die Menge aller ULDs mit Abflug von Hongkong und Ziel in London.
Jetzt können wir verwenden$$$j \in J_i$ um ein ULD-Kit zu erhalten, das der Versandhandelsroute entspricht $$$i$oder wir können verwenden $$$j \notin J_i$um einen Satz von ULD zu erhalten, der nicht übereinstimmt. Um die Bindung von Fracht an ULD zu verbieten, die nicht ihrer Quelle und ihrem Bestimmungsort entspricht, beschränken wir einfach$$$x_{i,j} = 0$für alle diese Flüge. Die Einschränkung wird vollständig wie folgt beschrieben:

$$

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

Lieferzeit

Wenn Sie mit Zeitstempeln in der Optimierung arbeiten, ist es praktisch, die erforderlichen Momente als Unix-Zeit darzustellen. Vorteile des Ansatzes:

1. Speichern von Daten als Zahlen.
2. Keine Notwendigkeit, Zeitzonen zu behandeln.
3. Der Solver verwendet direkte Vergleiche mit mehr oder weniger.

Der Flug muss vor der Lieferzeit ankommen:
$$$\sum_{j \in J_i}T_j^+x_{i,j}<=Q_i^+ \quad \forall i \in I \quad$
Bitte beachten Sie, dass wir genau wie bei der oben genannten Einschränkung für Abflug und Ziel angegeben haben, dass diese Einschränkung nur für die ULD im Set gilt $$$J_i$wo $$$J_i$ ist eine Reihe von ULDs, die dem Senden und Empfangen von Sendungen entsprechen $$$i$. Das ist alles! Schauen wir uns das ganze Modell an.

Volles Modell

Unter solchen Einschränkungen weist der Löser die ULD-Artikel auf die kostengünstigste Weise zu, wobei jede Ladung vom richtigen Abflugort zum richtigen Ziel geliefert wird. Natürlich wird die Ladung pünktlich und ohne Überladung der Artikel nach Volumen oder Gewicht geliefert.

Parameter

$$$I$: Ein Satz aller Sendungen. Eine Sendung eingereicht$$$i$
$$$J$: Ein Satz aller ULD. Einzelne ULD ist Kleinbuchstaben$$$j$.
$$$J_i$: Ein Satz aller ULDs, die mit Sender und Empfänger übereinstimmen $$$i$.
$$$g_i$: Versand Bruttogewicht $$$i$in Kilogramm.
$$$v_i$: Volumen in Kubikmetern Versand $$$i$
$$$c_j^E$: ULD-Überlastungsverhältnis $$$j$in US-Dollar pro Kilogramm
$$$U_j^M$: Maximale Gewichtskapazität ULD $$$j$in Kilogramm
$$$U_j^V$: ULD Maximale Umgebungsleistung $$$j$in Kubikmetern
$$$U_j^P$: Standardgewicht ULD $$$j$in Kilogramm

$$$T_j^-$: Zulässige Lieferzeit zum ULD-Terminal $$$j$.
$$$T_j^+$: ULD Ankunftszeit $$$j$.
$$$Q_i^-$: Versandbereitschaftszeit $$$i$. 
$$$Q_i^+$: Liefertermin $$$i$.

Entscheidungsvariablen und Zielfunktion:
$$$y_j$: ULD Gesamtgewicht $$$j$
$$$y_j^E$: ULD-Überlastung $$$j$in Kilogramm.
$$$x_{i,j}$: 1 beim Senden $$$i$von ULD zugewiesen $$$j$0 sonst.

Zielfunktion

$$

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

Einschränkungen

$$$y_j$ - Gesamtgewicht der Sendungen auf ULD $ j $: $$$y_j=\sum_{i \in I} g_ix_{i,j} \quad \forall j \in J$
Das zusätzliche Gewicht jE beträgt 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$
Jede Lieferung muss genau 1 ULD zugeordnet sein: $$$\sum_{j \in J} x_{i,j}=1 \quad \forall i \in I$.
ULD$$$j$ Maximales Gewicht darf nicht überschritten werden: $$$y_j<=U_j^M \quad \forall j \in J$
ULD $$$j$darf die maximale Kapazität nicht überschreiten: $$$\sum_{i \in I}x_{i,j}v_i <= U_j^V \quad \forall j \in J$

Weitere Schritte

Dieser Artikel beschreibt die mathematische Programmierung, die dem Zweck der Flugbelastung zugrunde liegt. Aber nur Mathe zu schreiben ist nicht genug. Der nächste Schritt besteht darin, das Programm, wahrscheinlich in AML, wie Pyomo, zu implementieren oder eine eigene Solver-API zu verwenden, beispielsweise die Python Gurobi-API. Danach schreibt der Entwickler einen Code, um die Parameter aller verfügbaren Abflüge und Flüge zu übertragen. Dann wird die Modellinstanz an den Solver gesendet. Der Solver legt die Werte der Entscheidungsvariablen optimal fest. Dann muss der Entwickler etwas mit den Werten der Entscheidungsvariablen tun.