Models and solution methods for the generation of flight schedules
type: Item
instance of: scholarly article
zbMATH Open document ID: 1050.90524
author: Anja Noltemeier
publication date: 2001-07-05T00:00:00Z
full work available at URL: http://www.shaker.de/de/content/catalogue/index.asp
Mathematics Subject Classification ID: 90C08
Mathematics Subject Classification ID: 90B06
Mathematics Subject Classification ID: 90C09
Mathematics Subject Classification ID: 90B35
zbMATH DE Number: 1614827
zbMATH Keywords: charter flight schedules
zbMATH Keywords: linear mixed \(0-1\) programming
zbMATH Keywords: LP relaxation
zbMATH Keywords: branch-and-cut method
zbMATH Keywords: heuristics
zbMATH Keywords: NP-completeness
MaRDI profile type: Publication
title: Models and solution methods for the generation of flight schedules
review text: 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.
description: scientific article; zbMATH DE number 1614827