Gesellschaft für Operations Research e.V.

gor

OR Konferenz 2022 – Karlsruhe

von JOHANNA DUJESIEFKEN & GUIDO VOIGT

Nach zwei Jahren der COVID19-Pandemie fand die diesjährige Jahrestagung der Gesellschaft für Operations Research endlich wieder in Präsenz statt. Vom 6. bis 9. September 2022 wurden am Karlsruher Institut für Technologie (KIT) abwechslungsreiche, interessante, und anspruchsvolle Ideen und Beiträge insbesondere zu den Themen Energie, Information und Mobilität präsentiert.
Die über 625 Teilnehmern konnten aus einem Tagungsprogramm, welches über 425 Beiträge in 113 Sessions umfasste, wählen. Ergänzt wurde das Programm durch 3 spannende Plenar- und 9 Semiplenarvorträge, 4 Workshops und das Begleitprogramm Dokt!OR.

Am Dienstagnachmittag begann die Konferenz, speziell für die Nachwuchswuchswissenschaftler, mit dem Dokt!OR-Programm. Hier hielt Manuela Schnaubelt vom KIT einen Vortrag zum Thema „Slow down and gain time – an introduction to stress and time management for doctoral researchers“. In der anschließenden Panel-Diskussion konnten sich interessierte Doktorandinnen und Doktoranden über Karrierewege in der Wissenschaft informieren. Für Fragen standen Prof. Dr. Christina Büsing (RWTH Aachen), Dr. sc. ETH Stephan Bütikofer (ZHAW Zurich University of Applied Sciences) und Dr.-Ing. Uta Mohring (KIT) zur Verfügung. Der Moderator Christian Füllner (KIT) führte durch die Veranstaltung. Beim abschließenden Get-Together im Mathematik-Gebäude 20.30 bestand die Möglichkeit, bei kühlen Getränken und leckeren Häppchen neue Kontakte in der Wissenschaft zu knüpfen oder bisherige Kontakte zu anderen Wissenschaftlern zu vertiefen.

Am Mittwoch wurde das wissenschaftliche Programm von Prof. Dr. Stefan Nickel und einer Video-Begrüßung von Prof. Dr. Steffen Rebennack eröffnet. Anschließend stellte Prof. Dr. Michael Decker das KIT, die Forschungsuniversität in der Helmholtz-Gemeinschaft, und Prof. Dr. Alf Kimms die Gesellschaft für Operations Research vor. Außerdem wurden vier Preise verliehen.

Für den GOR Master Thesis Award, gefördert von der GAMS Software GmbH, wählte die Auswahlkommission unter Leitung von Kevin Tierney die folgenden Arbeiten aus:

  • A Two-Stage Stochastic Optimisation Model for Urban Same Day Delivery with Micro Hubs, Charlotte Ackva, M. Sc., Georg-August-Universität Göttingen, Fakultät für Mathematik und Informatik, Betreuer: Prof. Dr. Russell Luke, Prof. Dr. Marlin Ulmer
  • Solving Customer Order Scheduling Problems with an Integrated Greedy Algorithm, Julius Hoffmann, Dipl.-Wi.-Ing., Technische Universität Dresden, Fakultät Wirtschaftswissenschaften, Betreuer: Prof. Dr. Udo Buscher
  • The stochastic bilevel selection problem, Jannik Irmai, M. Sc., Technische Universität Dortmund, Fakultät Mathematik, Betreuer: Prof. Dr. Christoph Buchheim

Nicht weniger schwierig war die Auswahl der Preisträger des GOR-Dissertationspreises, den die Gurobi Optimization GmbH finanziell unterstützte. Die Auswahlkommission unter Leitung von Peter Letmathe wählte die folgenden Arbeiten aus:

  • Algorithms for Mixed-Integer Bilevel Problems with Convex Followers, Dr. rer. nat. Thomas Kleinert, Friedrich-Alexander Universität Erlangen-Nürnberg, Naturwissenschaftliche Fakultät, Betreuer: Prof. Dr. Martin Schmidt
  • Resident scheduling in teaching hospitals, Dr. rer. pol. Sebastian Kraul, Universität Augsburg, Wirtschaftswissenschaftliche Fakultät, Betreuer: Prof. Dr. Jens O. Brunner
  • Prescriptive Analytics for Data-driven Capacity Management, Dr. rer. pol. Pascal Notz, Julius-Maximilians-Universität Würzburg, Wirtschaftswissenschaftliche Fakultät, Betreuer: Prof. Dr. Richard Pibernik
  • Faster algorithms for Steiner tree and related problems: From theory to practice, Dr. rer. nat. Daniel Rehfeldt, Technische Universität Berlin, Fakultät II – Mathematik und Naturwissenschaften, Betreuer: Prof. Dr. Thorsten Koch

