Die Routenplanung von kleinen Flugzeugen für Fly-in-Safaris ist ein anspruchsvolles Planungsproblem. Bei einer Flotte von Flugzeugen und einer Reihe von Flug-Anfragen mit zeitlichen Schranken für die früheste Abreise-und späteste Ankunftszeiten müssen die Flugzeugrouten so geplant werden, dass alle notwendigen Anforderungen erfüllt sind. Dazu gehören Kapazitätsbeschränkungen für die Ladung sowie für den Treibstoff. Darüber hinaus ist die Betankung der Flugzeuge nur an bestimmten, größeren Flughäfen möglich, so dass immer genug Treibstoff im Tank sein muss, um einen solchen erreichen zu können.

Wir führen eine auf gemischt-ganzzahliger linearer Programmierung basierende Formulierung für dieses Problem ein. Für seine Lösung entwickeln wir eine Heuristik, die auf randomisierter lokaler Suche basiert. Mit einem Branch-and-Cut-Löser kann die Formulierung beweisbar optimal nur für kleine Instanzen gelöst werden. Um bessere duale Schranken zu erhalten, verwenden wir eine Set-Covering basierte Neuformulierung, wobei neue Spalten mittels Heuristiken und exakter Methoden erzeugt werden. Wir verwenden ferner eine Neuformulierung, in der die Zeitfenster zunächst relaxiert sind, und später durch Schnittebenen und Branchings wieder eingeführt werden.

Partner

• Georgia Institute of Technology
• Georgia Institute of Technology

Vorträge

1. A Time-Free Relaxation for a Mixed-Integer Dynamic Optimization Problem, GOR Workshop on Technical Operations Research, Asselheim, Germany, 4.3.2014.
2. Optimizing Discrete and Continuous Problems Over Time, Magdeburg Lectures on Optimization and Control (MALOC), Magdeburg, 14.11.2013.
3. Optimizing Discrete and Continuous Problems Over Time, Discrete Optimization Seminar, Georgia Institute of Technology, Atlanta, Georgia, USA, 2.8.2013.
4. Scheduling and routing of fly-in safari airplanes, EURO/Informs 26th European Conference on Operational Research, Rom, 2.7.2013.
5. Scheduling and routing of fly-in safari airplanes, International Symposium on Mathematical Programming ISMP 2012, Berlin, 24.8.2012.

Veröffentlichungen

1. Armin Fügenschuh, George Nemhauser, Yulian Zeng, Scheduling and Routing of Fly-in Safari Planes Using a Flow-Over-Flow Model , In: M. Jünger, G. Reinelt (Eds.), Facets of Combinatorial Optimization, Series Algorithms and Combinatorics, Springer Verlag, Heidelberg, Seite 419-447, 2013.