Flugreiseplanung

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.

Unsere Webseite verwendet Cookies. Diese haben zwei Funktionen: Zum einen sind sie erforderlich für die grundlegende Funktionalität unserer Website. Zum anderen können wir mit Hilfe der Cookies unsere Inhalte für Sie immer weiter verbessern. Hierzu werden pseudonymisierte Daten von Website-Besuchern gesammelt und ausgewertet. Das Einverständnis in die Verwendung der technisch nicht notwendigen Cookies können Sie jeder Zeit wiederrufen. Weitere Informationen erhalten Sie auf unseren Seiten zum Datenschutz.

Erforderlich

Diese Cookies werden für eine reibungslose Funktion unserer Website benötigt.

Statistik

Für den Zweck der Statistik betreiben wir die Plattform Matomo, auf der mittels pseudonymisierter Daten von Websitenutzern der Nutzerfluss analysiert und beurteilt werden kann. Dies gibt uns die Möglichkeit Websiteinhalte zu optimieren.

Name Zweck Ablauf Typ Anbieter
_pk_id Wird verwendet, um ein paar Details über den Benutzer wie die eindeutige Besucher-ID zu speichern. 13 Monate HTML Matomo
_pk_ref Wird benutzt, um die Informationen der Herkunftswebsite des Benutzers zu speichern. 6 Monate HTML Matomo
_pk_ses Kurzzeitiges Cookie, um vorübergehende Daten des Besuchs zu speichern. 30 Minuten HTML Matomo