- Title
- Integrated aircraft routing, crew pairing, and tail assignment
- Creator
- Ruther, Sebastian
- Relation
- University of Newcastle Research Higher Degree Thesis
- Resource Type
- thesis
- Date
- 2013
- Description
- Research Doctorate - Doctor of Philosophy (PhD)
- Description
- Airline scheduling is the process of scheduling available aircraft and crews such that all flights that an airline operates are serviced. The goal is to develop a minimum-cost plan in which all aircraft and crews have tasks assigned to them. Aircraft operate sequences of flights, so-called routes, that must not violate maintenance requirements. Crews have pairings assigned to them, which are sequences of flights that respect several rules regarding work-load and rest periods. Due to its complexity, the airline scheduling is typically done sequentially, decomposing the entire problem into six more tractable sub-problems: the schedule design, fleet assignment, aircraft routing, crew pairing, crew rostering, and the tail assignment problem. The schedule design problem determines which flights should be offered, while the fleet assignment problem assigns the flights to aircraft types, matching aircraft capacity and expected demand as much as possible. The aircraft routing problem generates generic aircraft routes, whereas the crew pairing problem creates generic pairings. These pairings are then put together to form monthly rosters in the crew rostering problem. Finally, in the tail assignment problem, the generic routes are assigned to individual aircraft. An issue of the sequential approach is that later stages depend on decisions made in earlier stages. For example, the initial location, time since last maintenance checks of each required type, and usage history of the individual aircraft is not known with certainty in the aircraft routing problem. Thus, in the tail assignment problem, an assignment of the generic routes to available aircraft may not be possible without making costly adjustments to the routes. Another major disadvantage is caused by the long lead times and long planning horizons of the individual stages. Usually the aircraft routing and crew pairing problems are solved several weeks or even months before putting a plan into action, the so-called day of operations. As a result, routes and pairings will be formed based on forecasts and historical flight data. Often the circumstances do not eventuate according to the predictions, requiring modifications to routes and pairings close to or on the day of operations. While disruptive events on the day of operations will still occur, and have to be dealt with accordingly, many events leading up to that date may be considered if scheduling closer to the day of operations. For example, a change in workforce between solving the crew pairing problem and the day of operations may invalidate the crew pairing solution. Another example is that often minor equipment failures, such as a defective toilet, are tolerated if an aircraft's scheduled maintenance is not too far in the future. However, these issues may accumulate, possibly resulting in additional unscheduled maintenance. When scheduling close to the day of operations, these minor failures are largely known and can be accounted for by scheduling maintenance earlier than originally anticipated. Scheduling close to the day of operations also enables re-visiting fleeting decisions. The fleet assignment problem is solved months in advance, at which point demand is largely unknown. The literature indicates that the majority of the demand for each flight is realised during the last weeks prior to flight departure and that profit can be increased significantly if the fleeting decisions are revisited. However, since the aircraft routing problem is solved separately for each aircraft fleet, reassigning a flight to a different fleet due to updated demand information will invalidate the aircraft routes. Scheduling close to the day of operations overcomes this obstacle as routes are generated when most of the demand has been realised. Naturally, information becomes significantly more accurate as the day of operations approaches. The paradigm this thesis is based on allows an integrated aircraft routing, crew pairing, and tail assignment problem to be solved only a few days before the day of operations. At that point in time, it should be possible to predict location and status of crews and aircraft more accurately. In this paradigm, crews are not told the exact pairings they will be operating after the crew rostering phase; they will only be notified of days on and off. We then form "crew blocks", in which we aggregate all crews that have the same work period, i.e. consecutive working days, and are based at the same location. Then, for the purpose of our mathematical model, the crews represented by a crew block are considered identical. The solver will generate an appropriate number of pairings for each crew block. Since the work periods differ between crew blocks, we have to generate pairings for each individual crew block. Solving an integrated model this close to the day of operations means we can generate routes specifically for each aircraft, thereby eliminating the need to later assign routes to aircraft. The routes consider the location and maintenance requirements of the individual aircraft. Unlike standard aircraft routing, we consider all maintenance requirements that the aircraft has during the planning horizon. A downside of scheduling this close to the day of operations is that other processes and company divisions may be affected negatively. For example maintenance planning and technician rostering have to be carried out more timely, and, as already mentioned, crew members have to be more flexible as their final pairings are only revealed four days in advance. This may require higher financial compensation, however, we believe this to be offset by the benefits of using more accurate information when scheduling routes and pairings. To solve the integrated aircraft routing, crew pairing, and tail assignment problem, we use mathematical programming, more precisely we develop a column generation formulation in which the master problem ensures that all flights are covered by one aircraft and one crew. Additionally, it contains constraints that model the interaction of aircraft and crew along short and restricted connections: on short connections a crew must stay with an aircraft because insufficient time is available to physically move to another gate. Restricted connections are likely to propagate flight delays; staying with an aircraft avoids spreading the delay, thus increasing schedule robustness. All maintenance and crewing rules are relegated to the pricing problems, which are modeled as resource constrained shortest path problems with replenishments, where the replenishments represent maintenance checks for aircraft or rest periods for crews. The specific rules considered in our problem require several extensions to the standard resource constrained shortest path problems with replenishments. We present a labelling algorithm that is capable of handling these extensions. Furthermore, we develop a preprocessing procedure that significantly reduces the computational effort in the labelling algorithm. To obtain integer solutions to the integrated problem, we develop a branch-and-price algorithm based on follow-on branching. We evaluate the fitness of several column generation acceleration strategies to solve our problem by conducting numerical experiments on real world instances. Since we generate routes specifically for each aircraft and pairings specifically for each crew block, we must solve a large number of pricing problems. We develop several strategies to address this challenge. In the most straight-forward strategy, we solve all pricing problems in each column generation iteration. Another option is to solve only a subset of the pricing problems per iteration where the pricing problems are in a fixed order. In a third strategy, we chose a subset based on how well each pricing problem performed recently, and on the current state of the overall problem. The impact of these strategies on solution time, convergence of the column generation procedure, and the quality of the dual bound is investigated. We present detailed numerical results for real world and artificial instances of varying sizes. As perhaps the strongest methodological innovation in the thesis, we develop aggregated forms of pricing problems, which we call "superimposed pricing problems". These pricing problems can be solved instead of the many individual pricing problems as they fulfill the requirements of column generation, that is to generate the most negative reduced cost column among the represented pricing problems or prove that no such column exists. These superimposed pricing problems are slightly larger than the original problems but a much smaller number needs to be solved. We present numerical results, in which we compare their performance and impact on the overall branch-and-price algorithm to that of the regular pricing problem selection strategies. Lastly, we combine the ideas by solving only a subset of the superimposed pricing problems.
- Subject
- airline scheduling; aircraft routing; crew pairing; tail assignment; branch-and-price
- Identifier
- http://hdl.handle.net/1959.13/1038800
- Identifier
- uon:13585
- Rights
- Copyright 2013 Sebastian Ruther
- Language
- eng
- Full Text
- Hits: 1313
- Visitors: 2180
- Downloads: 1006
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT01 | Abstract | 223 KB | Adobe Acrobat PDF | View Details Download | ||
| View Details Download | ATTACHMENT02 | Thesis | 7 MB | Adobe Acrobat PDF | View Details Download |