GOR Blog

Optimierung mit Ordinalen Kosten

von Dr. Julia Sudhoff Santos (Gewinnerin Dissertationspreis 2023)

Ordinale Kosten werden verwendet, wenn eine Größe nicht numerisch messbar ist, sondern sich nur in geordnete Kategorien (zum Beispiel gut, mittel, schlecht) einordnen lässt. Bekannte Skalen dieser Art sind der Nutri-Score auf Lebensmitteln, die Stufe der Tierhaltungsform bei Fleisch, oder olympische Medaillen. Es gibt verschiedene Möglichkeiten die Länder bei Olympia zu ranken, weil nicht klar ist um wie viel besser Gold- verglichen mit Silber- und Bronzemedaillen sind. So gibt es verschiedene Ansätze, wie zum Beispiel die Länder nach der Gesamtzahl der Medaillen oder lexikographisch zu sortieren. Dies verdeutlicht, dass Optimierungsprobleme mit ordinalen Kosten mehrere optimale Lösungen haben können, welche nicht miteinander vergleichbar sind.

Diese Eigenschaft teilen sie mit den vielfach untersuchten multikriteriellen Optimierungsproblemen. Diese Ähnlichkeit hat eine mathematische Erklärung: Optimierungsprobleme mit ordinalen Kosten können durch eine lineare Transformation in äquivalente multikriterielle Optimierungsprobleme umgeformt werden, wobei die Problemstruktur erhalten bleibt und nur die Zielfunktion angepasst wird.

Drohnen als Zulieferer auf der letzten Meile

von Dr. Michael Dienstknecht (Gewinner YRA 2023)

Auf der Suche nach schnell wirkenden Lösungen für die Probleme auf der letzten Meile der Paketzustellung haben sich in der jüngeren Vergangenheit Forscher wie Praktiker u.a. auf den Einsatz moderner Technologien gestürzt – darunter auch Drohen. Den in der Forschung betrachteten drohnen-gestützten Konzepten ist (bis auf wenige Ausnahmen) gemein, dass sie eine direkte Interaktion zwischen Drohne und Empfänger voraussetzen – und damit neue Probleme wie bspw. bzgl. Kunden-Erreichbarkeit und Customer Experience schaffen. Es ergibt sich die Frage, ob es dennoch möglich ist, von den zweifellos vorhandenen Vorteilen einer Drohne zu profitieren, wenn direkter Kontakt zwischen Kunde und Drohne ausgeschlossen werden soll. Tatsächlich besteht diese Möglichkeit – etwa, wenn die Drohne eingesetzt wird, um den eigentlichen Zusteller von einem (außerstädtischen) Depot zu beliefern. Dadurch unterbleibt nicht nur jeder Kundenkontakt der Drohne, sondern es werden zwei logistisch interessante Dinge erreicht: Die oftmals (zu) knappen Kapazitäten der eigentlichen Lieferfahrzeuge werden erweitert und man erlaubt eine Berücksichtigung dynamisch am Depot eintreffender Lieferaufträge – gerade im Onlinehandel sehr relevant.

Im Rahmen eines Forschungsprojektes von Dienstknecht, Boysen und Briskorn (2022) wird ein entsprechendes Problem formalisiert, als gemischt-ganzzahliges Programm formuliert und mit verschiedenen Heuristiken, die auf der Dekomposition des Problems in die Routenplanung des Liefervehikels und die Erzeugung des für diese Route optimalen Flugplans der Drohne (per Dynamischer Programmierung) basieren, angegangen. In einer umfassenden Rechenstudie zeigt sich, dass dieses Lieferkonzept bei korrekter Umsetzung eine deutlich günstigere Auslieferung ermöglichen kann als die rein lieferwagen-gebundene Variante, aber auch als die sonst in der Literatur übliche Konzeption, in der sowohl Lieferwagen als auch Drohne Kunden direkt beliefern.

Eine mathematische Herausforderung: Buchungsvalidierung im Europäischen Entry-Exit Gasmarktsystem

von Dr. Johannes Thürauf (Gewinner YRA 2023)

