German Title: Lösung von großen Crew-Pairing-Problemen

Preview

PDF, English Download (1MB) | Terms of use

Abstract

Crew pairing is one of the most critical processes in airline management operations. Taking a timetable as input, the objective of this process is to find an optimal way to partition flights of the timetable without breaking rules and regulations which are enforced by an airline. The problem has attracted many scientists in recent decades. The main challenge is that there is no general method to work well with all kinds of non-linear cost functions and rules. In order to overcome the non-linearity, the thesis follows a main idea to transfer this combinatorial optimization problem to a set partitioning problem which is one of the most popular \np-hard problems. Although this problem has been studied throughout decades, it becomes more complicated with the increasing size of the input. The complication is induced not only in the transformation process, but also in the methods to solve the resulting set partitioning problem. Finding quickly a good and robust solution for large scale problems is more and more critical to airlines. They are the main targets which are studied by the thesis. The thesis presents exact methods which are usually based on a branch-and-bound scheme. A branch-and-cut approach applies preprocessing techniques, cutting plane generation methods, and heuristics which are suitable for crew pairing problems. The implementation can solve small and medium sized problems. However, for large problems, a branch-and-price approach is necessary to cope with huge constraint matrices. The thesis improves the weakness of standard column generation methods by applying stabilized column generation variants with sophisticated parameter control schemes into this approach. The computation time is reduced significantly by a factor of three. Moreover, the work also focuses on the extensibility of the methods. This is quite important for large scale problems. Then, we easily obtain a heuristic solution method by controlling running parameters of the presented approaches or combining them together. Utilizing the available computing resources to deal with large scale crew pairing problems as effective as possible is also a target of the thesis. A new parallel branch-and-bound library is developed to support scientists to solve combinatorial optimization problems. With little effort, they can migrate their sequential codes to run on a parallel computer. The library contains several load balancing methods and control parameters in order to work well with specific problems. The sequential branch-and-cut code to solve set partitioning problems is parallelized by the library and introduces a good speedup for most crew pairing test problems. Parallel computing is also used to solve a so-called pricing subproblem, which is the most difficult problem in the branch-and-price approach, with a nearly linear speedup. The implementation solves large scale crew pairing problems to optimality within minutes, whereas previous methods ended up in the range of hours or more.

Translation of abstract (German)

Im operativen Betrieb von Fluglinien stellt das Crew-Pairing-Problem eine der grössten Herausforderungen dar. Dieses Problem besteht darin, ausgehend von einem Flugplan, eine optimale Aufteilung der Flüge des Flugplans zu finden, ohne aber Regeln und Vorschriften zu verletzen, die von der Fluggesellschaft eingehalten werden müssen. Crew-Pairing ist Gegenstand intensiver Forschung im Bereich der Mathematik und der mathematischen Informatik. Die besondere Schwierigkeit resultiert aus der hohen Anzahl unterschiedlich formulierter nichtlinearer Kostenfunktionen und Nebenbedingungen. Diese machen die Entwicklung einer generischen, allgemein anwendbaren Methode sehr problematisch. Ein bekannter Ansatz zur Behandlung der auftretenden Nichtlinearitäten ist die Umformulierung des kombinatorischen Crew-Pairing-Problems in ein Set-Partitioning Problem, welches wiederum eines der am intensivsten studierten NP-schweren Probleme ist. Viele spezielle Strukturen des Set-Partitioning-Problems sind seit Jahrzehnten Forschungsthema und fanden bereits Anwendung bei der Lösung von Crew-Pairing-Problemen. Allerdings steigt die Komplexität des Problems mit der Grösse der Flugpläne stark an. Dies liegt nicht nur an der mathematischen Umformulierung, sondern insbesondere auch an den Methoden, die eingesetzt werden, um die resultierenden Set-Partitioning-Probleme zu lösen. Dabei ist das schnelle und zuverlässige Auffinden von Lösungen für sehr grosse Probleme von zunehmender Bedeutung für die Fluggesellschaften, gerade vor dem Hintergrund der aktuellen Krise in der Luftfahrt und dem daraus resultierenden steigenden Kostendruck. Das schnelle und zuverlässige Auffinden von Lösungen ist Ziel der vorliegenden Arbeit. Es werden exakte Methoden vorgestellt, die auf dem allgemeinen Branch-and-Bound Schema basieren. Ein hier vorgestellter Branch-and-Cut Ansatz verwendet häufig eingesetzte Preprocessing-Techniken, Cutting-Plane Methoden, sowie spezielle Heuristiken für das Crew-Pairing Problem. Die Implementierung dieses Schemas löst kleine und mittelgrosse Probleme sehr gut. Für sehr grosse Probleme allerdings reicht dieser Ansatz nicht aus. Hierfür wurde ein spezieller Branch-and-Price Ansatz entwickelt, der mit hochdimensionalen Nebenbedingungsmatrizen umgehen kann. Dabei werden in der vorliegenden Arbeit Nachteile von Standardverfahren zur Column-Generation durch den Einsatz von stablilisierten Column-Generation-Verfahren kompensiert, für die eine problemspezifische Parametrierung vorgestellt wird. Die Rechenzeit für betrachtete Probleme konnte mit dieser Technik um den Faktor drei reduziert werden. Darüberhinaus wurde zusätzlich zu den üblichen Leistungsmerkmalen grosser Wert auf die Erweiterbarkeit der Methoden gelegt. Dies ist ein wichtiger Aspekt in Hinblick auf reale, sehr grosse Probleme. Eine heuristische Lösung spezifischer Crew-Pairing Probleme kann dann relativ leicht durch Anpassen der Programmparameter und durch die Kombination der erwähnten Methoden erhalten werden. Ein weiteres Ziel dieser Arbeit ist die möglichst effektive Nutzung vorhandener Rechnerressourcen beim Lösen von grossen Crew-Pairing-Problemen. Eine neue Bibliothek von Parallelisierungsroutinen wurde entwickelt, um zukünftig das Bearbeiten von solchen kombinatorischen Optimierungsaufgaben zu erleichtern und zu beschleunigen. Mit nur geringem Aufwand kann nun ein sequentielles Programm auf einen Parallelrechner migriert werden. Die Bibliothek bietet mehrere Load-Balancing Methoden und Programmparameter an, um die Parallelisierung an das spezifische Problem anzupassen. Die sequentielle Branch-and-Cut Methode liegt ebenfalls als parallelisierte Variante in der Bibliothek vor. Weiterhin wurden Parallelisierungstechniken auf das sogenanntes Pricing-Unterproblem übertragen, dessen Berechnung im übergeordneten Branch-and-Price Verfahren die grössten Schwierigkeiten bereitet. Sämtliche Parallelisierungsansätze zeigen in den betrachteten Beispielen gute Ergebnisse. Mit Hilfe der aktuellen Implementierung kann eine optimale Lösung grosser Crew-Pairing Probleme innerhalb von Minuten gefunden werden, während bisherige Methoden eine Rechenzeit von bis zu Stunden aufweisen.