Models and solution methods for the generation of flight schedules (Q2723566)

Aus der Zusammenfassung: In dieser Arbeit beschäftigen wir uns mit dem Problem der Generierung von Flugplänen. Speziell betrachten wir das Problem der Generierung von Charterflugplänen. Nach einer formalen Beschreibung des in der Literatur kaum behandelten Problems stellen wir Vergleiche mit ähnlichen Pro\-ble\-men an. Wir entwickeln zunächst eine einfache ``Network Design''-Mo\-del\-lie\-rung und diskutieren eine Kanten-basierte Formulierung des Problems. Mit der Dantzig-Wolfe-Zerlegungs-Idee geben wir schließlich eine Pfad-basierte Formulierung als lineares gemischtes \(0-1\)-Programm an. Ein Schwer\-punkt dieser Arbeit liegt auf den komplexitätstheoretischen Be\-trach\-tun\-gen des Problems. Ein NP-Vollständigkeitsbeweis für die einfache Version des Flugplangenerierungsproblems wird präsentiert, der auf einer Reduktion von 3-Partition basiert. Ein wesentlicher Inhalt ist auch die realitätsnähere Modellierung des Problems und die Entwicklung dafür geeigneter Lösungsverfahren.