Ridepooling als Mobilitätsangebot für die allgemeine Bevölkerung

Autor: Arne Schulz

Im Kampf gegen den Klimawandel ist die Vermeidung von CO2-Emissionen essenziell. Neben anderen Bereichen trägt auch der Verkehrssektor und damit unsere tägliche Mobilität wesentlich zu der hohen CO2-Konzentration in der Atmosphäre bei. Glücklicherweise stehen uns bereits zahlreiche Möglichkeiten zur Emissionsvermeidung im alltäglichen Personenverkehr zur Verfügung. Neben CO2-neutralen Antriebsstoffen wie regenerativ erzeugtem Strom liegt ein wesentliches Potential in der geteilten Nutzung der Fahrzeuge. Durch Carsharing kann die absolute Anzahl der Fahrzeuge und damit der Ressourcenverbrauch in der Herstellung reduziert werden.

Ein Problem, das durch Carsharing nicht gelöst wird, ist die häufig sehr geringe Auslastung der Fahrzeuge. Von typischerweise fünf Plätzen eines PKWs sind oft nur ein oder zwei besetzt. An diesem Punkt setzt das Ridepooling an. Beim Ridepooling werden die Fahrtwege unterschiedlicher Personen zu einer Fahrt zusammengefügt. Während der Vorteil mit der besseren Auslastung des Fahrzeugs auf der Hand liegt, ist der Nachteil, dass die einzelne Person gegebenenfalls einen Umweg in Kauf nehmen muss, damit eine andere Person abgeholt oder an ihr Ziel gebracht werden kann. In einer Großstadt wiegt der Nachteil des Umwegs für die Kunden aufgrund der Alternativen (ÖPNV, eigener PKW, Carsharing, Taxi, E-Scooter, Bikesharing) noch stärker. Der Anbieter muss also attraktiv genug für die Kunden sein und gleichzeitig eine hinreichend hohe Poolingrate erreichen, um wirtschaftlich arbeiten zu können.

Um ein derartiges System zu evaluieren, haben wir einen Adaptive Large Neighbourhood Search Algorithmus für die Zuordnung von Kunden zu Fahrzeugen und die Planung der Touren entwickelt, der zu vielversprechenden Ergebnissen führt.

Der dazugehörige Artikel im OR Spectrum steht unter folgendem Link frei zum Download zur Verfügung: https://link.springer.com/article/10.1007/s00291-021-00656-7

Resident scheduling in teaching hospitals

Autor: Sebastian Kraul

There are currently almost 60,000 medical residents in one of 57 specialist training programs in Germany. The cost pressures of hospitals and the changing view of the medical profession regarding the work-life balance have led to recruitment problems and low employee satisfaction in many places. A promising approach to counter this problem is through objective and structured training planning.

My dissertation mainly deals with medical residents‘ strategic and tactical-operative training scheduling. In addition to relieving the medical staff currently responsible for the planning process, a focus was to increase the predictability of a structured training. This allows hospitals to increase the quality of their training and, consequently, their attractiveness to other hospitals. In addition, supervisors from different departments can better assess the knowledge of residents and thus keep the level of service, which is particularly important in hospitals, permanently high even when changing residents.

From the residents‘ point of view, a well-structured training planning, in addition to ensuring the program duration, enables a high degree of information. Residents are therefore no longer surprised by a short-term department change – they are currently informed one or two weeks in advance about a change – and have a direct insight into their training progress.

In addition to the mathematical modeling of the problems and the development of exact and heuristic solution approaches, our cooperation partner München rechts der Isar made a practice-oriented verification of the methods by cross-checking the actual training schedules in close coordination with the responsible planner. It showed that the developed methods led to results usable in practice. In particular, we were able to identify bottlenecks in the hospital’s surgical portfolio, which strongly impacts training. Finally, the interactions within and outside the training process were analyzed, especially regarding fairness, continuity, and uncertainty.

Additional information on the results can be found on my project page on Research Gate.

A Two-Stage Stochastic Optimisation Model for Urban Same-Day Delivery with Micro-Hubs

Autor: Charlotte Ackva

Facing the vast range of products in the e-commerce sector, more and more customers are purchasing online. To compete with the big online retailers, many local shops also offer a delivery service to their customers. However, conventional delivery by motorised vans is often inefficient due to low delivery volumes, access restrictions in city centres, and poor parking conditions.

To overcome these challenges, local shops start collaborating for joint transportation of parcels to the same region. For this, micro-hubs are used as intermediate storage and transhipment facilities. This increases consolidation opportunities in the delivery process: shops bring their goods to a close-by micro-hub. There, parcels are picked up by a shared vehicle for further transportation to other micro-hubs close to the parcels’ destinations. The shared vehicle is conducting a consistent tour, i.e. visiting the same micro-hubs at the same time every day. While this gives planning stability to storekeepers, customers, and drivers, finding an effective consistent schedule is challenging. Since customer orders vary from day to day, it highly depends on the consistent schedule which of these orders can be fulfilled. Figure 1 exemplarily shows a consistent schedule for two different demand realisations.

Figure 1: Example of a consistent tour for two different demand realisations (own illustration).

We formulate the problem as a two-stage stochastic optimisation model aiming to maximise the expected number of fulfilled customer orders. At the first stage, when demand is still unknown, the vehicle’s schedule is determined. At the second stage, the flow of parcels is decided based on the schedule from the first stage.

