应用网络流模型解决航班衔接问题
Solving Flight Conflict Problem with Network Flow Model
-
摘要: 针对单枢纽机场航线结构的特点,以所需飞机数最少为目标,提出了一种描述航班衔接问题的图论模型 及优化算法。首先将航班衔接问题转化为航班节的衔接问题,并建立一个描述航班节衔接问题的二部图,将航 班衔接问题转化为二部图的最大匹配问题,然后由二部图生成一个具有单源汇网络特征的辅助图,利用Ford- Fulkerson算法求该网络的最大流,进而得到二部图的最大匹配,从而得到了一个需用飞机数最少的航班节衔接 方案,为利用计算机自动编制并优化航班衔接方案提供了一种可行方法。并且通过调整过站时间上限,可以得 出不同的航班衔接方案,为制订生产计划提供了必要的灵活性。
-
关键词:
- 建立模型 /
- 航班衔接 /
- 单枢纽航线结构 /
- 二部图的最大匹配 /
- Ford-Fulkerson算法
Abstract: 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
点击查看大图
计量
- 文章访问数: 1345
- HTML全文浏览量: 62
- PDF下载量: 192
- 被引次数: 0