南 京 航 空 航 天 大 学 学 报 第 卷第 期 年 月!"#$%&'#%$ '$%%$ # ()*++-+ 基于协同决策的多航站楼停机位实时分配算法 刘君强 张马兰 陈鹏超 谢吉伟 左洪福 南京航空航天大学民航学院 南京 + 摘要 针对多航站楼机场停机位实时指派问题 提出了基于协同决策并考虑航空公司时隙交换公平性的机位实时指派算法 该算法将多航站楼资源的可共享性考虑到指派算法中 以最小延误费用原则为约束 采用混合集合规划进行指派模型的建立与求解 该算法在保证多航站楼停机位资源有效共享的前提下 充分实现了航空公司时隙交换的公平性 并且使延误引起的多方成本最小化 算例说明 本文提出的算法可以有效解决多航站楼的机位实时分配问题 关键词 航空运输 协同决策 多航站楼 实时指派 混合集合规划 航班波中图分类号!. 文献标志码 ' 文章编号 -+--+!" #$%&'!!!"# ##"'"%!"#$%&'#%$ '$%%$ +2 &' %%2##-%#$$#%3# %-%##-%#$$#%- %2$33$#$#%2#%"##$%2#$%#42##$$##%#$ 12#%2$2#%##$#$$#%2##&$%33#$%2#$%% 3%%2#4#$#%3 %$"#%2#$$#%#!#%2#3#$%#$2 %- %#%2##%2#5#%2##$$%2##%#$%%#2#5#%2#$% $#&%2##&12##43#$26$%2%%2#33$##%2##%"#&$"#%2##-%#- %3#%-%# $%$3%%%"##$%-%##-%# %#$$#%4# $#%3 072%8 随着民航运输的飞速发展 运输量的快速增长 多航站楼多管理已经成为民航发展的一种趋势 然而这将使得机场运行保障变的更加复杂 机位是机场的核心资源 机位分配是机场日常运行保障中的一个非常重要的工作 高效合理的机位分配方案不仅会给民航运输带来巨大的经济效益 并且在一定程度上可以提高民航运输的安全性 在机场停机位实时指派的问题上 国内外学者已经 -/ 进行了很多模型与算法的相关研究 从已有研究来看 在机位实时指派算法中 仍需综合考虑多航站楼模式 航班波 协同决策 时隙交换公平性以及这 个因素的影响 基金项目 国家自然科学基金 + 重点资助项目 国家自然科学基金委与中国民用航空总局联合 +// 资助项目 中国博士后面上基金 0. 资助项目 中国博士后基金 1+ 资助项目 江苏高校哲学社会科学研究基金 ( 资助项目 收稿日期 --. 修订日期 --/ 通信作者 刘君强 男 博士 讲师 - #
南 京 航 空 航 天 大 学 学 报第 卷 由于运输量增长 许多大型机场都通过扩容的方式来满足需求 其中 航站楼的改扩建使得一个机场多个航站楼的运行模式应运而生 在多航站 - 楼运行中 有很多公共的资源需要共享 如机位 跑道等外场资源 旅客由于转机等原因需要在多个航站楼之间活动 飞机也可能因为调配原因而从一个航站楼转移到另外一个航站楼 因此 机场的运行调度算法必须能够满足以上种种运行上的需求 在多航站楼运行模式下进行资源分配时 必须充分考虑各种资源之间的联动关系才能做到协 调运行 此时 值得注意的是应当将航站楼作为资源分配的一个基本判断依据 首先判断航班机位是否在不同航站楼之间调整 然后根据预先设定的各种规则再进行其他资源的变更 这样才能使系统的处理逻辑相对清晰和简单 为满足日益增长的航空运输需求 航空公司纷纷考虑以航班波的方式进行排班 相应地 枢纽机场针对航班波进行各项航班保障工作 其中就包括 停机位的指派 航班波是指 为实现航班有效衔接 在一个时段安排进港航班 在紧接着的另一个时段安排出港航班 当航班波不受延误影响时 机场资源可以得到高效利用 旅客的中转等待时间大大缩短 但是 如果航班波受到延误航班的影响 旅客的中转时间会大幅度上升 要使航班不受或尽量少受延误航班的影响 则需要实现机场 航空公司和空管的协同决策 然而 目前机场 空管和航空公司大多单独完成各自任务 没有达到协同决策的要求 在实现航空公司与机场的协同决策时 需要考虑到时隙分配和机位指派的先后关系以及相互影响 当航班延误之后 航班所获得的时隙将会改变 但在航空公司不知道后续机位指派方案的前提下 无法判断延误航班获得的时隙方案所对应的最佳机位指派方案是否为所有可能的机位指派方案 时隙交换后 中延误成本最小的 因此 航空公司需要与机场进行协同决策 首先由航空公司给出不同时隙方案 机场给出不同时隙方案下机位指派的延误成本 根据最小延误成本确定最佳时隙交换方案 再将该方案告知航空公司 然而 在总的延误成本最小时还需考虑航空公司间的利益均衡 所以在进行时隙交换时 还要考虑航空公司间的利益均衡性 进行公平的时隙交换 本文在协同决策的基础上综合多航站楼资源共享性 航班波延误最小化 时隙交换公平性等因素 建立机场停机位实时指派模型 并在混合集合规划中实现模型的求解 ( 机位实时分配模型 (( 模型符号 为机位集合 $% 为航班集合 %& 为航班波集合!& ( 为延误航班集合 ( %(%( ' 表示航空公司 ' 的延误航班 ( 表示可交换时隙的延误航班 ( ' 表示航空公司 ' 的可交换时隙数量 1 1 分别为调整前 后航班滑行到停靠机位所需时间 为航班 的乘客数量 $ 表示机位的大小 数字越大 机位越大 表示航班机型的大小 数字越大 机型越大 + 表示同一机位两个航班的最小安全时间间隔 $ 的意义为 若航班 分配到机位 $ 则为 否则为. $ 为机位 $ 空闲的开始时间 $ 为机位 $ 空闲的结束时间 / $ 为航班 到达机位 $ 的时间 $ 航班 离开机位 $ 的时间! 的意义为 若延误航班 处于航班波! 中 则! 为 若延误航班 不处于航班波! 中 则! 为 17 为中转旅客的人数 按照.9 的中转比例计算 中转等待时间人均 /! 3 为延误航班计划所属航班波! 为延误航班实际所属航班波!! 3 (! 为航班波! 的波长 一般航班波波长为 % 表示航站楼 ) 表示航站楼 具有的航班波数量 为有航班波衔接的延误航班数量集合 % * 为没有航班波衔接的延误航班数量集合 % # () 模型表达式 机场停机位实时分配的综合模型如下所示 #+ % $ $1 1 -
第 期 刘君强 等 基于协同决策的多航站楼停机位实时分配算法 (!&!(!!! 3 $% $ $ + % $ + %$! + (!&! + (! & $ $ $ % $ -.$ $. $./ $.$ $ $ $ $ %$ +. 0. (' ( '- 0 / $ $ (!!! 3 %$!!! 3 & -+ 式 为目标函数 表示航班滑行时间和中转等待时间同时得到 式 要求每个航班只分配到一个机位 式 表示了机位使用的唯一性 式 表示一个航班只属于一个航班波 式 表示航班与航班波的对应性 式 + 表示机位与机型大小相匹配 式 表示机位的空闲时间大于最低安全间隔时间 式. 表示机位空闲开始时间应早于航班的到港时间并且机位空闲结束时间应晚于航班离港时间 式 / 表示两个航空公司 航空公司航班数量相当 的可交换时隙的比例值满足区间. 即航空公司时隙交换的公平性约束条件 式 表示有效性约束 式 表示滑行成本权重 和旅客中转成本权重 的和等于 ) 求解方法 混合集合规划 04#$#%3 07 源自逻辑规划与约束规划 是以一阶逻辑与集合推理为算法框架的逻辑求解系统 07 能够将集合运算 量词 布尔逻辑 逻辑函数 日期 时间推理 数值约束等集成于一个系统 实现从实数 整数等数值类型扩充到布尔值 日期 时间集合类型的混合域上的全局推理 以及约束满足问题的建模与求解 此处 集合规划的概念并非指在问题求解中对集合运算符号 集合变量及集合约束的简单使用 而是系统地将集合推理与运筹学算法相结合 以集合变量为主进行问题建模 以基于集合推理的算法为核心进行模型求解 本文采用 07 方法求解下列算法 )( 延误航班的时隙分配步骤 ( 将多航站楼的每个航班波的计划到达时刻按升序排序得到 & :! %! %! ) %! %! %! ) % 即第一个航站楼 % 有 ) 个航班波 第 个航站楼 % 有 ) 个航班波 步骤 ) 根据不同的航站楼 % % 分 次循环 对于每次循环 定义. 为航班波. 包含的延误航班数量 从 1 时刻开始到完成航班波. 需要的时间 定义最大. 值对应的航班波结束时刻为 1 定义 1 为在 1 时刻未结束而在 1 时刻结束的下一个航班波结束时刻 1 1 有 : 1 1 次循环 步骤 * 根据不同的航站楼 % % 分 对于每次循环 将最大. 值对应航班波内的航班按可交换时隙的方式指派到 时刻之前的时隙中 个航站楼各自的有航班波衔接的延误航班数量集合为 : % * % * * % 没有航班波衔接的延误航班数量集合为 : % # % # # % 则该步骤得到的时隙分配方案 的数量为 对于有航班波衔接的延误航班 % * ; % * ;;% * 对于没有航班波衔接的延误航班 % # ;%# # ;% 步骤 + 将指派完成的航班波从集合 1 中去除 重新进行航班波排序 重复步骤 最终可输出所有延误航班的时隙分配方案 )) 停机位实时分配步骤 ( 读取航班的机位预分配结果 航班对应的机位预分配信息 得到每个机位的可利用时间段 从时隙分配方案中得到航班的时隙分配结果 包括带有航班波衔接的延误航班和没有航班波衔接的延误航班 步骤 ) 对于没有航班波衔接的延误航班 根据航站楼 % % 分 次循环 将没有航班波衔接的延误航班根据最小延误费用原则和航站楼
南 京 航 空 航 天 大 学 学 报第 卷 资源共享原则进行停机位分配 步骤 * 对于有航班波衔接的航班 考虑时隙公平交换的原则 根据不同的航站楼 % % 分 次循环 得到每个航站楼的延误航班时隙交换集合 根据有航班波衔接的航班和有时隙交换的延误航班 得到没有时隙交换的延误航班集合 根据最小延误费用原则和航站楼资源共享原则进行停机位分配 步骤 + 将步骤 的结果根据不同的航站楼进行综合 得到最终的各个航站楼的停机位分配 在求解策略的设计中 将精确算法和启发式规则有机地结合在一起 既确保解的可行性 又灵活 个性化地控制搜索过程 启发式规则为 假设延误航班计划所属航班波为! 3 则其分配时隙所属的航班波必须大于等于! 3 航空公司进行时隙互换时 延误航班所处的航班波的数值应尽量相同 航班的停机位在不同航站楼之间调整要满足以下条件 不能是有航班波衔接的航班 调整后该航班产生的油耗费用不能大于该航班所属机型的平均油耗 调整后该航班的到达停机位时间不能大于该航班所属机型的平均滑行时间 调整后各航空公司的时隙交换满足公平性原则 将上述两个算法的求解规则 结合不同的 值和约束条件 同时植入深度优先搜索算法中 一体化搜索确定延误航班的时隙分配集合与停机位指派集合 从而延误航班的时隙分配并最终确定满足多目标的停机位指派方案 * 实例分析 *( 实验数据 大型机场的航站楼比较庞大 分区也较为复杂 因此本文选取两个航站楼内 个 / 内到达的航班及机位分配情况进行 其中 和 属于一个航站楼 和 属于另一航站楼 小 中 大机型分别用 表示 国航 东航 南航 海航分别用 ( 表示 最小安全时间间隔 : 旅客中转等待成本 元 飞机的油耗成本 元 8 飞机油耗 大型飞机 +8 中型.8 小型 8 航班信息见表 各个的机位信息见表 延误信息见表 *) 实验结果及分析 执行本文算法 根据时隙交换的优先级高于滑行油耗的原则 进行多次运算后 得到 :0 : 在满足时隙交换公平性的条件下 得到时隙交换结果如表 所示 航班号 表 ( 多航班信息表 &(- " 到港时间 离港时间 机型 乘客航空航班波数量公司 ' / / ' / ' / ' / ' '+ ' '. / / / / / ( / +. / ( ( / / / / / +. / ( / / ( / ( / ( / ( / (+ / ( (. (/ (
第 期 刘君强 等 基于协同决策的多航站楼停机位实时分配算法 机位号 表 ) 多机位信息表 &) " 步行时间 滑行时间 机位型号 所属 +. / + + +. / +. + + + +. + / +. 表 * 延误航班信息 &*$ 航班号到港时间离港时间 ' '+ '. / / /. ( ( (. 表 + 时隙交换结果 &+./" 航班号到港时间离港时间航班号到港时间离港时间 ' / '+ '.. ( / ( / (. 在不同的限定条件下 得到机位实时指派方案如表 所示 其中 初始方案表示航班尚未延误的机位初始分配方案 方案表示航班延误后 进行合理的时隙交换但航站楼之间与航站楼各之间的机位资源不共享时产生的机位指派方案 方案表示航班延误后 进行合理的时隙交换且航站楼之间与航站楼各之间的机位资源可共享时产生的机位指派方案 方案表示航班延误后 不进行时隙交换但航站楼之间与航站楼各之间的机位资源可共享时产生的机位指派方案 航班 号 表 0 不同方案下的机位指派 &0 $ 初始 航班 号 初始 '. ' ' + + + + + + '. + ' '+ + + + + ' + + + + '.. /. / (.. / ( / / / ( /... ( + + (... (+.. / / ( / / / / / (... (/ / / ( 初始方案中 滑行油耗为 8 旅客中转等待时间为 +/+ 因此 总成本为.+. 元 方案中 滑行油耗为 8 旅客中转等待时间为 因此总成本为 +/ 元 方案中 滑行油耗为 ++8 旅客中转等待时间为 因此总成本为 + 元 方案中 滑行油耗为 +.8 旅客中转等待时间为. 因此总成本为 /. 元 各部分成本变化情况如图 所示 对比方案 与方案 可知 当资源共享时 飞机的滑油成本可以大幅度减小 从而降低最终的总成本 对比方案 和方案 可知 当时隙可交换时 旅客的中转等待时间可以大幅度减小 从而控制最终总成本 结果显示 本文
+ 南 京 航 空 航 天 大 学 学 报第 卷 图 不同机位指派方案下的成本增量对比 $%3$ %#$$#%$2##$ 提出的算法在实现了资源共享的同时也实现了时隙的有效交换 达到了控制延误成本的目标 + 结束语 本文研究了协同决策机制下 航班延误时 多航站楼的机位实时指派算法 实验证明 本文提出的机位实时指派算法是一种切实可行且运行高效的调整算法 该算法能充分考虑多航站楼资源的共享性以及航空公司的时隙互换公平性 实现多方延误费用的最小化 降低航班延误引起的滑行油耗成本和旅客中转等待成本 能够在航班波的环境下实现航空公司与机场的协同决策 参考文献 0 0%2$#( )3%5 %# $$#%$%3%%#$1$3%% ##/./-.. 2# '#-$##%"##%2#$- %%3% %#$6##- $#&$%#$//.-+ 2$%32#'##%%2 332 %% %##$$#%3# 1$3%% ##.-./ ## #& 12#3% %#$$#% 3#0%2#%#%$#2- %27##$%2#%2 <6*%#- % ### &$%# ##$ <6 *- ( <= '#$#%#62#$%$ %2# "#-$%# 3% %# $$#% 3#%2#)3#%#$#2- #%&+-+. +2&1 22'2#$%332 3% %#$$#%$$%2$%2%#- &$3#)3#%#$#2.-+ 1 22#-%# %#$$#%$ # %#3& %#$2%#$$%2$%2%#&$ **%#%####"#)3- #%$=$%$*%$2* /+-. 熊杰 张晨 基于飞机滑行油耗的枢纽机场机位分配研究 交通运输系统工程与信息 ++- #>2 2# '3% %# $$#% 6%23#%4 $%&$$ 1$3%%&$%#$## *% 1#2&++- /1 222&< 52' &- %2 %#$$#%$#"# 2%#&%**%#- %###3%###*- %1#2& **12#* /- 严俊 吴桐水 高强 等 协同决策机制下的时隙二次指派 南京航空航天大学学报 -+?1$2@ #%#-$$- #%$%%"##$-8 #2- $!"#$%&'#- %$ '$%%$-+ 高强 严峻 朱金福 (0 机制下航空公司时隙分配决策 交通运输系统工程与信息 /-/. @ >2'#$A3%5- %#$$%%(0 1$3%%&$%#$## *% 1#2&/-/. 朱博 朱金福 高强 飞机和机组一体化恢复的约束规划模型 交通运输工程学报 -. >2>2@ $%%3- #%#%##"#&% #611$3%%- ## -. 皇甫国晟 张兰芳 机场多航站楼体系间运输方式的适用性分析 交通与运输 -+ <$2# >2 = 12#33% &$$%$3% #%2 %-%#$&$- %#$1 1$3%%- + >2&' %# 4# $#%3 *%2# %2 *%#%&3$ )3#%$#$#2*%$'33%$>2- #2*.- >2& *%%%%2#$%%- #=12#=7 -