Resources
Article

How to get started: Das Last-Mile-Delivery-Problem

Quantagonia macht alte Software fit für Quantencomputer. Würde Frank Thelen investieren?

Jul 9, 2024
5
min read
Read full article

Hands-On: Mixed Integer Linear Programming für Last-Mile Delivery

Bei der Lieferung von Arzneimitteln auf dem „letzten Kilometer“ zum Anwender (engl.: Last-Mile) geht es um den Transport von Medikamenten und medizinischen Geräten von einem zentralen Lager zu Apotheken, Kliniken, Krankenhäusern und anderen Einrichtungen. Dieser Prozess muss äußerst zuverlässig und effizient sein, um auf unvorhergesehene Notfälle und Nachfragen reagieren zu können.

Was, wenn Drohnen die Notfallversorgung schneller und in schwer erreichbaren Gebieten ermöglichen?

Durch die drohnen-gestützte Anlieferung eines Defibrillators an einen Patienten mit Herzstillstand in Schweden konnten beispielsweise erste Schocks verabreicht werden, bevor die Rettungssanitäter eintrafen. Ein anderes aktuelles Beispiel ist die Verteilung von Blutkonserven per Drohne in Großstädten und im ländlichen Raum. Schneller Zugang zu lebensrettender Ausrüstung ist essenziell bei der medizinischen Notversorgung. Eine optimierte Routenführung führt zu einer effizienten Nutzung der verfügbaren Ressourcen.

Wie hilft gemischt-ganzzahlige Optimierung bei der Logistik?

Bei der Logistik werden regelmäßig gemischt-ganzzahlige Optimierungsprobleme (wie CVRP) gelöst, um effiziente Transportwege zu finden. Diese Probleme gehören zum Bereich des Operations Research. Dabei geht es um die Optimierung der Nutzlast für jedes Fahrzeug und die Bestimmung der kürzesten Routen mit mehreren Lieferadressen. Ziel ist es, die Abläufe mit optimalen Auslieferungszeiten zu finden.

Dafür vereint man zwei bekannte ganzzahlige lineare Optimierungsprobleme:

  • Nutzlastkapazität (Knapsack-Problem)
  • Zeitliche Beschränkungen (Traveling Salesman Problem)

Der Algorithmus optimiert die Nutzlast und die Lieferreihenfolge, um eine effiziente und koordinierte Zustellung der Pakete sicherzustellen. Dafür wird die sogenannte MILP Modellierung herangezogen.

Dieses Tutorial soll Logistikern, OR-Analysten und Unternehmensberatern bei der Anwendung von Quantagonia’s HybridSolver helfen.

How to: Implementierung von Mixed Integer Linear Programming in Python

Das Aufsetzen eines Optimierungsproblems in Python folgt einer strukturierten Herangehensweise.

  1. Definition der relevanten Parameter (z.B. Lieferorte)
  2. Definition der Zielfunktion (z.B. Minimierung der Gesamtentfernung)
  3. Definition der Nebenbedingungen (z.B. Fahrzeugkapazität)
  4. Modell berechnen / optimieren
  5. Verarbeitung der Resultate

Diese Struktur sorgt für Klarheit und macht es einfacher, den Code zu verstehen und später zu ändern.

Beispiel Code-Implementierung: Optimierung von Drohnen-gestützter Logistik in München

Für das Beispiel werden zufällige Standorte innerhalb Münchens generiert. Jede Drohne kann maximal drei Gegenstände mitnehmen, wobei jeder Standort einen davon benötigt. Ziel ist es, alle Lieferungen so schnell wie möglich abzuwickeln (Minimierung der Zielfunktion, in diesem Fall die zurückgelegte Gesamtstrecke). Sobald die Drohne alle drei Gegenstände ausgeliefert hat, muss sie für die erneute Beladung zurück zum Lagerhaus.

Es folgt die Definition der Nebenbedingungen und Einschränkungen:

  • Erfüllung der Nachfrage an jedem Standort
  • Kapazitätsgrenzen der Drohne dürfen nicht überschritten werden
  • Keine doppelten Besuche innerhalb einer Tour
  • Eliminierung von Subtouren und Umwegen

Das gesamte Modell wird an die HybridSolver-API übergeben, um die effizientesten Routen zu berechnen.

Die Lösung fasst ähnliche Orte in einem gemeinsamen Flug zusammen. Die Routenberechnung kann jedoch mit zunehmender Drohnenanzahl, variablen Nutzlasten und verschiedenen Lagerhäusern zunehmend komplex werden. Probier es aus. Hier ist die code-Implementierung des Tutorials.

Anwendung von Knapsack and Traveling Salesman Problemen

Die Kombination aus dem Knapsack-Problem und dem Traveling-Salesman-Problem (TSP) lässt sich auf die Last-Mile-Lieferung und die Logistikbranche anwenden. Das Capacitated Vehicle Routing Problem (CVRP) ermittelt effiziente Multi-Stopp-Navigation unter Berücksichtigung der Transportkapazität. Hier sind einige Anwendungsfälle, die davon profitieren können:

Ridesharing (Car Pooling)

Optimale Routenführung für Ridesharing-Plattformen kann durch CVRP für die Koordination von einem Fahrer mit mehreren Fahrgästen erzielt werden. Durch die richtige Reihenfolge der Stopps und Fahrzeugauslastung können Ridesharing-Anbieter die Wartezeiten reduzieren, den Treibstoffverbrauch und die Nutzer-Zufriedenheit verbessern.

Koordination von Außendienst und Ersthelfern

Optimierte Planung und Zeitpläne für Außendienste und Ersthelfer, wie Instandhalter, Reparateure und Notfallsanitätern: CVRP helfen mit besserer Einsatzabdeckung und Reaktionszeit bei Notfällen. Dadurch wird sichergestellt, dass mehr Einsätze an einem Tag bei höherem Kundenerfolg ausgeführt werden können.

Lean Logistic

Schlanke Logistik für E-Commerce und Logistikanbieter können mit CVRP ihre Lieferrouten optimieren, um effektiv größere Volumen zu bearbeiten. Durch das Lösen vom Knapsack-Problem können Lieferwagen optimal beladen werden und mit TSP die beste Routenführung bestimmt werden. Dabei werden gleichzeitig Kosten und Lieferzeiten optimiert.

Öffentlicher Nah- & Fernverkehr

Verbesserte Fahrpläne für öffentliche Verkehrsmittel: CVRP für die Optimierung der Bus- und Zug-Fahrpläne. Durch die effiziente Nutzung der Verkehrsmittel werden Wartezeiten und Zuverlässigkeit für die Fahrgäste verbessert.

Warenhauslogistik

In automatisierten Warenhäusern können Roboter dank optimierter Auslastung alle Sammelstellen schneller bedienen. Die Kombination aus Knapsack und TSP gestaltet den Prozessablauf so effizient wie möglich.

Die oben genannten Beispiele können implementiert werden, indem man der Struktur im Colab-Notebook folgt. Wir unterstützen gerne bei der Modellformulierung für Anwendungsfälle: help@quantagonia.com. Plane effiziente und resiliente Last-Mile-Lieferungen mit dem HybridSolver.

Referenzen

1 https://www.nejm.org/doi/10.1056/NEJMc2200833

2 https://www.thelancet.com/journals/langlo/article/PIIS2214-109X(22)00048-1/fulltext

Quantagonia Application Logo

Want to get entangled or stay up to date?

Let's push the boundaries of technology and create a quantum-powered future.