第1章 绪论
1.1 停机位分配问题的研究背景和意义
随着国民经济的快速发展和人民生活水平的提高，航空运输作为一种方便、舒适、快捷的空中交通方式，乘坐比重愈来愈大。据民航局预计，我国航空运输总周转量以年均14%高速增长，到2025年中国民航将实现运输总周转量2000亿吨公里以上，航空旅客运输量将超过8.7亿人次，货邮运量2600万吨，旅客周转量在国家综合交通运输中的比重达到20%以上[1]，这将导致机场面临着容量不足的问题。我国《民用运输机场建设“十三五”规划中期调整方案》提出，要续建机场30个、新建机场43个、改扩建机场125个和迁建机场17个，但在短期内通过耗时耗资对停机位、跑道、航站楼等关键资源进行新建或扩容难以解决机场资源容量的严重不足问题[2，3]。因此，在保证航班安全运行的前提下，对机场现有的有限关键资源进行优化配置与合理调度，提高关键资源利用率和机场服务水平，进而全面提升经济效益。
停机位作为机场极其稀缺和昂贵的重要资源，是实现航班快速安全停靠、保证航班之间有效衔接、提高整个机场系统容量和服务效率的一个关键因素。机场停机位分配问题是针对关键资源停机位分配的优化问题，旨在满足一定约束条件和目标要求的前提下，为每个执行航班分配适当停机位，以保证航班正常和客货的有效衔接，提高机场的服务质量。该问题具有内在的多目标、多约束和多资源理论复杂属性，且由航空公司自身原因、流量控制、天气原因等造成的不正常航班停机位再分配问题更为复杂。停机位已成为继跑道之后又一个制约机场发展的瓶颈，不合理的停机位分配，不但增加航班的延误、降低资源的利用率，造成旅客满意度的下降，而且还增加了航空公司和机场的运营成本[4，5]。因此日益增长的航空运输需求与航空运输系统容量之间的矛盾愈加突出，导致机场停机位分配问题的重要性日益凸显。由此可见，机场停机位分配问题的研究在现实中具有重要意义。
停机位静态分配只考虑了机场结构、航班数、飞机类型等确定性因素，没有考虑航班延误、航班早到、航班新增、航班取消等随机因素。而现实运行中任何停机位分配都不可避免存在动态不确定因素，如恶劣天气、飞机机械故障、空中流量控制等，都将导致航班延误，甚至航班取消。近年来，我国航班不但正常率不断降低(已低于80%)，而且平均延时也在增加(已达到60分钟)。根据不正常航班产生原因的分类统计，由航空公司自身原因造成的航班不正常达到40%以上，其次是流量控制约占25%，天气原因约占20%[6]。天气和流量控制导致的航班不正常并不是主要原因，也是航空公司无法控制的；而航空公司自身原因导致的航班不正常却是整个航班不正常的*大贡献者，有不少研究表明导致航班不正常的主要原因是航空公司的调度设计决策不合理造成的。某一航班的不正常可能对分配到同一停机位的其他航班造成连锁效应，甚至出现“多米诺效应”，从而导致机场停机位完全重新再分配与调度。航班停机位的改变将对操作人员、安保人员、旅客等造成广泛的影响。因此，获得具有鲁棒性的停机位分配甚至动态分配的计划，得到稳定高效的智能调度方案，不仅对机场各部门非常重要，而且还能提升旅客的服务质量，对于实现智慧机场的智能化具有重要的理论意义和实际价值。
1.2 机场停机位分配问题
停机位分配问题就是将机场每一架进港的飞机，安排到一个合适的停机位上。其中，每个停机位在同一时刻只能停靠一架允许的机型，并且每个停机位上的飞机都会执行一个到达航班和一个出发航班，这两个航班由这一架飞机来执行，这两个航班相互配对形成了一个航班对，这架飞机在此停机位上的停靠时间被称为机位占用时间。在机位占用时间内，别的飞机不能停靠在此停机位上，在这架飞机离开此停机位后，还要求在一个安全间隔时间以后，才允许将此停机位安排给另外一架飞机使用。
飞机在停机位上的主要作业活动流程图，如图1.1所示。
图1.1 飞机在停机位上的主要作业活动流程图
停机位分配问题是经典分配问题的一种变形，其中停机位是被分配者，任务是待分配停机位的航班。停机位分配与经典分配的不同之处在于一些被分配者不能执行某些任务、任务比被分配者多，以及任务和被分配者的数量随时间变化等。停机位分配问题与经典分配问题的主要区别还在于经典分配问题中没有限定完成任务的准确时间段，而在停机位分配问题中，则明确规定了作为“任务”的完成时间，所以停机位分配问题比经典分配问题要更为复杂。
1.3 停机位分配问题的研究现状
针对机场有限的停机位资源分配问题，国外学者从20世纪70年代便开始了停机位分配问题的研究，主要通过抽象和归纳停机位分配问题中的约束条件，建立其数学模型，并从数学上研究数学模型的求解。国内开展停机位分配问题的研究起步较晚，约从2004年起，一些专家学者才开展机场停机位分配的研究，主要采用数学规划法、分支定界法、专家系统、启发式算法等来实现停机位的分配。作为一类受人类智能、生物群体社会性或自然现象规律的启发而发展起来的群集智能优化算法，如遗传算法、粒子群优化算法、禁忌搜索算法、蚁群优化算法、差分进化算法、菌群优化算法、萤火虫算法等，具有较强的全局优化能力，已成功用于机场停机位资源的优化分配，并取得了较理想的停机位分配结果。这些年来，学术界主要集中在停机位静态分配的研究，而与实际动态环境更加密切的停机位动态分配与实时再分配的研究相对较少。下面对国内外关于机场停机位分配问题的研究现状进行分析。
1.3.1 停机位静态分配问题的研究现状
停机位静态分配问题是从20世纪70代开始研究，至今已提出关键路径法、分支定界法、整数规划法、启发式算法等研究方法。Braaksma等[7]*早以所有旅客行走距离*小为单一目标，建立了基于关键路径法的仿真模型，以增强停机位的利用率。Babic等[8]以旅客步行距离*短为目标构建了停机位分配模型，利用分支定界法对其求解。Mangoubi等[9]在 Babic模型基础上构建了以旅客步行总距离*小化的数学规划模型。针对分支定界、动态规划、线性松弛等精确算法只能分析小规模问题，提出了元启发式方法(遗传算法、禁忌搜索、模拟退火等)用于求解较大规模的停机位分配问题。Haghani等[10]采用启发式算法求解提出的机场终端停机位分配整数规划模型。文军[11]用划分时间片算法建立了停机位分配的图论模型，将机场停机位分配问题转化为图的 K-顶点着色问题，采用遗传算法求解图的 K-顶点着色问题。冯程等[12]建立了以旅客进出机场飞行区时间*短为目标的停机位分配模型，通过沈阳桃仙国际机场实际数据设计了算法和仿真分析。Genc等[13]建立了以停机位占用时间*大为目标的停机位分配模型，采用混合启发式算法和随机方法对其求解。Cheng等[14]建立了基于遗传算法、禁忌搜索和模拟退火相结合的机场停机位分配方法。Kim等[15]提出了旅客过境和飞机滑行加权*小时间的停机位分配模型，并采用遗传算法对其求解。陈前等[16]考虑到机场系统的安全运行约束，建立了避免冲突的停机位分配模型，采用遗传算法进行求解，验证了模型的合理性与有效性。马思思等[17]基于传统停机位指派要求和场面运行安全规定以及航空公司约束，以滑行总距离*小为目标函数建立停机位分配模型，采用全局求解器( global solver)进行了求解。李云鹏等[18]根据机场停机位分配的实际规则，以*小化停机位使用数目为优化目标，建立了停机位分配混合整数规划模型，采用基于属性匹配的启发式算法对其进行了求解。Pternea等[19]建立一个考虑机场的布局和航班连接的停机位分配模型，并对其进行了求解。Zhao等[20]以*大分配率为优化目标建立了机场停机位分配模型，采用深度强化学习求解模型。
这些文献分析表明，当前是以实际运营为导向的停机位分配问题研究，主要运用启发式算法求解实际航班停机位分配问题。
1.3.2 多目标停机位分配问题的研究现状
停机位分配是一个复杂的多目标组合优化问题，国内外一些研究者对多目标停机位分配问题进行了探讨，多目标机位分配问题已成为近年来的研究热点。Yan等[21]以*小化旅客行走距离和到达旅客等待时间为目标，建立了多目标0-1整数规划模型，结合变量产生法、单纯型法及分支定界法对其求解。Ding等[22]考虑*小化未分配停机位的航班数量和旅客总计步行距离(进离港航班、转机)两个优化目标，建立了受限停机位二次分配模型，运用贪婪算法、模拟退火、禁忌搜索等群集智能优化算法对其求解。Drexl等[23]考虑*小化无停机位的航班数量和旅客行走距离以及*大化航班停机位偏好为优化目标，利用基于 Pareto的模拟退火算法获得 Pareto前沿优化解。杨文东等[24]以航班延误和停机位空闲时间线性总和*小为优化目标，提出了停机位航班连结树的概念和构造方法，利用贪婪算法对其求解。刘长有等[25]为合理分配大型繁忙机场停机位，兼顾安全与效率，建立了基于运行安全的停机位分配问题优化模型，利用遗传算法对其求解。丁建立等[26]根据不同航班占用停机位的时间冲突约束，建立了基于停机位和航班类型匹配约束的图权值停机位分配模型，并用蚁群协调算法对其求解。Maharjan等[27]以飞机燃油成本*小、旅客转机感受*好和转机时间*短为优化目标，将停机位分配问题建模为网络流模型，利用分解方法对其求解。Jiang等[28]以所有旅客步行的距离*短和不同航线步行距离平均化为目标，建立了多目标停机位分配模型。陈华群[29]以停机位使用数量*少，航空器在机场滑行距离或时间*短且充分考虑机位均衡利用为目标，建立了机场停机位分配问题的优化模型，设计了基于蚂蚁径路搜索规则的迭代寻优算法对其求解。Yu等[30]建立了具有稳健性、成本*小和乘客满意度的停机位分配等效 MIP模型，并设计了4个不同算法对其求解。Genc等[31]以*大化停机位分配、*小化旅客步行距离和*大化航班到登机口偏好为优化目标，建立了多目标停机位分配模型，采用进化单步大爆炸优化方法对其求解。Da.[32]以旅客步行距离*短和地面操作*少化为优化目标，建立机场停机位分配的多目标优化模型，并对其求解。Dell'Orco等[33]以旅客步行距离*短和远机位使用*小化为优化目标，建立机场停机位分配模型，采用模糊蜂群优化算法对其进行求解。徐思敏等[34]分析了停机位指派过程设计的利益主体，以航空公司运行成本旅客步行距离、航班冲突概率*小化以及航空公司之间的公平性*大化为目标，建立了大型机场停机位多目标指派模型，采用第二代非支配排序遗传算法对模型进行仿真验证。Seyedmirsajad等[35]考虑直接影响机场多准则决策过程的所有资源和约束，建立了停机位三目标分配数学模型，采用第二代非支配排序遗传算法对其进行有效求解。Li等[36]考虑到使用的停机位数量和未分配到停机位的航班数量*少，以及未换乘旅客人数*少为目标，建立了停机位分配的多目标0-1规划模型，采用参数优化的图着色算法对模型进行了求解。余朝军等[37]在考虑航班类型约束、飞机机体类型约束和转场时间间隔约束的基础上，以分配在固定登机口的航班数量*多、使用的固定登机口数量*少和乘客换乘紧张度*小为目标，建立了航班－停机位分配的多目标非线性0-1整数规划模型，并设计了一种改进型基因编码的遗传算法以提高求解效率。闫萍等[38]构建基于冲突回避的滑行道与停机位联合调度模型，并提出改进的自适应差分进化算法求解问题。方健尔等[39]针对不同的优先级建立多目标规划模型对航班进行优化分配，采用贪心算法和禁忌搜索算法，结合登机口类型、航班时间的约束，逐次对*大化分配航班问题，*小化中转旅客*短流程时间问题，*小化旅客总体紧张度问题进行建模求解。唐旭等[40]考虑了航站楼扩增对中转旅客影响，建立了综合的登机口优化调度的模型，提出基于社群联盟冲突消解原则的图着色优化算法，实现了对模型的优化，得到*佳调度方案。文笑雨等[41]针对登机口候机紧张和中转旅客航班衔接的
展开
