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

第37卷第2期 西南交通大学学报 Vol37№2 0FSOUrHWESTJ队01roNGUNⅣERSITY ADr．龇 2002年4月 JOURNAL 文章缩号：0258．2724(2002)02_0∞3Ⅸ 应用网络流模型解决航班衔接问题 孙宏 (西南交通大学交通运输学院，四川成都610031) 摘要：针对单枢纽机场航线结构的特点，以所需飞机数最少为目标，提出了一种描述航班衔接问题的图论模型 及优化算法。首先将航班衔接问题转化为航班节的衔接同置。并建立一十描述航班节衔接问题的二部圈，将航 班衔接问题转化为二部图的最大匹配问题，然后由二部图生成一个具有单嚣汇网络特征的辅助圉，利用F州- F血e咖算法术该网络的最大漉，进而得到二部圉的最大匹配。从而得到了一十需用飞机数量步的航班节衡接 方案，为利用计算机自动缩错并优化航班衔接方案提供了一种可行方法。并且通过谓整过站时闻上限，可以褥 出不同的航班衔接方案，为制订生产计盘f提供了必要的是活性。 关■词：建立模型；航班衔接；单枢纽航线结构；二部图的量大匹配；MFul№算法 中田分类号：u拼．1 文献标识码：^ C加伍ctPmM哪wimN咖orkFIowModeI SoIvingFH吕ht SUN Ho鸭 BⅡd ofTh伍c (sch∞l Tr帅叩．．SoII出w竹tJ讪恤gu缸他蹲竹，ch朗du61003l，chi∞) schedulejstlle Ah咖lcl：F1i曲卜00nn妯gb聃i鲁。f删■ngI删dneⅣ。ducⅡon一衄of砌鹏opem如n mis ch盯ac￡e矗s6cs。f f。rairline 8衄j咖rd camp“龆．h1p印盯，髓cmdi玎瞎蕾口出e sjnglehnb矗lld即吐e moc瑚衄d 丑ig}ltne栅mk，BbipB—te伊phic i捃op￡in垃碰叩_丘l鲥thmam小心Pedf醯ⅡiglI￡ iIia t0miIIjmi船出cnumb盯of hub砌8poke肿fw∞k8ystem 8irc袖坤qIlired．F妇，￡lIe connecdng into isc咖Verced 8 p丑ir王ngoonnec血gprnbl锄，衄d flight·connec血gproblem tlIe丑i曲t hip8rcite de model 窘mphic Bc】dbitlgthe丑i曲tp曲证gc0硼钟血g印)蚰咖i8bu丑t．1‰，衄0Pd唯I丑i曲t- to iB岫md妇dthe tlle ∞nnedngpInhleln maxim哪m酗ingpIo}l哪0fbip积ite睁a—曲model． B删∞e ba僦on出e an