We apply the Progressive Hedging (PH) Algorithm to determine a consistent schedule. While convergence of PH is shown for convex programs, this does not hold true for integer programs anymore. Therefore, we investigate the performance of the algorithm for different parameter settings and different demand patterns. We find that PH performs rather poorly when demand is randomly distributed, but yields particularly good results when structural information of the demand distribution is available.

Multi-Period Optimization of the Refuelling Infrastructure for Alternative Fuel Vehicles

Author: Alexander Böhle

The idea for my Bachelor Thesis “Multi-Period Optimization of the Refuelling Infrastructure for Alternative Fuel Vehicles” originated from combining two of my favourite topics – The future of mobility and Operations Research.

While many consider alternative fuel vehicles (AFV) as an important mean to reduce greenhouse gas emissions, the lack of a sufficient refuelling infrastructure is a major barrier to the widespread adoption of AFVs. Although it is expected that an adequate number of alternative fuel stations (AFS) will eventually be constructed, due to the high resource-intensity of infrastructure development, an optimal step-by-step construction plan is needed. For such a plan to be actionable, it is necessary, that the underlying model considers realistic station sizes and budgetary limitations.

To address this issue, I have developed a new formulation of the flow-refuelling location model, that combines multi-periodicity and node capacity restrictions (MP-NC FRLM). For this purpose, the models of Capar et al., 2013 and Kluschke et al., 2020 have been extended, and the pre-generation process of sets and variables has been improved.

While adding a temporal component to a model might seem easy at first glance, it is far from obvious whether a multi-period model leads to a performance improvement that would justify the additional complexity. Hence, I adapted and applied the two evaluation concepts Value of the Multi-Period Solution (VMPS) and Value of Multi-Period Planning (VMPP) to assess the model’s relative additional benefit over its static counterparts. To better identify situations respectively parametric constellations where the multi-period model would be worth applying, I looked for potential drivers of the additional value of the multi-period model within the scope of a numerical experiment.

While the MP-NC FRLM has proven to provide additional benefit over static counterparts, it comes at the cost of a higher solving time. For determining realistic station sizes, the model could be further developed by adding deviation paths (= the drivers’ willingness to deviate from the optimal path for refuelling) and the stochasticity of demand.

Acknowledgement:
I would like to thank my mentor Hannah Bakker for the great support and Professor Stefan Nickel (both Karlsruhe Institute of Technology) for his openness to supervise my thesis project, even though it did not quite match the chair’s research focus. Finally, I would like to thank Professor Youssef Maknoon (Technische Universiteit Delft) for inspiring me with his excellent lectures during my exchange to write my thesis in Operations Research.

Datengetriebene Absicherung von Rohstoffpreisrisiken

Autor: Christian Mandl

Rohstoffpreise sind während der Corona-Pandemie signifikant gestiegen. Dies gilt nicht nur für Holz, dessen Preis sich in den vergangenen Monaten nahezu verdreifacht hat. Auch die Preise für Aluminium und Kupfer stiegen im vergangenen Jahr um mehr als 50%. Ähnliche Preisanstiege sind für Agrarprodukte wie Mais oder Weizen zu beobachten.

Dies macht für rohstoffbeschaffende Unternehmen gerade jetzt ein effektives Risikomanagement wichtiger denn je.

Zwei in der Praxis gängige Instrumente zur Absicherung von Rohstoffpreisrisiken sind Termingeschäfte (sogenanntes Financial Hedging) und die Vorratslagerhaltung (sogenanntes Operational Hedging).

In beiden Fällen setzt die Optimierung der Beschaffungszeitpunkte und -mengen die Lösung eines komplexen, mehr-periodigen stochastischen Optimierungsproblems voraus. Darüber hinaus stellt sich in einer aktuell von Buzzwords wie „KI“ und „Big Data“ dominierten Geschäftswelt die Frage, wie Daten (beispielsweise interne und externe Featuredaten) zur Optimierung von Beschaffungsentscheidungen genutzt und effizient operationalisiert werden können.

Eine Kombination aus klassischen Optimierungsverfahren (z.B. gemischt-ganzzahlige lineare Programmierung) mit Standardverfahren des Maschinellen Lernens kann hier Abhilfe schaffen, um Beschaffungs- und Lagerhaltungsentscheidungen am Rohstoffmarkt datengetrieben abzuleiten.

Während die klassischen Ansätze Prognose und Entscheidung bzw. Optimierung typischerweise separieren, setzen unsere Ansätze auf eine Integration von Prognose und Optimierung, das heißt Machine Learning ist Teil des Optimierungsalgorithmus. So wird sichergestellt, dass nicht notwendigerweise die Preisprognosen optimiert werden sollen (was ohnehin ein schwieriges Unterfangen ist), sondern der Fokus auf der Minimierung der Beschaffungskosten liegt, was die eigentliche Zielfunktion des Unternehmens charakterisiert. Dadurch wird der Beobachtung Rechnung getragen, dass optimale Preisprognosen keine notwendige Bedingung für kostenoptimale Beschaffungsentscheidungen sind.

Das Resultat sind einfache und interpretierbare (lineare) Entscheidungsregeln, die dem Einkäufer datengetriebene Kaufsignale (oder Wartesignale) liefern, die je nach Rohstoffklasse beispielsweise von Konjunkturindikatoren aber auch Wetterdaten abhängen können.

Weitere Details zu unserer Arbeit finden Sie unter anderem unter den folgenden Links:
https://link.springer.com/chapter/10.1007/978-3-658-31898-7_3
https://pubsonline.informs.org/doi/abs/10.1287/msom.2020.0890