摘要
针对单枢纽机场航线结构的特点 ,以所需飞机数最少为目标 ,提出了一种描述航班衔接问题的图论模型及优化算法。首先将航班衔接问题转化为航班节的衔接问题 ,并建立一个描述航班节衔接问题的二部图 ,将航班衔接问题转化为二部图的最大匹配问题 ,然后由二部图生成一个具有单源汇网络特征的辅助图 ,利用Ford Fulkerson算法求该网络的最大流 ,进而得到二部图的最大匹配 ,从而得到了一个需用飞机数最少的航班节衔接方案 ,为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限 ,可以得出不同的航班衔接方案 ,为制订生产计划提供了必要的灵活性。
Flight connecting schedule is the basis of making routine production plan of airline operation for airline companies. In this paper, according to the structural characteristics of single hub and spoke flight network, a bipartite graphic model and its optimization algorithm are developed for flight connecting in a hub and spoke network system to minimize the number of aircraft required. First, the flight connecting problem is converted into the flight pairing connecting problem, and a bipartite graphic model describing the flight pairing connecting problem is built. Thus, an optimal flight connecting problem is transformed to the maximum matching problem of the bipartite graphic model. Then, an assistant graph with single source and sink is created based on the bipartite graphic model. The maximum matching of the bipartite graph is obtained by calculating the maximum inflow with the Ford Fulkerson algorithm, and a flight connecting schedule with minimum craft number is accordingly produced. This provides a feasible method to computerize the work of making and optimizing a flight connecting schedule. Moreover, through adjusting the upper limit of the time of passing depots, different flight connecting schedules can be obtained. This brings flexibility to the making of production plans.
出处
《西南交通大学学报》
EI
CSCD
北大核心
2002年第2期223-226,共4页
Journal of Southwest Jiaotong University
基金
中国民航科研基金资助项目 (2 0 0 0 - 18)
