GOR Blog

Methoden der gemischt-ganzzahligen Optimierung für robuste Bilevel-Probleme mit „here-and-now“-Followern

von Dr. Yasmine Beck (Gewinnerin des GOR Dissertationspreises 2025)

Optimierungsmodelle sind ein zentrales Werkzeug zur Unterstützung von Entscheidungsträgern in komplexen Entscheidungsprozessen. In der klassischen, einstufigen Optimierung wird angenommen, dass eine einzige Person oder Instanz alle Entscheidungen trifft – ein geeigneter Rahmen für viele Anwendungen in der Praxis, aber eben nicht für alle. In zahlreichen realen Situationen treffen mehrere Akteure Entscheidungen, die sich gegenseitig beeinflussen können. Ein Entscheidungsträger muss dabei oft antizipieren, wie andere auf seine Wahl reagieren werden. Zum Beispiel legt ein Unternehmen Preise für Waren oder Dienstleistungen fest, welche die Nachfrage der Kunden beeinflussen können. Im Verkehrsmanagement bestimmen Behörden Mautgebühren, auf deren Grundlage Reisende ihre Routen anpassen. Beim Schutz kritischer Infrastrukturen müssen Schutzmechanismen so gewählt werden, dass Systeme auch in Ausnahmesituationen wie Naturkatastrophen, technischen Ausfällen oder terroristischen Angriffen funktionsfähig bleiben.

Optimiertes Matching von Angebot und Nachfrage in Free-Floating Car-Sharing Systemen

von Prof. Dr. Felix Weidinger (Gewinner YRA 2024)

Car-Sharing wird häufig als eine wichtige Brückentechnologie in eine nachhaltigere individuelle Mobilität gesehen. Schätzungen zufolge ersetzt in Deutschland ein Pkw in einem Car-Sharing-Angebot abhängig von verschiedenen Einflussfaktoren zwischen drei und zehn privat besessene Pkw (Umweltbundesamt, 2024); Branchenschätzungen sprechen sogar von bis zu zwanzig ersetzen privaten Pkw (Bundesverband Carsharing, 2024).  Dennoch ringen viele Car-Sharing-Anbieter weltweit um den Fortbestand ihrer Car-Sharing-Systeme. Selbst Branchengrößen im Automobilsektor, wie Mercedes-Benz, BMW und General Motors, beendeten vor einigen Jahren ihr Engagement in diesem Bereich, da sie nicht in der Lage waren, die Dienste profitabel zu betreiben (vgl. Wayland, 2020, Hubik, 2022).

Verkehrsflüsse mit Adaptiver Routenwahl basierend auf Echtzeitinformationen

von Dr. Lukas Graf (Gewinner Dissertationspreis 2024)

Netzwerkflüsse bzw. Flüsse in Graphen sind ein häufig genutztes Modell für den Autoverkehr.  Hierbei wird das Straßennetz als gerichteter Graph und der Verkehr darin als Fluss modelliert. Insbesondere bildet man hierbei also nicht einzelne Autos ab, sondern gibt nur für jede Kante (=Straße) an, welche (beliebig teilbare) Menge an Verkehrsfluss diese benutzt. In Abhängigkeit von dieser Flussmenge hat jede Kante dann gewisse Kosten für ihre Benutzung. Im einfachsten Fall entsprechen diese Kosten dabei den vom Verkehr induzierten Reisezeiten auf den jeweiligen Straßen.

Regionen in Standortproblemen: Neue Perspektiven durch Mustererkennung

von Dr. Hannah Bakker (Gewinnerin Dissertationspreis 2024)

Das Capacitated Facility Location Problem (CFLP) gehört zu den klassischen Problemen der Standortplanung. Hierbei werden aus einer Menge von Kandidaten Standorte für Einrichtungen mit fixer Kapazität ausgewählt, um Nachfragen einer bekannten Menge an Kunden zu erfüllen. Die Eröffnung von Standorten verursacht fixe Kosten, während die Bedienung von Kundennachfragen variable Kosten verursacht, die von der Menge und Entfernung abhängen. Der zentrale Trade-off besteht darin, dass mehr Standorte höhere Fixkosten mit sich bringen, aber gleichzeitig kürzere Transportwege die variablen Kosten senken. Es wird entschieden, welche Standorte eröffnet und welche Kunden welchen Standorten zugeordnet werden.

Das CFLP ist seit den 1960er Jahren ein intensiv erforschtes Problem. Trotz seiner Anschaulichkeit findet man jedoch kaum visuelle Darstellungen von Instanzen oder Lösungen. Dies liegt einerseits daran, dass reale Transportkosten oft nicht proportional zu Luftlinienentfernungen sind, was eine Darstellung gemäß Positionen auf der Landkarte wenig aussagekräftig macht. Andererseits fehlen bei synthetischen Daten oft Angaben zur Position von Kunden oder Standorten, da nur Transportkostenmatrizen angegeben sind. Mit Hilfe multidimensionale Skalierung (MDS), einem Verfahren, das häufig in der Vorverarbeitung von Daten im maschinellen Lernen verwendet wird, bietet sich die Möglichkeit, Instanzen und Lösungen transportkostengerecht zu visualisieren. Hierbei wird die Transportkostenmatrix auf zwei Dimensionen reduziert, die als Koordinaten in der Ebene interpretiert werden, sodass die relativen Positionen von Standorten und Kunden transportkostengerecht abgebildet werden [1].

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.