应用网络流模型解决航班衔接问题

摘要

针对单枢纽机场航线结构的特点,以所需飞机数最少为目标,提出了一种描述航班衔接问题的图论模型及优化算法.首先将航班衔接问题转化为航班节的衔接问题,并建立一个描述航班节衔接问题的二部图,将航班衔接问题转化为二部图的最大匹配问题,然后由二部图生成一个具有单源汇网络特征的辅助图,利用Ford-Fulkerson算法求该网络的最大流,进而得到二部图的最大匹配,从而得到了一个需用飞机数最少的航班节衔接方案,为利用计算机自动编制并优化航班衔接方案提供了一种可行方法.并且通过调整过站时间上限,可以得出不同的航班衔接方案,为制订生产计划提供了必要的灵活性.