In vielen Anwendungsbeispielen der diskreten Optimierung müssen zeitliche Aspekte bei der Modellierung berücksichtigt werden. Eine Möglichkeit den Aspekt der Zeit in die Modelle zu integrieren sind zusätzliche kontinuierliche Variablen, die zum Beispiel Ankunftszeiten an bestimmten Orten repräsentieren. Diese Modelle haben den Nachteil, dass deren lineare Relaxierung normalerweise sehr schwach ist, was negative Auswirkungen im Lösungsprozess mittels Branch-and-Bound hat. Alternativ ist es möglich jede mögliche Kombination von Ankunftszeit und Ort als Knoten in einem Graphen, dem sogenannten zeitexpandierten Graphen, zu modellieren. Kanten in diesem Graphen dürfen nur genutzt werden, wenn die Bewegung zwischen den Orten weniger Zeit benötigt, als der Unterschied der Ankunftszeiten. Mittels dieser Graphen lassen sich häufig Formulierungen herleiten deren lineare Relaxierung stark ist. Das Problem dieser Formulierungen ist nun, dass die Anzahl der benötigten Knoten und möglichen Kanten sehr groß ist. Im DFG Projekt "Lösung zeitabhängiger logistischer Optimierungsprobleme mit Hilfe zeitreduzierter Relaxierungen'" geht es darum Graphen zu finden, die immer noch eine relativ starke Relaxierung des Problems ermöglichen, aber deutlich weniger Knoten und Kanten benötigen. Diese Graphen dürfen prinzipiell auch Lösungen zulassen, die einen Teil der zeitlichen Bedingungen verletzt. In einem iterativen Verfahren werden die Graphen dann angepasst, bis eine Lösung gefunden wird, die keine der zeitlichen Bedingungen mehr verletzt. Im Laufe des Projekts wurden solche Ansätze auf zwei praxisnahe Probleme angewendet. Bei dem ersten galt es die Routenplanung von kleinen Passagierflugzeugen, die bei Safaris in Afrika zum Einsatz kommen, zu optimieren. Beim zweiten wurden die Reihenfolge, in der Kunden von autonom fahrenden elektrischen Zustellrobotern, optimiert.

Partneruniversitäten

Technische Universität Dortmund

Finanzierung

Deutsche Forschungsgemeinschaft, Grant Nr. FU 860/1-1

Vorträge

• Refinement Algorithms for the Time and Battery VRP, Workshop Optimierung 2021, Cottbus, 24.03.2021.
• The Branch and Refine Algorithm for Time Dependent Discrete Optimization Problems, OR 2019/ International Conference on Operations Research, Dresden, 05.09.2019.
• A Time-Flow Approach for Scheduling and Routing Fly-in Safari Airplanes, Workshop Optimierung 2019, Olbernhau, 15.03.2019.
• A Time-Flow Approach for Scheduling and Routing of Fly-in Safari Airplanes, OR 2018/ International Conference on Operations Research, Brüssel, 12.09.2018.

Veröffentlichungen

• Fabian Gnegel, Stefan Schaudt, Uwe Clausen, Armin Fügenschuh, A 2D Layered Graph Approach for Scheduling Delivery Robots, 2021, Preprint. DOI:10.26127/btuopen-5493
• Fabian Gnegel und Armin Fügenschuh, Branch-and-Refine for Solving Time-Dependent Problems, 2020, Preprint. DOI: 10.26127/btuopen-5199
• Fabian Gnegel und Armin Fügenschuh, An Iterative Graph Expansion Approach for the Scheduling and Routing of Airplanes, Computers & Operations Research 114:104832, 2020. DOI: 10.1016/j.cor.2019.104832