GOR Blog

Kollaborative Tourenplanung mit dynamischer Kundenannahme und Überbuchungen

von Dr. Yannick Scherr (Gewinner YRA 2024)

In der Logistikbranche ist das unmittelbare Antworten auf Kundenanfragen entscheidend für die Wettbewerbsfähigkeit. Die dynamische Annahme von Aufträgen unter Unsicherheit sorgt allerdings dafür, dass die Ressourcen nicht optimal genutzt werden. Dies motiviert insbesondere kleinere Logistikdienstleister miteinander zu kooperieren, um Transportaufträge zu tauschen. In diesem Kontext betrachten wir ein Pickup-and-Delivery-Problem mit dynamischer Kundenannahme und horizontaler Kollaboration mittels kombinatorischer Auktion.

Wir modellieren das Optimierungsproblem der einzelnen Dienstleister als Markov-Entscheidungsprozess (MEP), der alle Phasen umfasst: von der dynamischen Kundenannahme über die Auswahl von Aufträgen für die Auktion, das Bieten auf Auftragsbündel in der Auktion, bis hin zur abschließenden Tourenplanung. Die gewinnmaximierende Zielfunktion umfasst den Umsatz aus angenommenen Kundenanfragen abzüglich der Kosten, die bei der Zustellung in Touren z.B. am nächsten Tag anfallen. In der dazwischenliegenden Auktion können Kosten eingespart werden.

Optimale gemeinsame Tourenplanung von Lieferfahrzeugen und Lastenfahrrädern

von Asst. Prof. Philine Schiewe (Gewinnerin YRA 2024)

Paketlieferungen sind für viele schon lange ein Teil des Alltags und die damit verbundenen Lieferfahrzeuge sind aus dem heutigen Stadtbild kaum noch wegzudenken. Durch das hohe Paketvolumen trägt die Zustellung von Paketen auf der letzten Meile allerdings erheblich zu Staus und Umweltbelastungen in städtischen Bereichen bei. Daher ist es notwendig, traditionelle, dieselbetriebene Lieferfahrzeuge durch umweltfreundlichere Alternativen zu ergänzen. In den letzten Jahren sind dafür verschiedene Strategien vorgeschlagen worden. Zum Beispiel werden in Zwei-Stufen-Verfahren Pakete von Lieferfahrzeugen zunächst zu Mini-Depots im Stadtgebiet gebracht und von dort mit Hilfe von kleinen, möglicherweise autonomen, Fahrzeugen zu den Empfängern transportiert. Eine weiterer Vorschlag besteht darin, Drohnen in den Auslieferungsfahrzeugen zu transportieren, die einzelne Empfänger beliefern können.  Allerdings haben beide Strategien entscheidende Nachteile. Die Standortwahl und der Bau von Mini-Depots sind oft von politischen Faktoren beeinflusst und stationäre Mini-Depots sind wenig robust gegenüber Änderungen in der Nachfrage. Auch der Einsatz von Drohnen in urbanen Gebieten ist regulatorisch eingeschränkt. Zusätzlich sind die Transportkapazität von Drohnen und deren Reichweite beschränkt, so dass Drohnen oft nur ein Paket transportieren und sich nicht weit von dem Lieferfahrzeug entfernen können.

Laufzeitschranken für den Simplex Algorithmus durch Markov-Entscheidungsprozesse

von Nils Mosis (Gewinner Masterpreis 2023)

Simplex Algorithmus

Der Simplex Algorithmus wurde 1947 von George Dantzig entwickelt [1] und wird bis heute für die Lösung linearer Optimierungsprobleme genutzt. Der Algorithmus startet in einer Ecke der zulässigen Menge und bewegt sich dann iterativ zu benachbarten Ecken mit einem verbesserten Zielfunktionswert, bis er eine optimale Lösung findet (siehe Abb. 1) oder erkennt, dass das lineare Programm (LP) unbeschränkt ist.