Infolge der seit den 1990er Jahren voranschreitenden europäischen Gasmarktliberalisierung wurde das sogenannte Entry-Exit-System als Gasmarktsystem in Europa eingeführt. Eines der Hauptziele dieses Marktsystems ist die Entkopplung von Gashandel und dem zugehörigen Gastransport. Für die Analyse des europäischen Entry-Exit-Systems wird in der mathematischen Literatur häufig ein vierstufiges Optimierungsmodell, siehe [1], verwendet, welches eine idealisierte Form des Entry-Exit-Modells beschreibt. In diesem Modell interagieren ein Netzbetreiber und Gashändler auf verschiedenen Stufen miteinander, wobei der Netzbetreiber verantwortlich für den Gastransport ist. Sogenannte Buchungen spielen eine wichtige Rolle im Entry-Exit-System, um den Gashandel und -transport zu entkoppeln. Buchungen sind im Allgemeinen mittel- bis langfristige Verträge bezüglich Kapazitätsrechte an Ein- und Ausspeisepunkten des Netzes. Die vorab gebuchten Kapazitäten erlauben es den Händlern, im täglichen Gashandel beliebige bilanzierte Ein- und Ausspeisemengen innerhalb der gebuchten Kapazitäten zu nominieren. Für einen detaillierten Einblick in die mathematische Modellierung des Entry-Exit-Systems und in die Gasmarktliberalisierung in Europa verweisen wir auf [1, 4].

Semidefinite Programme für die Berechnung der Stabilitätszahl

Autorin: Elisabeth Gaar

Viele mathematische Optimierungsproblem sind auf so genannten Graphen definiert. Diese haben Knoten (die man sich als Punkte vorstellen kann) und Kanten (die man sich als Striche vorstellen kann), die je zwei dieser Knoten miteinander verbinden. Eines der fundamentalsten Optimierungsproblemen auf Graphen ist es, die Stabilitätszahl eines Graphen zu bestimmen. Dabei handelt es sich um die größte Anzahl von Knoten des Graphen, so dass je zwei dieser Knoten nicht miteinander durch eine Kante verbunden sind. Leider ist es ein (NP-) schweres Problem, die Stabilitätszahl eines Graphen zu bestimmen. Aufgrund der zahlreichen Anwendungen, zum Beispiel in der Molekularbiologie oder bei Terminplanungsproblemen, hat man aber trotzdem ein großes Interesse daran, die Stabilitätszahl von Graphen genau zu bestimmen.

Elisabeth Gaar, Melanie Siebenhofer und Angelika Wiegele haben sich im Artikel „An SDP-based approach for computing the stability number of a graph“, der 2022 im Journal Mathematical Methods of Operations Research publiziert wurde, damit beschäftigt, die Stabilitätszahl von Graphen zu berechnen. Dabei haben sie sich eines weit verbreiteten Lösungsansatzes (einem so genannten Branch-and-Bound-Verfahren) bedient, für dessen Umsetzung man gute Schranken an die Stabilitätszahl braucht. Die Autorinnen haben diese Schranken mit Hilfe eines Semidefiniten Programms erhalten, das bereits 1979 von Lovasz eingeführt wurde, und für das kürzlich von Elisabeth Gaar und Franz Rendl weitere Verbesserungen vorgeschlagen wurden. In dieser Publikation wurden einerseits erstmals die existierenden Schranken für die gesamte Berechnung der Stabilitätszahl verwendet. Andererseits haben die Autorinnen zwei Wege vorgeschlagen, um diese existierenden Schranken deutlich schneller zu berechnen, ohne dabei einen großen Qualitätsverlust in Kauf nehmen zu müssen. Einer der Wege basiert auf der Kenntnis der Facetten des zugrundeliegenden Polytops, der andere auf separierenden Hyperebenen. Dadurch ist es den Autorinnen möglich, den Speicherbedarf für die Berechnung der Stabilitätszahl klein zu halten, und dabei die Zeit für die Berechnung deutlich zu verringern.

Den ganzen Artikel aus Mathematical Methods of Operations Research findet man frei zugänglich unter https://link.springer.com/article/10.1007/s00186-022-00773-1.

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