自主取消航班下多目标时隙二次分配的改进食物链退火算法_陈可嘉.pdf

第 28 卷 第 1 期2023 年 2 月工业工程与管理Industrial Engineering and ManagementVol.28 No.1Feb.2023自主取消航班下多目标时隙二次分配的改进食物链退火算法陈可嘉，郭小清（福州大学 经济与管理学院，福建 福州 350108）摘要:对航空公司在协同决策机制下时隙充分时的自主取消航班问题的研究，能够有效地缓解因不正常航班带来的延误损失。针对此问题，建立了航空公司总延误成本最低及旅客总延误时间最小的多目标模型。在已有改进食物链算法的基础上，提出了改进食物链退火算法，求解了兼顾航空公司和旅客双方利益的Pareto解集。以某机场的不正常航班数据仿真，验证了算法的可行性。最后通过与改进食物链算法对比，证明了改进后的算法得到的解的个数更多并且结果更优。该模型和算法能够为航空公司自主取消航班下时隙二次分配问题做出合理决策提供参考。关键词:时隙二次分配；协同决策；航班取消；多目标优化；改进食物链退火算法中图分类号:V 355 文献标识码:AImproved Food Chain Simulated Annealing Algorithm for Multi-objective Slot Secondary Assignment under Autonomous Flight CancellationCHEN Kejia，GUO Xiaoqing（School of Economics and Management，Fuzhou University，Fuzhou，Fujian 350108，China）Abstract:Research on the autonomous flight cancellation of airlines when the slots are sufficient under the cooperative decision-making mechanism can effectively alleviate the delay and loss caused by abnormal flights.In response to this problem，a multi-objective model was established to minimize the total delay cost of airlines and the total delay time of passengers.Based on the existing improved food chain algorithm，an improved food chain simulated annealing algorithm was proposed to solve the Pareto-front，which took into account the interests of both airlines and passengers.The abnormal flight data at a certain airport was simulated to prove the feasibility of the algorithm.Compared with the improved food chain algorithm，the improved algorithm has more solutions and better results.The model and algorithm can provide a reference for airlines to make reasonable decisions on the slot secondary assignment problem for autonomous flight cancellation.Key words:slot secondary assignment;collaborative decision-making;flight cancellation;multi-objective optimization;improved food chain simulated annealing algorithm文章编号：1007-5429（2023）01-0051-08DOI：10.19495/ki.1007-5429.2023.01.007收稿日期：2021-01-02基金项目：国家社会科学基金项目（18BGL003）作者简介：陈可嘉（1978），福建福州人，博士，教授，主要研究方向为服务系统运作管理。E-mail：。-51第 28 卷 陈可嘉，等：自主取消航班下多目标时隙二次分配的改进食物链退火算法1 引言 根据中国民用航空局发布的民航行业发展统计公报显示，我国的平均航班不正常率在2018年和2019年分别是19.87%1和18.57%2。天气和航空公司自身原因是造成航班不正常的两个最主要原因。当因恶劣天气影响及空域流量变化引起的航班延误发生时，空中管理部门会给航空公司重新分配时隙资源，但航空公司只拥有时隙的使用权而没有分配权，因此不一定能获得理想的时隙。在这个大背景下，协同决策（collaborative decision-making，CDM）机制应运而生。在 CDM 下，航空公司可参与时隙分配决策。公报数据显示，2019年由于航空公司自身原因导致的不正常航班相比2018年下降了2.22%，CDM功不可没。不正常航班发生时，航空公司需迅速采取应对策略，将航班延误对航空公司及旅客带来的影响降到最低。在成本损失方面，PELLEGRINI等3以降低空域用户的总体成本为目标，考虑飞机的周转时间限制提出了整数线性规划模型，更好地优化机场时隙分配。ARIKAN等4考虑飞机和旅客的相关费用，提出了综合航班和旅客恢复问题的混合整数规划模型，寻找运营成本和旅客成本之间的最佳折衷。COROLLI等5考虑天气等不确定因素建立了空中交通流量管理随机规划模型，以总延误成本最小为目标，设计的求解算法能为航空公司带来切实利益的决策。另一方面，减少旅客的延误时间也是值得关注的重点，旅客延误时间的增加会给旅客带来不好的出行体验，影响航空公司形象，不利于长远发展6。IVANOV等7提出混合整数优化模型来解决航路需求与容量的不平衡问题，控制延迟分配的可能性以最小化延迟向后续航班的传播，从而减少旅客的总延误时间。ERKAN 等8提出了在CDM下用于重新分配航班的起飞和到达时间的模型，航空公司利用该模型可获得延误航班重新编排方案以减少旅客的总延误时间。目前的相关研究多数只考虑到延误成本或延误时间其中一个因素，但快速变化的市场环境使得竞争日益激烈，多目标优化问题更加符合实际。如何同时兼顾航空公司的总延误成本及旅客的总延误时间两个目标是如今对不正常航班优化问题研究的重点。多目标优化问题的求解方法主要有：（1）通过给目标赋予不同权值，将多目标转化为单目标9；（2）分步对单个目标求解，之后寻找最优解10；（3）寻找Pareto最优解集11。ZOGRAFOS和JIANG12同时考虑航空公司的利益与旅客的延误时间，建立了时隙调度问题的双目标模型，采用行生成算法进行求解。YANG等13以航班总延误成本和旅客平均延误时间最小为目标，针对CDM下的时隙分配问题，提出了多目标规划模型，将多目标问题转化为单目标问题，采用交互式的线性和通用优化求解器求解。空管部门在时隙分配决策中起着主导地位，航空公司虽然也逐渐参与决策过程，但其真实需求仍然无法正确反映。因此，航空公司对空管部门分配的 时 隙 资 源 进 行 二 次 分 配 就 显 得 尤 为 重 要。RIBEIRO等14提出了基于多目标优先级的时隙分配模型，在满足机场容量限制的条件下对时隙分配进行优化，为航空公司提供了符合要求的时隙分配策略。BALL 等15研究了当空域或机场变得拥挤时，可采取时隙二次分配方式来缓解这种拥挤，并提出了连续整数规划模型求解航空公司的时隙二次分配问题。航空公司在时隙二次分配中采取的策略通常有延误航班和取消航班。取消航班虽然会让航空公司付出更大的成本损失，但能增强航班恢复计划制定的灵活性。有研究表明，当航空公司有了可以依赖的合作伙伴时，会更加倾向于取消航班16。PINEDA 等17为解决因航班取消而导致的时隙重新分配问题，综合考虑航空公司和旅客成本、改航引起的旅客延误等因素，提出了一种混合模型来寻找最佳方案与替代方案。HU等18研究了航线中断的多目标航班恢复问题，建立了以航班延误及取消总成本最小、延误时间最小的多目标模型，设计引入邻域搜索的启发式算法，为航空公司提供航班重新编排计划。在航空公司共同参与到时隙分配的过程中，空管部门可以更有效地分配时隙资源，并且通过考虑取消航班进行时隙二次分配，能够更好地发挥航空公司在CDM下的作用。结合上述分析，本文研究在空管部门已经初步确定时隙分配方案的基础上，航空公司根据实际情况对所得时隙资源进行二次分配的问题。研究中考虑航空公司自主取消航班的情况，兼顾航空公司成本损失和旅客总延误时间，建立多目标优化模型。根据问题特征，设计求解该问题的改进食物链退火算法（improved food chain simulated annealing algorithm，IFCSAA）。最后，以某大型机场的不正-52第 1期工 业 工 程 与 管 理常航班数据进行仿真分析，给出合理的时隙分配方案，并与改进前的算法结果作对比，验证该改进算法的有效性。2 时隙二次分配问题模型构建 2.1问题描述与假设天气等不确定因素造成时隙资源的变动是造成航班延误的重要原因，同时给空中交通流量的优化分配带来困难。在CDM下，航空公司参与空管部门决策的基本方式就是对时隙进行二次分配，主要举措是延误航班和取消航班。当时隙资源充足时，航空公司可通过取消航班放弃时隙的方式使得所使用的时隙少于空管部门分配给的数量，称作自主取消航班。将航班取消策略纳入航空公司时隙二次分配中可极大地增强航班恢复计划制定的灵活性。定义1 航空公司的总延误成本为航班的延误成本与取消成本之和。民航业一般将航班取消也视作延误，取消延误时间认定为480 min。定义2 旅客的延误时间为搭乘航班的实际起飞时刻与该航班计划起飞时刻的差值。根据问题描述，抽象出如下基本假设：假设1 当出现恶劣天气、流量管控时，空管部门给航空公司重新分配时隙时刻，并保持时隙数量与航班数量一致。假设2 在CDM下，航空公司可自由分配拥有的时隙，保证每个航班所用的时隙时刻不早于航班的计划起飞时刻。假设3 航空公司拥有自主取消航班的权力。2.2符号定义（1）模型集合I：所有航班的集合，iI；J：所有时隙的集合，jJ。（2）模型参数M为时隙数量；i为航班编号，i=1，2，M；j为时隙编号，j=1，2，M；sj为时隙j的时刻；ri为航班i的计划起飞时刻；i为航班i的机型延误运营成本；bi为航班i的取消费用；pi为航班i的票价；mi为航班i的最大载客人数；di为航班i的实际旅客人数。（3）决策变量xij为0-1 变量，xij=1表示航班i使用时隙j，xij=0表示不使用；yi为0-1变量，yi=1表示航班i取消，yi=0表示不取消。2.3目标函数（1）航空公司总延误成本最低航空公司的总延误成本包括航班延误成本和取消成本。延误成本主要有空中飞行延误成本、地面延误成本和旅客食宿补贴成本三个部分。总延误成本最低的目标函数为：minz1(x)=iIjJcijxij+iIbiyi（1）其中，cij代表航班的延误成本，由航班的机型延误运营成本和延误盈利损失构成，其计算公式为：cij=()i+plmi/h(sj-ri)（2）其中，p为航空公司平均票价，为航空公司平均利润率，h为平均飞行时间，l为航班平均客座率，sj-ri为航班的延误时间。取消成本主要由调机换乘、搭乘可选的最近航班、改签次日航班（航空公司需给予200元/人的食宿补贴）和旅