Abb. 1: Das zulässige Polyeder eines LPs mit zu maximierendem Zielfunktionsvektor c. Der Simplex Algorithmus findet das Optimum hier in drei Schritten.

Multidimensionale Optimierung und das Problem der k kürzesten Wege

von Max Huneshagen (Gewinner Masterpreis 2023)

Viele Millionen Menschen fliegen jedes Jahr von Deutschland aus zu Zielen in Nah und Fern. Nur die Wenigsten werden sich dabei fragen, welchen Weg sie eigentlich genau nehmen. Aus der Sicht von Fluggesellschaften kann sich die Wahl der optimalen Flugroute als ein kompliziertes Problem herausstellen. Auf den ersten Blick könnte man meinen, dass man immer den direkten Weg wählen sollte – schließlich ist dieser am kürzesten und daher doch wohl sicher auch am billigsten? In der Realität ist dieser naive Ansatz leider zumeist falsch, da weitere Kosten berücksichtigt werden müssen, die nicht unbedingt proportional mit der Weglänge steigen. So verlangen beispielsweise Staaten Gebühren für das Überqueren ihres Hoheitsgebietes. Deswegen kann es womöglich günstiger sein, eine längere Strecke über ein Land mit geringen Gebühren zu fliegen als nur kurz über ein Land, das viel Geld für einen Überflug verlangt. Außerdem spielen die Stärke und Richtung des Windes eine wichtige Rolle in der Flugplanung, was dazu führt, dass Flugrouten oft dynamisch geplant werden müssen.

On-Demand-Mobilitätsdienste als integrative Ergänzung zum ÖPNV

von Lorenz Saathoff (Gewinner Masterpreis 2023)

Neuartige Konzepte des bedarfsorientierten Nahverkehrs (engl. Demand-Responsive Transport) werden im Sinne der Verkehrswende als vielversprechende Lösungsansätze für notwendige Veränderungen im Mobilitätssektor diskutiert. Zusätzlich zum Ausbau des ÖPNV muss dessen Attraktivität gesteigert werden, um Anreize für den Umstieg zu setzen und damit den Anteil des Umweltverbunds am Modal Split zu erhöhen. Die Ergebnisse der Studie [1] in Bezug auf die Einflüsse von Anreizen für einen Wechsel zeigen, dass eine bessere Anbindung im Sinne hoher Pünktlichkeit, Taktung und Flexibilität den größten Einfluss aufweist. Bei der Verbesserung des Anschlusses bisher noch nicht ausreichend erschlossener Gebiete können Dial-a-Ride-Services (DARS) einen wichtigen Beitrag leisten, welche in der mit dem Masterarbeitspreis der GOR ausgezeichneten Arbeit [2] näher betrachtet werden.

Solche bedarfsorientierten Verkehrsmittel zeichnen sich dadurch aus, dass Fahrgäste auf Basis mobiler Applikationen die Möglichkeit erhalten, Fahrten innerhalb des Geschäftsgebiets kurzfristig online zu buchen. Die Anbieter versuchen, die angefragten Fahrten möglichst zu bündeln, um eine optimale Auslastung der Fahrzeuge (zumeist Minibusse) zu gewährleisten, ohne den Reisenden zu starke Unannehmlichkeiten in Form von Umwegen und Wartezeiten zu bereiten. Anbieter solcher Dienste sehen sich mit dem in der Wissenschaft als Dial-a-Ride-Problem (DARP) bezeichneten Planungsproblem konfrontiert. In dessen Rahmen gilt es, zu entscheiden, welche Fahrtanfrage welchem Fahrzeug zugeordnet wird und in welcher Reihenfolge die Wagen die Fahrgäste bedienen sollten. Aufgrund operativer Einschränkungen und anderer Vorgaben, die das Finden einer im Sinne eines Ziels oder mehrerer Ziele optimalen Lösung erschweren, handelt es sich hierbei um ein komplexes Entscheidungsproblem.