不正常航班恢复的一种改进的列生成算法

分析了由飞机资源短缺造成的航班不正常情况,将该问题视为带有容量约束的多个商品的整数最小费用流问题,建立了多商品网络流数学模型。采用列生成算法框架求解该大规模整数规划问题。一般的列生成算法是每次迭代过程只加入一个列,造成迭代次数过多,因而降低了算法效率低。文中采用每次迭代过程中加入多个列,并对加入的多个列应该满足的条件进行了分析。最后给出的算例验证了该方法的正确性和有效性。

Improved Column Generation Algorithm for Disrupted Airline Schedules Recovery

The disrupted airline schedules caused by the shortage of aircraft resources is considered as a multi-commodity integer minimum cost flow with the side constraints, and a mathematic model of multi-commodity network flow is established. The column generation scheme is introduced to solve the integer programming problem. Generally, only one column is added in each iteration for the column generation algorithm, which results in excessive number of iterations, thereby reduces the efficiency of the algorithm. The method of adding more columns in each iteration process is set up, and the requirements which the added multiple columns should meet are analyzed. Finally, an example is given to validate the correctness and efficiency of the method.