CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

The Tail Assignment problem

Mattias Grönkvist (Institutionen för data- och informationsteknik, Datavetenskap (Chalmers))
51st Airline Group of the International Federation of Operational Research Societies Annual Proceedings - Annual Symposium and Study Group Meeting, AGIFORS 2011; Antalya; Turkey; 10 October 2011 through 14 October 2011 Vol. 3 (2011), p. 1509-1804.
[Konferensbidrag, refereegranskat]

The Aircraft Assignment problem is the problem of assigning flights to aircraft in such a way that some operational constraints are satisfied, and possibly that some objective function is optimized. We propose an approach to aircraft assignment which captures all operational constraints, including minimum connection times, airport curfews, maintenance, and preassigned activities. It also allows multiple fleet optimization, and can model various types of objective functions, which sets it apart from most other aircraft assignment approaches. The name we have chosen for our approach is the Tail Assignment problem. The tail assignment problem is general in the sense that it can model the entire aircraft planning process, from fleet assignment to the day of operation. We develop solution methods based on mathematical programming and constraint programming, and also show how the methods can be combined. The resulting hybrid solution method is general in the sense that it can be used both to quickly find initial solutions and to find close to optimal solutions, if longer running times are allowed. We present a mathematical programming approach based on column generation, conduct thorough computational experiments to show the impact of various implementation choices on running time and convergence, and present heuristics to find integer solutions. We show how constraint programming can be used stand-alone to quickly produce solutions to the tail assignment problem, and to substantially improve the computational performance of the column generation algorithm. Preprocessing algorithms based on constraint programming are presented that can reduce the size of the problem substantially more than standard balance-based preprocessing, resulting in major speedups and increased solution quality. Our complete solution approach combines column generation, constraint programming and local search. Finally, as proof of concept, we present modeling examples and computational results for a selection of real-world tail assignment instances, demonstrating how our model and solution methods can be used to increase operational robustness, enforce equal aircraft utilization, and decrease aircraft leasing costs. Our tail assignment system is currently in use at two medium-sized airlines.

Nyckelord: Aircraft routing; Airline optimization; Column generation; Constraint programming; Fleet planning; Hybrid optimization; Tail assignment

Denna post skapades 2015-05-05.
CPL Pubid: 216454