Daily Aircraft Routing and Scheduling
研究每日飞机航线与调度问题，提出两种模型（集合划分和带时间约束的多商品网络流），通过列生成和分支定界求解，在两家航空公司的数据上验证了能显著提升利润且计算时间合理。
In this paper we consider the daily aircraft routing and scheduling problem (DARSP). 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. We present two models for this problem: a Set Partitioning type formulation and a time constrained multicommodity network flow formulation. We describe 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, we propose various optimal branching strategies compatible with the column generation technique. Finally we report 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 our approach and that this can be obtained in a reasonable amount of CPU time.