In this paper the DARSP (daily aircraft routing and scheduling problem) is considered. It consists of determining daily schedules which maximize the anticipated profits derived from the aircraft of a heterogeneous fleet. This fleet must cover a set of operational flight legs with known departure time windows, durations and profits according to the aircraft type. Two models for this problem are presented: a Set Partitioning type formulation and a time constrained multicommodity network flow formulation. It is described the network structure of the subproblem when a column generation technique is applied to solve the linear relaxation of the first model and when a Dantzig-Wolfe decomposition approach is used to solve the linear relaxation of the second model. The linear relaxation of the first model provides upper bounds. Integer solutions to the overall problem are derived through branch-and-bound. By exploiting the equivalence between the two formulations, various optimal branching strategies compatible with the column generation technique are proposed. Finally the paper reports computational results obtained on data provided by two different airlines. These results show that significant profit improvement can be generated by solving the DARSP using the approach and that this can be obtained in a reasonable amount of CPU time.
Daily aircraft routing and scheduling
Der tägliche Flugzeugflottenplan mit Gewinnmaximierung
Management Science ; 43 , 6 ; 841-855
1997
15 Seiten, 2 Bilder, 3 Tabellen, 24 Quellen
Article (Journal)
English
A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem
British Library Online Contents | 2013
|A Lifted Compact Formulation for the Daily Aircraft Maintenance Routing Problem
Online Contents | 2013
|COMBINED AIRCRAFT MAINTENANCE ROUTING AND MAINTENANCE TASK SCHEDULING
European Patent Office | 2016
|Benders Decomposition for Simultaneous Aircraft Routing and Crew Scheduling
British Library Online Contents | 2001
|