Für den GOR Young Researcher Award, der vom Fraunhofer IWTM gesponsert wurde, wählte die Auswahlkommission unter Leitung von Alexander Martin die folgenden Forscher aus:

  • Dr. Elisabeth Gaar, An SDP-based approach for computing the stability number of a graph – gemeinsam mit Melanie Siebenhofer, Angelika Wiegele– veröffentlicht in Mathematical Methods of Operations Research
  • Dr. Arne Schulz, An ALNS algorithm for the static dial a ride problem with ride and waiting time minimization – gemeinsam mit Christian Pfeiffer – veröffentlicht in OR Spectrum
  • Dr. Stefan Schwerdfeger, Last-mile delivery concepts: a survey from an operational research perspective – gemeinsam mit Nils Boysen, Stefan Fedtke – veröffentlicht in OR Spectrum

Den GOR Company Award erhielten die Gründer der Optano GmbH, Dr. Stefan Bunte, Dr. Jens-Peter Kempkes und Dr. Ingmar Steinzen. Im Namen der Auswahlkommission übergab Dr. Jens Schulz (FICO) den Preis.

Anschließend hielt Prof. Dr. Maria Grazia Speranza (University of Brescia, Italien) einen inspirierenden Vortrag über die „Optimization in transportation & logistics: yesterday, today, tomorrow“. In einem spannenden Bogen über die Entstehung und Entwicklung des Gebiets des Operations Research zeigte sie zukunftsweisende Anwendungsgebiete des Operations Research auf. Den zweiten Plenarvortrag mit dem Titel „Sensing Applications as a Driver for Edge-AI Solutions“ hielt PD Dr. Victor Pankratius (Bosch Sensortec) im Laufe des Donnerstags. Der Vortrag zeigte viele Anwendungsfälle, in denen Sensoranwendungen zu einem wichtigen Treiber für künstliche Intelligenz im Ultra-Low-Power-Kontext werden. Weiterhin wurde auf die Bedeutung der Formalisierung und Einbeziehung von Fachwissen in das maschinelle Lernen eingegangen, das Optimierungspotentiale wie z. B. die Verringerung des Speicherbedarfs schafft. Den dritten Plenarvortrag mit dem Titel Lessons for OR from the Covid-19-Pandemic hielt Prof. John R. Birge (University of Chicago, USA) im Rahmen der Abschlussveranstaltung am Freitag. Basierend auf den Lehren der Covid-19-Pandemie adressiert dieser Vortrag neue Forschungsherausforderungen und die Rolle von Operations Research bei der Behandlung von globalen politischen Fragen.

Auch in den neun Semiplenarvorträgen spiegelt sich die Vielfalt des Operations Research wider. Am Mittwoch standen folgende Semiplenarvorträge auf dem Programm:

  • Algorithmic Developments in Multiobjective Optimization, Gabriele Eichfelder, TU Ilmenau
  • Steiner Cut Dominants, Volker Kaibel, OvGU Magdeburg
  • Improving Cancer Treatment Logistics, Nadia Lahrichi, Polytechnique Montréal, Kanada

Am Donnerstag umfassten die Semiplenarvorträge:

  • Network Design in Humanitarian Logistics, Bahar Yetis Kara, Bilkent University, Türkei
  • Automated Design of Algorithms, Thomas Stützle, National Science Foundation, Belgien
  • Rapid Optimization Projects, Optano GmbH

Am Freitag fanden sich im Programm die folgenden Semiplenarvorträge:

  • Moving Consumer Goods, Not Vehicles, Virginie Lurkin, University of Lausanne, Schweiz
  • 50 Years Club of Rome – OR Challenges and Perspectives on Energy Security and Complex Resource Conflicts, Stefan W. Pickl, Universität der Bundeswehr München
  • Additive Approximation and Approximation Schemes for Load Balancing, Tjark Vredefeld, University of Maastricht, Niederlande

Nach der GOR-Mitgliederveranstaltung fand am Donnerstagabend das Konferenzdinner im Lichthof der BGV Badische Versicherungen statt. In angenehmer Atmosphäre konnten beim Sektempfang und dem anschließenden exquisiten Buffet neue Kontakte geknüpft und bestehende Kontakte vertieft werden.

Stellvertretend für alle Konferenzteilnehmer bedanken wir uns bei den Verantwortlichen, insbesondere Prof. Dr. Steffen Rebennack, Prof. Dr. Stefan Nickel und Dr. Marcel Sinske, für das gut gestaltete Tagungsprogramm sowie dem gesamten Organisationsteam vor Ort für die ausgezeichnete und reibungslose Organisation. Wir freuen uns auf ebenso schöne Konferenztage bei der OR 2023 in Hamburg! (https://www.or2023.uni-hamburg.de)

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