基于最少可用飞机数的航班编组计划

研究了航空公司在运力紧张状况下的航班编组计划问题.首先根据单枢纽航线结构的特点,将航班编组计划问题转化为在枢纽机场的航班节编组问题,然后通过构造描述航班节间衔接关系的传递图,并利用传递图与其对应无向偶图的关系,将需用飞机数最少的航班节编组计划问题转化为求对应无向偶图的最小权最大匹配,从而构造出一个解决运力紧张状况下航班编组计划的多项式算法.最后通过一个算例说明了该算法的应用.

Airliner Flight Connecting Scheduling Based on Minimum Fleet Available

This paper studies airliner flight connecting scheduling when short of enough fleet available. Firstly, according to the character of single hub and spokes network which widely used in Chinese airliners, an new concept called "flight pairing" is defined, by which the flight connecting problem is transferred to flight-pairing connecting problem; Secondly, by constructing transferring graph and corresponding bipartite graph describing flight-pairing-link property, the flight pairing connecting problem based on minimum fleet available is transferred to a minimum weight maximum matching problem, which can be solved by ford-falkson algorithm; Finally, an example is analyzed to demonstrate the application of this algorithm. The computerizing complexity of this algorithm is O(Kn~4).