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.

Mehr erfahren

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.

Mehr erfahren

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.

Mehr erfahren

Demand Management in Shared Mobility Systems

von Dr. Matthias Soppert (Gewinner Dissertationspreis 2023)

Shared Mobility Angebote wie Car Sharing und Bike Sharing sind im Laufe der letzten Jahrzehnte zu weit verbreiteten und beliebten Formen der urbanen Mobilität herangewachsen. Aufgrund ihrer ressourcenschonenden Ermöglichung von individuellem Personenverkehr gelten Shared Mobility Systeme (SMSe) als eine der zentralen Säulen für eine nachhaltige Mobilität der Zukunft. Aufrechterhaltung und Ausweitung dieses Angebots seitens privater Unternehmen erfordern einen profitablen Betrieb, jedoch besteht diesbezüglich eine große Herausforderung darin, dass sich aufgrund fluktuierender Nachfragemuster und unausgewogener Fahrzeugbewegungen – insbesondere bei den modernen free-floating SMSen – fortwährend Ungleichgewichte zwischen Angebot und Nachfrage einstellen, welche die Auslastung der Flotte mindern. Um diesen Ungleichgewichten entgegenzuwirken, wurde in der wissenschaftlichen Literatur traditionell vor allem die angebotsseitige Steuerung durch aktive Relokation von Fahrzeugen betrachtet. Die Dissertation Demand Management in Shared Mobility Systems von Dr. Matthias Soppert (Postdoc an der Professur für Business Analytics & Management Science, Universität der Bundeswehr München) schlägt mit dem Demand Management eine innovative und kosteneffiziente Alternative vor, bei der durch Preis- und Verfügbarkeitssteuerung nachfrageseitig Einfluss auf das System genommen wird.

Kontakt: matthias.soppert@unibw.de, Universität der Bundeswehr München, Professur für Business Analytics & Management Science

Balanced Electric Vehicle Charging under Uncertainty – From User-Centric to System-Centric Approaches

von Dr. Marianne Guillet (Gewinnerin Dissertationspreis 2023)

To facilitate the transition from conventional to electric vehicles (EV), various incentive mechanisms, such as purchase bonuses or tax reduction, have emerged, while car makers expand their EV model offerings and public charging infrastructure continues to evolve. Despite these efforts, the unavailability of home-charging solutions decreases the likelihood of adopting an EV, as scarce and unreliable public charging infrastructure triggers the so-called drivers’ charge anxiety. Thus, operational solutions that mitigate uncertainties in the public charging experiences are needed to foster EV adoption. My dissertation introduces three novel models and solution methods, that aim to reliably help EV drivers find a free charging station in the presence of uncertainties.

From a driver-centric approach, the aim is to provide reliable navigation guidance to the driver to find a free charging station, assuming uncertain charging station availability. The solution consists of a sequence of charging stations to visit until one can be used, e.g., no car blocking the access. The problem can be represented as a sequential decision-making process, that we formulate as a Markov Decision process. Our optimal solver is based on a labeling algorithm, whose dominance criterion builds on the decomposition of the Markovian policy cost. This approach also provides an effective heuristic algorithm if using a simplified variant of the dominance criterion. We further extend our formulation and methodology to account for coordinated guidance instructions in a multi-agent setting, which we solve with a hierarchical variant of our labeling algorithm.

From a system-centric perspective, we study a non-cooperative offline resource allocation problem, where several navigation platforms aim to optimally assign their EV drivers to available charging stations, such that no visit conflict arises for their drivers and the total travel time for drivers to assigned stations is minimal. In a game-theoretic setting, the non-guaranteed existence of a Pure Nash equilibrium motivates us to implement a mechanism design approach, both in an offline and in an online scenario. Such an approach significantly reduces visit conflicts and decreases the social cost by up to 42% in the online scenario.

Related publications can be accessed on Researchgate.