Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

Solving large scale crew pairing problems [Elektronische Ressource] / vorgelegt von Van Hoai Tran

159 pages
Ajouté le : 01 janvier 2005
Lecture(s) : 12
Signaler un abus

INAUGURAL-DISSERTATION
zur
Erlangung der Doktorwurde
der
Naturwissenschaftlich-Mathematischen Gesamtfakult at
der
Ruprecht-Karls-Universit at Heidelberg
vorgelegt von
Ingenieur-Informatik Van Hoai Tran
aus Quang Tri, Vietnam
Tag der mundlic hen Prufung: 2. Juni 2005Thema
Solving Large Scale
Crew Pairing Problems
Gutachter: Prof. Dr. Gerhard Reinelthter: Prof. Dr. Dr. h. c. Hans Georg BockAbstract
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 nd an optimal way
to partition igh ts 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 popularNP-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 prob-
lems, 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 signi can tly 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 to-
gether.
Utilizing the available computing resources to deal with large scale crew pairing
problems as e ectiv e 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 e ort, 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 speci c 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 di cult 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.Zusammenfassung
Im operativen Betrieb von Fluglinien stellt das Crew-Pairing-Problem eine der
gr ossten Herausforderungen dar. Dieses Problem besteht darin, ausgehend von einem
Flugplan, eine optimale Aufteilung der Fluge des Flugplans zu nden, ohne aber Regeln
und Vorschriften zu verletzen, die von der Fluggesellschaft eingehalten werden mussen.
Crew-Pairing ist Gegenstand intensiver Forschung im Bereich der Mathematik und der
mathematischen Informatik. Die besondere Schwierigkeit resultiert aus der hohen An-
zahl unterschiedlich formulierter nichtlinearer Kostenfunktionen und Nebenbedingun-
gen. Diese machen die Entwicklung einer generischen, allgemein anwendbaren Methode
sehr problematisch.
Ein bekannter Ansatz zur Behandlung der auftretenden Nichtlinearit aten ist die
Umformulierung des kombinatorischen Crew-Pairing-Problems in ein Set-Partitioning
Problem, welches wiederum eines der am intensivsten studiertenNP-schweren Prob-
leme ist. Viele spezielle Strukturen des Set-Partitioning-Problems sind seit Jahrzehn-
ten Forschungsthema und fanden bereits Anwendung bei der L osung von Crew-Pairing-
Problemen. Allerdings steigt die Komplexit at des Problems mit der Gr osse der Flugpl ane
stark an. Dies liegt nicht nur an der mathematischen Umformulierung, sondern ins-
besondere auch an den Methoden, die eingesetzt werden, um die resultierenden Set-
Partitioning-Probleme zu l osen. Dabei ist das schnelle und zuverl assige Au nden
von L osungen fur sehr grosse Probleme von zunehmender Bedeutung fur die Flugge-
sellschaften, gerade vor dem Hintergrund der aktuellen Krise in der Luftfahrt und dem
daraus resultierenden steigenden Kostendruck. Das schnelle und zuverl assige Au nden
von L osungen 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 au g eingesetzte Preprocessing-Techniken, Cutting-Plane Methoden, sowie spezielle
Heuristiken fur das Crew-Pairing Problem. Die Implementierung dieses Schemas l ost
kleine und mittelgrosse Probleme sehr gut. Fur sehr grosse Probleme allerdings reicht
dieser Ansatz nicht aus. Hierfur wurde ein spezieller Branch-and-Price Ansatz entwick-
elt, der mit hochdimensionalen Nebenbedingungsmatrizen umgehen kann. Dabei wer-
den in der vorliegenden Arbeit Nachteile von Standardverfahren zur Column-Generation
durch den Einsatz von stablilisierten Column-Generation-Verfahren kompensiert, fur
die eine problemspezi sc he Parametrierung vorgestellt wird. Die Rechenzeit fur betra-
chtete Probleme konnte mit dieser Technik um den Faktor drei reduziert werden.
Darub erhinaus wurde zus atzlich zu den ublic hen Leistungsmerkmalen grosser Wert
auf die Erweiterbarkeit der Methoden gelegt. Dies ist ein wichtiger Aspekt in Hinblick
auf reale, sehr grosse Probleme. Eine heuristische L osung spezi sc her Crew-Pairing
Probleme kann dann relativ leicht durch Anpassen der Programmparameter und durch
die Kombination der erw ahnten Methoden erhalten werden.
Ein weiteres Ziel dieser Arbeit ist die m oglichst e ektiv e Nutzung vorhandener
Rechnerressourcen beim L osen von grossen Crew-Pairing-Problemen. Eine neue Bib-
liothek von Parallelisierungsroutinen wurde entwickelt, um zukunftig das Bearbeitenvon solchen kombinatorischen Optimierungsaufgaben zu erleichtern und zu beschleu-
nigen. Mit nur geringem Aufwand kann nun ein sequentielles Programm auf einen
Parallelrechner migriert werden. Die Bibliothek bietet mehrere Load-Balancing Meth-
oden und Programmparameter an, um die Parallelisierung an das spezi sc he 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 ub ertragen, dessen Berechnung im ub ergeordneten
Branch-and-Price Verfahren die gr ossten Schwierigkeiten bereitet. S amtliche Paral-
lelisierungsans atze zeigen in den betrachteten Beispielen gute Ergebnisse. Mit Hilfe der
aktuellen Implementierung kann eine optimale L osung grosser Crew-Pairing Probleme
innerhalb von Minuten gefunden werden, w ahrend bisherige Methoden eine Rechenzeit
von bis zu Stunden aufweisen.Contents
Introduction 1
Outline of the thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1 Notations and Foundations 5
1.1 Linear Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 Graph Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3 Convex Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Polyhedral Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5 The Simplex Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6 Integer Programming . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.7 Branch-and-Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.8 Parallel Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2 The Crew Pairing Problem 17
2.1 Airline Management Operations . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Characteristics of the Crew Pairing Problem . . . . . . . . . . . . . . . 19
2.3 Literature Survey . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Pairing generation . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3.2 Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4 A Case Study: Vietnam Airlines . . . . . . . . . . . . . . . . . . . . . . 28
3 A Branch and Cut Approach 33
3.1 Set Partitioning Model . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.1.1 Set packing and set covering models . . . . . . . . . . . . . . . . 34
3.1.2 Crew pairing to set partitioning problem . . . . . . . . . . . . . 36
3.2 Facial Structure of Set Partitioning Polytope . . . . . . . . . . . . . . . 38
3.2.1 Set packing facets . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.2.2 Set covering facets . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.3 Computational Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.1 Data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.3.2 Preprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.3.3 Branch-and-bound . . . . . . . . . . . . . . . . . . . . . . . . . 48
i3.3.4 Cutting plane generation . . . . . . . . . . . . . . . . . . . . . . 50
3.3.5 Primal heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 53
3.3.6 Computational results . . . . . . . . . . . . . . . . . . . . . . . 55
4 A Branch-and-Price Approach 64
4.1 Column Generation Method . . . . . . . . . . . . . . . . . . . . . . . . 64
4.1.1 Column generation for linear programs . . . . . . . . . . . . . . 65
4.1.2 Dantzig-Wolfe decomposition principle . . . . . . . . . . . . . . 66
4.1.3 Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
4.2 Pricing Subproblem in Crew Pairing Problem . . . . . . . . . . . . . . 69
4.2.1 The resource constrained shortest path problem . . . . . . . . . 71
4.2.2 K shortest paths problem . . . . . . . . . . . . . . . . . . . . . 73
4.2.3 Constraint logic programming . . . . . . . . . . . . . . . . . . . 74
4.2.4 Hybrid approach . . . . . . . . . . . . . . . . . . . . . . . . . . 75
4.3 Computational Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.1 Test problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
4.3.2 Initial solution . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4.3.3 Branching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.4 Pricing subproblem . . . . . . . . . . . . . . . . . . . . . . . . . 78
4.3.5 Primal heuristics . . . . . . . . . . . . . . . . . . . . . . . . . . 81
4.3.6 Computational results . . . . . . . . . . . . . . . . . . . . . . . 83
4.4 Stabilized Column Generation Method . . . . . . . . . . . . . . . . . . 86
4.4.1 Generalized stabilized column generation method . . . . . . . . 88
4.4.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . 90
5 Parallel ABACUS 100
5.1 Aspects of Parallelization . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.1.1 Communication library . . . . . . . . . . . . . . . . . . . . . . . 100
5.1.2 Task granularity . . . . . . . . . . . . . . . . . . . . . . . . . . 101
5.1.3 Pool of nodes and load balancing . . . . . . . . . . . . . . . . . 103
5.1.4 Object oriented design . . . . . . . . . . . . . . . . . . . . . . . 104
5.1.5 Object serialization . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.2 New Communication Design . . . . . . . . . . . . . . . . . . . . . . . . 106
5.2.1 Termination detection . . . . . . . . . . . . . . . . . . . . . . . 110
5.3 New Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
5.4 Parallel Set Partitioning Solver . . . . . . . . . . . . . . . . . . . . . . 113
5.4.1 Parallelizing the sequential code . . . . . . . . . . . . . . . . . . 113
5.4.2 Computational results . . . . . . . . . . . . . . . . . . . . . . . 114
6 A Parallel Pricing for the Branch and Price Approach 125
6.1 Parallelizing Sequential Pricing Algorithms . . . . . . . . . . . . . . . . 125
6.2 Aspects of Implementation . . . . . . . . . . . . . . . . . . . . . . . . . 127
6.3 Computational Results . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
ii7 Conclusions 133
Index 144
iii

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin