有限信息共享下多类型机场地面保障设备调度：一种基于增广拉格朗日的协同方法

《Journal of Air Transport Management》：Multi-type airport ground support equipment scheduling under limited information sharing: an augmented Lagrangian-based coordination approach

　　

# 摘要

机场地面支持设备（GSE）运营中的一个关键挑战在于分散的决策结构以及不同服务提供者之间薄弱的协调，这些挑战源于去中心化的运营结构和有限的信息交流。此外，由于问题规模庞大且任务交互复杂，直接求解完全集成的多类型GSE调度模型在计算上是不可行的。为应对这些挑战，本文提出了一种新颖的两层增广拉格朗日协调框架，将集成问题分解为独立子问题，同时增强全局调度的一致性。在所提出的方法中，主问题通过优化航班延误缩减和调度鲁棒性来确定全局任务开始时间，而服务类型子问题则优化车辆路径和局部调度决策以最小化行驶成本。为提升计算效率，嵌入了自适应大邻域搜索（ALNS）启发式算法，为子问题生成高质量的暖启动解。基于实际数据的计算实验表明，所提出的框架相较于贪婪局部调度基准提高了路径效率，在保持调度鲁棒性的同时显著降低了车辆总行驶成本，航班延误仅有适度增加，从而在合理的计算时间内有效平衡了延误绩效、鲁棒性和运营成本。

## 1. 引言

### 1.1 研究动机

航空运输需求的迅速扩张导致了航班运行数量的不断增加，给机场带来了日益增长的运营负担（Qian等，2025；Zhang等，2025）。特别是，飞机过站过程需要及时完成多项地面保障作业，每项作业都由专门类型的地面支持设备（GSE）提供支持。这些异构GSE资源的组织与调度效果是机场运营绩效的关键决定因素，而 inadequate 的GSE调度是航班延误的主要原因之一，仅次于空中交通管制问题（Wu和Caves，2004；Wang等，2025）。

协调多类型GSE运营的一个关键挑战源于异构利益相关者之间有限的信息共享和分散的决策（Fricke和Schultz，2009；Zhou等，2025）。不同的服务提供者往往仅基于对地面保障过程中其他参与者调度、约束和运营调整的有限了解来规划和运营其资源，这在一定程度上是由于数据隐私顾虑和组织边界所致。因此，调度决策往往侧重于局部服务效率，而与系统级绩效目标的协调仍然有限。这种分散的规划环境使得跨利益相关者的运营协调变得困难，并可能导致资源利用效率低下。

除了协调挑战之外，多类型GSE调度的大规模和组合特性进一步增加了集成优化的复杂性（Wang等，2025；Zhou等，2025）。一个真实的机场实例可能涉及数百架航班、数千个服务任务以及具有不同运营规则的多种车辆类型（Andreatta等，2014a, 2014b；Fei和Shuan，2016；Zhou等，2023；Wu等，2023）。当以完全集成的方式对跨所有服务类型的路径决策和任务开始时间进行建模时，所形成的优化问题在计算上变得不可行。这种复杂性还因多趟次车辆执行需求以及不同服务车队之间强烈的时空交互作用而进一步加剧。

基于上述挑战，本研究旨在开发一种调度框架，能够在信息共享有限的情况下有效协调多类型GSE运营，同时对大规模机场实例保持计算可行性。本文所提出的方法不假设完全集中化，而是考虑了去中心化和异构的服务提供者，以及服务任务之间的强耦合关系。建立了一个集成多类型GSE调度问题模型以捕捉这些运营需求，并开发了基于协调的解决方案框架，将集成问题分解为服务类型子问题，同时迭代地将局部决策与系统级目标进行对齐。

### 1.2 文献综述

关于多类型GSE调度的多项研究涉及在复杂资源约束下运营效率与服务绩效的联合优化，通常聚焦于降低成本、缓解延误和提高调度鲁棒性（Mao等，2009；Padrón等，2016；Zhao等，2019；Zheng和Jia，2020；Wu等，2023；Jin等，2025）。现有研究主要关注有限的车辆类型子集或特定的服务组合，这限制了捕捉真实机场运营中复杂的跨服务优先关系和冲突关系的能力（Zhao等，2019；Zheng和Jia，2020；Zhu等，2022）。从建模角度来看，多类型GSE调度问题通常被表述为带时间窗的车辆路径与调度问题（VRP）的变体。在该框架中，路径决策确定车辆访问飞机机位的顺序，而调度决策则在规定时间窗、任务时长以及跨服务优先或非重叠约束的条件下指定服务开始时间。这些基于VRP的模型为捕捉GSE运营的时空结构提供了灵活的建模基础，同时凸显了多种服务类型和紧密耦合的任务关系所带来的内在复杂性（Cheung等，2005；Padrón等，2016；Zhu等，2022）。

从算法角度来看，GSE调度的求解方法很大程度上取决于问题规模和建模复杂性。精确优化方法或基于分解的优化方法，包括商业优化求解器、网络流模型和列生成技术，已成功应用于小规模或中等规模实例，通常依赖于精心设计的模型或问题特定的分解策略以确保可求解性（Diepen等，2013；Schwarze和Voβ，2014；Li等，2017；Han等，2023）。然而，随着航班数量、服务类型和运营约束的增加，这些方法变得计算代价高昂，特别是当纳入容量约束、充电需求、技能兼容性和不确定性等现实特征时。为解决大规模和现实实例问题，已开发了一系列启发式和元启发式方法，包括贪婪算法（Wang等，2018）、遗传算法（Ip等，2012）、群体智能方法（Du等，2008）和大邻域搜索框架（Bubalo等，2017；Lv等，2023）。总体而言，这些研究表明，基于启发式的求解方法能够在实际计算时间内有效求解大规模多类型GSE调度问题。对于多类型GSE调度问题，异构服务任务之间复杂的时序交互引入了显著的协调挑战。因此，提出了多种基于分解的方法。例如，Padrón等（2016）将每个GSE车队建模为VRPTW子问题，并通过约束传播协调子问题解。然而，他们的方法主要强调可行性一致性和运营效率，而时序鲁棒性未得到明确考虑。Liu等（2022）为多个GSE车队提出了基于分解的框架，但协调过程严重依赖于基于优先关系的顺序调度和详细的上游调度结果。Zhu等（2022）开发了协调加油车和摆渡车的多目标混合整数规划框架，其中协调与路径和服务排序决策紧密耦合。Wu等（2023）进一步提出了基于分解的神经调度框架，根据服务优先关系顺序构建路径解。

尽管关于GSE调度的研究已相当广泛，但仍存在几个重要的研究空白。大多数现有研究假设集中化决策和完全信息共享，而在实际中，GSE运营由多个独立的服务提供者执行，信息共享有限，导致分散的局部优化和薄弱的整体协调。此外，许多现有分解方法依赖于基于优先关系的顺序调度和子问题之间的路径协调。虽然这些策略提高了计算可行性，但固定服务序列可能会显著限制车辆路径子问题的优化灵活性，其中路径决策是在预先确定的时序需求下进行优化的，以保持全局可行性，但可能以牺牲路径效率和调度鲁棒性提升为代价。这限制了同时改善路径效率和时序鲁棒性的能力。此外，由于异构车队、复杂的优先关系和容量约束，直接求解集成的多类型GSE调度模型对于大规模实例在计算上不可行，这凸显了对可扩展的协调框架的需求，该框架需平衡延误绩效、鲁棒性和运营成本。

### 1.3 研究贡献

本研究的主要贡献总结如下：

● 提出了一种新颖的主问题-子问题建模框架，用于在信息共享有限的条件下进行多类型GSE调度，其中全局任务开始时间在主问题层面确定，服务类型子问题独立处理车辆路径和局部调度，从而实现异构服务提供者之间的系统级协调。

● 开发了一种基于增广拉格朗日的协调算法，在统一框架内联合解决航班延误、调度鲁棒性和车辆行驶成本问题，并在服务类型子问题中嵌入自适应大邻域搜索（ALNS）启发式算法，以提升大规模实例的求解质量和计算效率。

● 进行了全面的敏感性分析，探讨资源可用性、管理偏好和运营约束对调度绩效的影响，从而为机场运营者和地面服务管理者选择合适的协调策略提供定量洞察。

本文其余部分组织如下。第2节描述多类型GSE调度问题，包括运营设置和任务特性。第3节建立所提出协调框架的主问题层面和服务类型子问题调度模型。第4节介绍基于增广拉格朗日的协调算法以及用于高效求解问题的嵌入式ALNS启发式算法。第5节报告计算实验和敏感性分析结果，并讨论资源可用性和管理偏好对调度绩效的影响。最后，第6节总结全文并展望未来研究方向。

## 2. 问题描述

机场地面支持运营涉及一系列异构服务任务，这些任务必须在有限的过站时间内为每个航班完成。典型的地面服务包括行李装卸、加水、加油、污水排放、垃圾收集、餐饮服务、飞机牵引以及其他地面保障活动，这些作业由专门的地面支持设备（GSE）车队执行。本研究的目标是提高异构地面保障车辆的协调水平，以联合最小化航班起飞延误、提高调度鲁棒性并降低各GSE车队的总行驶成本，重点针对停靠廊桥的靠桥航班的地面保障运营。因此，考虑的是停靠在航站楼旁的出港航班。

地面服务任务通过安全法规和运营实践紧密耦合，同一航班关联任务的执行顺序必须符合一系列运营原则。具体而言，若存在行李卸载作业，须在行李装载之前完成。由于共享作业空间，加油作业不能与行李作业同时进行。出于卫生要求，加水和污水排放必须依次执行。垃圾收集的时序限制较少，可以与其他服务（包括行李作业和加油）并行进行。餐饮服务是飞机过站期间运营关键性服务，需要仔细协调调度。餐饮车通常每趟仅服务一架飞机，这是由服务定制化和卫生要求决定的。飞机牵引仅在所有必需的机位地面服务完成后方可进行（Zhu等，2022；G?k等，2023；Zhou等，2025）。图1总结了本研究所考虑的出港航班各项地面保障服务之间的时序关系。


此外，地面支持车辆的异构特性带来了不同的容量约束和服务模式，需要在建模阶段予以考虑。特别是，牵引车辆不受容量限制，而餐饮车辆通常每趟仅服务一架飞机，这是由于服务定制化和卫生要求所致。本研究所考虑的不同类型地面支持车辆的特性总结于表1中，其中"与其他服务的时间协调"表示相应服务是否需要在时序上与其他过站作业进行协调或排序，"与其他服务的空间冲突"表示该服务是否与至少一种类型同时进行的服务在飞机周围产生作业冲突。此外，某些服务类型受容量约束，因此在飞机过站运营中可能需要多趟次执行，而餐饮服务通常遵循每趟单次服务的运营模式。

**表1. 本研究所考虑的不同类型地面支持车辆特性**

| 车辆类型 | 与其他服务的时间协调 | 与其他服务的空间冲突 | 容量约束 | 每趟单次服务 |
|---------|-------------------|-------------------|---------|------------|
| 行李车 | 是 | 是 | 是 | 否 |
| 加油车 | 是 | 是 | 是 | 否 |
| 垃圾车 | 是 | 否 | 是 | 否 |
| 餐饮车 | 是 | 否 | 是 | 是 |
| 加水车 | 是 | 否 | 是 | 否 |
| 排污车 | 是 | 否 | 是 | 否 |
| 牵引车 | 是 | 否 | 否 | 否 |

由于不同类型的地面支持车辆通常由不同的利益相关方运营，独立做出的调度决策可能导致运营冲突。为应对这一问题，所提出的框架采用主问题-子问题分解结构。主问题确定所有地面服务任务的全局可行开始时间，目标是在提高调度鲁棒性的同时降低整体起飞延误。基于主问题调度方案，每个利益相关方在相应的子问题中独立确定车辆路径以最小化局部调度成本。

这些问题可以表述为带有时间窗的多趟次容量约束车辆路径问题（MTCVRPTW）的变体，其中每一趟次代表一个从场站到场站的服务周期。对于容量受限的地面支持车辆而言，由于车辆在开始下一个服务周期之前需要返回场站进行补给、卸载或容量重置操作，因此可能需要多个趟次。通过主问题与子问题之间的迭代交互，可以获得一个协调方案，从而在系统级性能与局部运营效率之间取得平衡。

所研究问题的整体描述如下：

**给定条件：**（1）一组待服务的出发航班，每个航班关联一组预定义的地面服务任务，包括行李装卸、加水、加油、排污、垃圾收集、配餐服务和飞机牵引。每项任务以服务持续时间和可行时间窗口为特征。（2）一组多种服务类型的地面支持车辆，每种车辆类型关联不同的运营特征，如容量约束和服务模式（例如单服务每趟次或多服务每趟次）。（3）同一航班的地面服务任务之间的优先关系，指定固定的执行顺序，以及可交换顺序关系，即要求任务按顺序执行但不规定固定顺序。（4）每类地面支持车辆在飞机停机位与场站之间的行驶时间信息。（5）航班的计划离港时间，用于评估地面服务任务执行所导致的离港延误。

**任务：** 确定所有地面服务任务和地面支持车辆的协调调度方案，使得每项任务的可行全局开始时间得到分配，并为每种服务类型构建车辆路径。目标是在任务时间窗口、优先和可交换顺序约束、车辆容量限制以及路径可行性的前提下，减少总离港延误并增强计划的鲁棒性。该方案应通过在任务开始时间与车辆路径决策之间进行联合协调，平衡系统级性能与局部运营效率。

## 3. 模型构建

### 3.1 符号说明

为方便阅读，本文所使用的符号汇总于表2。

**表2. 本研究使用的符号**

**集合**
- ?：航班集合
- ??：所有地面服务任务集合
- ??：服务类型集合
- ??????：服务类型 ?? 的任务集合，??∈??
- ??_f???：航班 ?? 关联的地面服务任务集合
- ??_s：服务类型 ?? 的车辆集合
- ?????×??：优先关系，(??,??)∈?? 表示任务 ?? 必须优先于任务 ??
- ??_f???：航班 ?? 内部的优先关系集合
- ?????×??：可交换顺序关系，(??,??)∈?? 表示任务 ?? 与任务 ?? 必须顺序执行但不规定固定顺序
- ??_f???：航班 ?? 内部的可交换顺序关系
- ?={0,1,…,R_max?1}：每辆车的趟次索引集合

**参数**
- ??_??, ??_??：任务 ?? 的最早和最晚可行开始时间
- ??_??：任务 ?? 的服务持续时间
- ??_??：航班 ?? 的计划离港时间
- ??_u_v：从节点 ?? 到节点 ?? 的行驶时间，其中 ??,??∈{0}∪??，其中节点0表示场站
- ??_??：任务 ?? 的需求量（如适用）
- ??_??：车辆 ?? 的容量（如适用）
- ??：足够大的常数
- ??：航班延误的权重系数
- ??：鲁棒性的权重系数
- ??：同一航班内连续任务之间最小时间缓冲的下界
- ??：与使用趟次数相关的小正惩罚系数
- R_max：每辆车允许的最大趟次数

**决策变量**
- ??_g_??：任务 ?? 的全局开始时间
- ??_s_??：任务 ??∈??_?? 的局部开始时间
- ??_??≥0：航班 ?? 的延误
- ??_??_??≥0：同一航班内优先相关任务 (??,??) 之间的时间间隔
- ??_??≥0：航班 ?? 内连续任务之间的最小时间缓冲
- ??_s_??_??_??_??∈{0,1}：二元变量，若车辆 ?? 在第 ?? 趟次中遍历弧 ???? 则为1
- ????????????_??_??_??∈{0,1}：二元变量，若任务 ?? 在第 ?? 趟次中分配给车辆 ?? 则为1
- ??_??_??∈{0,1}：二元变量，若车辆 ?? 的第 ?? 趟次被使用则为1
- ??_start_??_??, ??_end_??_??：第 ?? 趟次的出发和返回时间
- ??^f_??_??：可交换顺序关系的顺序选择变量，其中 ??^f_??_??=1 表示任务 ?? 先于任务 ?? 执行，??^f_??_??=0 则相反，(??,??)∈??_f

### 3.2 主问题

主问题确定所有地面服务任务的全局开始时间，为调度框架提供时间协调。详细的车辆路径和资源分配决策在子问题层面根据主计划进行处理。目标函数为：

(1a) min ??∑_{??∈?}??_?? ? ??∑_{??:??_??≠?}??_??

约束条件为：

(2) ??_??≤??_g_??≤??_??, ???∈??

(3) ??_g_??≥??_g_??+??_??, ???∈?, (??,??)∈??_??

(4) ??_??_??=??_g_?????_g_?????_??, ???∈?, (??,??)∈??_??

(5) ??_??≤??_??_??, ???∈?, (??,??)∈??_??

(6) ??_g_??≥??_g_??+??_?????(1???^f_??_??), ???∈?, (??,??)∈??_??

(7) ??_g_??≥??_g_??+??_???????^f_??_??, ???∈?, (??,??)∈??_??

(8) ??_??≥??_g_{??_TOW(??)}???_??, ???∈?

(9) ??_??_??≥0, ?(??,??)∈??_??

(10) ??_??≥0, ???∈?

(11) ??^f_??_??∈{0,1}, ???∈?, (??,??)∈??_??

目标函数(1a)同时最小化总离港延误并最大化每个航班内部的最小时间缓冲，从而在运营效率与计划鲁棒性之间实现平衡。约束(2)将每项任务的全局开始时间限制在其可行时间窗口内。约束(3)确保每项地面服务任务仅在同一航班内其所需的前序任务完成后才开始。约束(4)将优先相关任务之间的时间间隔变量定义为前序任务完成与后续任务开始之间的松弛量。约束(5)将航班级鲁棒性指标定义为同一航班所有优先相关任务中最小的时间间隔。约束(6)和(7)确保每个可交换顺序对中的任务按可交换顺序依次执行。约束(8)将航班的离港延误定义为其关联的牵引任务（记为 ??_TOW(??)）的实际开始时间与计划离港时间的正偏差。结合 ??_?? 的非负性约束以及目标函数中延误项的最小化，确保延误变量在最优解处取最小可行值。约束(9)和(10)分别对辅助间隔变量和延误变量施加非负性约束。约束(11)规定二元顺序选择变量。

主问题中考虑的两个目标共享相同的时间维度，因此采用线性加权求和公式来权衡离港延误与计划鲁棒性是合理的。当存在关于可接受鲁棒性水平的事先知识或专家经验时，所提出的公式可进一步扩展为ε-约束公式。在本研究中，该双目标问题还可以通过设定鲁棒性缓冲的下界来转化为单目标优化模型。具体而言，目标函数(1a)可重新表述为：

(1b) min ∑_{??∈?}??_??

并施加额外约束：

(12) ??_??≥??, ???∈?, ??_??≠?

其中 ?? 表示每个航班内部最小时间缓冲的指定下界。这种替代公式允许决策者在最小化离港延误的同时明确控制所生成计划的鲁棒性水平，为不同的运营偏好和规划场景提供额外的建模灵活性。

### 3.3 子问题

子问题根据主问题提供的全局计划，确定每种服务类型的路径决策和局部开始时间。它考虑了车辆可用性、行驶时间、服务持续时间和运营约束，确保车辆路径和任务执行的可行性。子问题的目标函数表述如下：

(13) min ∑_{??,??}(∑_{??∈??_??}??_0_????_s_0_??_??_?? + ∑_{??,??∈??_??,??≠??}??_??_????_s_??_??_??_?? + ∑_{??∈??_??}??_??_0??_s_??_0_??_??) + ??∑_{??,??}??_??_??

约束条件为：

(14) ∑_{??∈??_??}∑_{??∈?}????????????_??_??_??=1, ???∈??_??

(15) ∑_????_s_0_??_??_??=??_??_??, ???,??

(16) ∑_????_s_??_0_??_??=??_??_??, ???,??

(17) ??_0_??_??_??+∑_{??∈??_??,??≠??}??_s_??_??_??_??=????????????_??_??_??, ???,??,??

(18) ??_??_0_??_??+∑_{??∈??_??,??≠??}??_s_??_??_??_??=????????????_??_??_??, ???,??,??

(19) ????????????_??_??_??≤??_??_??, ???,??,??

(20) ??_??≤??_s_??≤??_??, ???∈??_??

(21) ??_s_??≥??_s_??+??_??+??_??_?????(1???_s_??_??_??_??), ???,??∈??_??, ??≠??, ??,??

(22) ??_s_??≥??_start_??_??+??_0,?????, ???,??,??

(23) ??_end_??_??≥??_s_??+??_??+??_??,0???(1???_s_??_0_??_??), ???,??,??

(24) ∑_{??∈??_??}??_??????????????_??_??_??≤??_????_??_??, ???,??

(25) ??_??,??≥??_??,??+1, ???, ??=0,…,R_max?2

(26) ??_start_??,??+1≥??_end_??,?????(1???_??,??+1), ???, ??=0,…,R_max?2

(27) ??_start_??_??≤????_??_??, ???,??

(28) ??_end_??,??≤????_??_??, ???,??

(29) ??_start_??_??≤??_end_??,??, ???,??

目标函数(13)最小化所考虑服务类型车辆路径的总行驶成本，同时一个小惩罚项 discourage 不必要的趟次使用，其中点 {0} 表示场站。约束(14)确保该服务类型的每项任务恰好分配给一辆车的一个趟次。约束(15)和(16)强制每个被使用的趟次从场站出发并返回场站。约束(17)和(18)是流量平衡约束，确保分配给车辆趟次的每项任务恰好进入和离开一次。约束(19)防止任务被分配给未使用的趟次。约束(20)将每项任务的局部开始时间限制在其可行时间窗口内。约束(21)-(23)沿车辆路径传播服务开始和完成时间，以确保相对于行驶时间和服务持续时间的时序可行性，从而隐式地消除子回路，因为任何循环路径都会违反由此产生的时序优先级。约束(24)对容量受限的服务类型施加车辆容量限制。约束(25)和(26)确保同一车辆执行的多个趟次顺序执行，从而防止趟次重叠。约束(27)-(29)对每个趟次的出发和返回时间进行界定并强制执行其逻辑一致性。

对于配餐车辆，由于新鲜度和温度要求以及不同航班的异质餐食需求，每个配餐趟次限制最多服务一架飞机，由约束(30)强制：

(30) ∑_{??∈??_CAT}????????????_CAT_??_??_??≤1, ???∈??_CAT, ???∈?

并且约束(24)仅对容量受限的服务类型施加，对于牵引车辆则省略。

所提出模型中的所有时间变量均以分钟表示。因此，航班延误、鲁棒性和行驶成本指标均以分钟衡量。

## 4. 求解方法

### 4.1 基于增广拉格朗日的协调算法

主问题确定全局开始时间 ??_g，而每个服务类型子问题确定局部开始时间 ??_s 以及路径变量。为了促进主计划与子问题计划之间的一致性，引入以下共识约束：

(31) ??_g_??=??_s_??, ???∈??, ???∈??_??

上述约束将主问题与服务类型子问题耦合在一起。直接求解包含耦合共识约束的整合公式将导致计算代价高昂的大规模优化问题，并且需要从所有服务类型子问题获取详细的运营信息。为解决这一问题，通过增广拉格朗日松弛（ALR）框架对耦合共识约束进行松弛。如图2所示，所考虑的问题表现出紧密耦合的约束结构，其中共识约束通过共享的任务开始时间变量将主问题与所有服务类型子问题联系起来。这些共识约束构成了困难的耦合约束，显著增加了问题规模。通过增广拉格朗日框架松弛耦合约束，原始紧密耦合的问题被分解为独立的子问题，大大提高了计算可行性。此外，通过引入拉格朗日乘子，共识约束被纳入每个子问题的目标函数中。这使得每个模块能够同时考虑自身目标和共识项。具体而言，主问题在航班延误、计划鲁棒性与共识惩罚之间进行平衡，而每个服务类型子问题则在其车辆路径成本与相应的共识惩罚之间进行平衡。因此，协调过程不需要在每次迭代时严格要求共识，也不需要在匹配全局和局部任务开始时间时过度牺牲各个模块的原始目标。相反，共识项提供了一种灵活的协调机制，逐步促进主问题与服务类型子问题之间的一致，同时保留每个模块的优化灵活性。

通过这种方式，增广拉格朗日方法不仅简化了问题结构，还在迭代协调过程中平衡了局部和全局目标。ALR方法已被广泛应用于现有研究中，用于求解各种场景下的大规模混合整数规划（MIP）问题，包括供应链规划（Tautenhain et al., 2021）、运输规划（Guo et al., 2024）、车辆路径（Yang et al., 2020; Song and Cheng, 2022; Song et al., 2024a）、选址问题（Song et al., 2024b）和电力管理（Qader, 2022）。ALR方法被用于提供紧下界并改善解的质量（Song and Cheng, 2022），或者用于建立增广拉格朗日协调框架，其中子问题通过启发式方法求解以迭代改进对偶乘子，随后通过恢复步骤保证可行性（Guo et al., 2024）。

**图2. 所研究问题的约束模块结构**

在本研究中，采用增广拉格朗日方法在统一的优化框架内协调主问题与服务类型子问题，使共识约束得以松弛并通过块坐标更新进行处理。每次迭代采用启发式方法求解复杂的MTCVRPTW子问题。迭代过程结束后，固定最终迭代中获得的全局开始时间并用于求解子问题，从而保留相对于全局和局部约束的可行性。

从实际运营角度来看，不同的GSE车队通常由独立的服务提供商管理，信息交流有限。在这种设置下，详细的路径计划、车辆级运营决策和内部调度信息通常不会在利益相关方之间完全共享。为了协调运营，每个服务提供商仅向主问题上传每架飞机任务的计划开始时间，而不透露个体车辆路径、容量或其他车队特定参数。增广拉格朗日协调机制基于这些有限信息，迭代更新异构服务任务之间的全局时间一致性，从而为分布式机场地面保障运营提供了一个实用的协调框架。

增广拉格朗日函数的公式如等式(32)所示。为每个共识约束引入拉格朗日乘子 ??_s_??，连同增广拉格朗日协调项。设 ??(??_g) 表示原始主问题目标函数，??_s(·) 表示服务类型 ?? 的原始子问题目标函数。

增强子问题目标函数记为 $G_s(\cdot)$，其同时考虑原始路由目标以及增强拉格朗日框架中与乘子和二次一致性惩罚项相关的部分。增强拉格朗日函数定义如下：

(32) $\mathcal{L}_\rho = F(S_g) + \sum_{s \in \mathcal{S}} H_s + \sum_{s \in \mathcal{S}} \sum_{i \in T_s} u_{s,i}(S_{s,i} - S_{g,i}) + \frac{\rho}{2} \sum_{s \in \mathcal{S}} \sum_{i \in T_s} (S_{s,i} - S_{g,i})^2$

其中 $\rho > 0$ 为控制一致性强制力度的惩罚参数。

增强拉格朗日问题通过迭代块坐标优化过程求解，其中主问题和各服务类型子问题交替更新。在每次块更新中，相应问题通过同时考虑其原始目标和鼓励全局与局部任务开始时间对齐的一致性项来进行优化。在第 $t$ 次迭代中，给定 $\{S_{s,t}\}$ 和 $u_t$，我们更新主问题和子问题，其中服务类型子问题通过启发式方法求解以生成本地时刻表和路由决策，而可求解主问题的解如下：

(33) $S_{g,t+1} = \arg\min_{S_g \in \Omega_g} \left\{ F(S_g) - \sum_{s \in \mathcal{S}} \sum_{i \in T_s} u_{s,t,i} S_{g,i} + \frac{\rho_t}{2} \sum_{s \in \mathcal{S}} \sum_{i \in T_s} (S_{s,t,i} - S_{g,i})^2 \right\}$

拉格朗日乘子根据式(34)使用对偶上升法更新：

(34) $u_{s,t+1,i} = u_{s,t,i} + \rho_t (S_{s,t+1,i} - S_{g,t+1,i}), \quad \forall s \in \mathcal{S}, \forall i \in T_s$

迭代过程基于原始残差的稳定准则终止，定义如下：

(35) $r_t \leq \epsilon$

(36) $r_t = \max_{s \in \mathcal{S}} \max_{i \in T_s} |S_{s,t+1,i} - S_{g,t+1,i}|$

为提高数值稳定性并避免过于激进的惩罚，引入了惩罚参数 $\rho$ 的自适应更新机制：

(37) $\rho_{t+1} = \begin{cases} \min\{\tau \rho_t, \rho_{\max}\}, & r_{t+1} > \kappa r_t \\ \rho_t, & \text{其他} \end{cases}$

其中 $\tau > 1$ 和 $\kappa \in (0,1)$ 为预定义常数。该策略仅在一致性违反未充分减少时增大 $\rho$。

整体增强拉格朗日协调程序总结于算法1中。

**算法1 增强拉格朗日协调**

输入：服务类型集合 $\mathcal{S}$；主目标 $F(S_g)$ 和可行域 $\Omega_g$；子问题模型 $\{sp_s\}_{s \in \mathcal{S}}$ 和可行域 $\{\Omega_s\}$；最大协调迭代次数 $T_{\max}$；残差容差 $\epsilon$；初始惩罚 $\rho_0 > 0$，乘子向量 $u_0 = 0$；惩罚更新参数 $\tau > 1$，$\kappa \in (0,1)$，$\rho_{\max}$；每个子问题的时间限制 $t_L$。

输出：协调时刻表 $S_g$；各服务类型路由和本地开始时间 $\{(x_s, S_s)\}_{s \in \mathcal{S}}$；最佳可行集成解 $\mathcal{X}_{\text{best}}$

S1: $\mathcal{X}_{\text{best}} \leftarrow \text{ALNS\_WarmStart}(\mathcal{S})$

2: 从 $\mathcal{X}_{\text{best}}$ 中提取初始本地时刻 $\{S_{s,0}\}_{s \in \mathcal{S}}$

3: 初始化 $u \leftarrow u_0, \rho \leftarrow \rho_0, t \leftarrow 0$

4: **while** $t < T_{\max}$ **do**

5:  主问题更新

6:  子问题更新（按服务类型并行）

7:  残差和乘子更新

8:  惩罚参数自适应更新

9:  准则检查：**if** $r_t \leq \epsilon$ **then break**

10:  $t \leftarrow t + 1$

11: **end while**

12: 固定全局开始时间 $S_g$

13: 以固定的 $S_g$ 求解各服务类型子问题以获得可行路由和本地时刻表

14: **return** $S_g, \{(x_s, S_{s,\text{final}})\}, \mathcal{X}_{\text{best}}$

### 4.2 基于ALNS的暖启动

3.3节中定义的服务类型子问题构成包含时间窗、容量约束和多趟次需求的大规模混合整数路由模型。直接求解这些子问题至最优性计算代价高昂。为应对这一挑战，采用自适应大邻域搜索（ALNS）启发式算法快速构建高质量可行路由和调度解，作为增强拉格朗日方法的有效暖启动输入，并有助于稳定和快速收敛。

ALNS是一种广泛使用的启发式算法，通过迭代地破坏和修复当前可行解中的任务子集来探索解空间。本研究开发了一种定制的ALNS算法，其中包含多种破坏和修复算子以及温度递减接受准则。具体而言，设 $\mathcal{X}_s = \{x_{s,k,r,i,j}, a_{s,s,i,g_n,s,i,k,r}, y_{k,r}, S_{S,i}, T_{s,t,k,r}, T_{end,k,r}\}$ 表示服务类型 $s$ 子问题的一个可行解。从初始可行解 $\mathcal{X}_{s,0}$ 出发，ALNS通过以下步骤生成暖启动解：

(1) 选择一个破坏算子从当前解中部分移除任务，其中移除任务的数量由从预定义区间中随机抽取的破坏比确定；

(2) 应用修复算子将移除的任务重新插入；

(3) 根据概率接受规则决定是否接受所得候选解；

(4) 根据算子的历史表现自适应更新破坏和修复算子的选择概率；

(5) 当满足停止准则时，记录并返回最佳可行解 $\mathcal{X}_{s,\text{best}}$。

3.3节中开发的子问题所使用的定制ALNS的详细过程如下。

**● 初始解构建。** 初始解 $\mathcal{X}_{s,0}$ 使用顺序插入启发式方法构建。具体而言，首先根据所有任务 $i \in T_s$ 的最早可行开始时间 $e_i$ 对其进行排序。然后将任务逐个插入到在车辆 $k \in K_s$ 和趟次索引 $r \in R_s$ 上定义的多趟次车辆路线结构中。对于每个任务 $i$，评估所有车辆-趟次组合中的可行插入位置。若插入能保持分配约束(14)、基于路线时间传播的时间窗约束(20)以及（适用时）每趟容量约束(24)的可行性，则该插入为可行。在所有可行插入中，选择使增强子问题目标 $G_s(\cdot)$ 值最小的插入。此过程重复进行直到所有任务分配完毕，从而得到一个完整的可行初始解。

**● 破坏算子。** 在每次ALNS迭代中，一个破坏算子从当前解 $\mathcal{X}_s$ 中移除一部分任务，暂时松弛与这些任务相关的分配和路由决策。采用不同的破坏策略以多样化搜索，包括：(a) 随机移除，以均匀随机方式选择任务；(b) 基于成本的移除，针对对旅行成本边际贡献大的任务；(c) 基于关联度的移除，移除空间上或时间上接近的任务。

**● 修复算子。** 给定包含未分配任务 $D$ 的部分解，修复算子逐个将任务重新插入到可行位置。对于每个任务 $i \in D$，在容量、时间窗和趟次串行约束下考察所有可行的车辆-趟次-位置组合。采用两种主要修复原则：(a) 贪心插入，选择使 $G_s(\cdot)$ 增量最小的插入；(b) 后悔值插入，优先处理次优插入显著差于最优插入的任务。未分配任务 $i$ 的后悔值定义为其次优和最优可行插入成本之差，如式(38)所示，其中 $\Delta G_s^{(1)}(i)$ 和 $\Delta G_s^{(2)}(i)$ 分别表示任务 $i$ 在所有可行车辆-趟次-位置插入中最小和第二小的增强子问题目标 $G_s(\cdot)$ 增量。修复阶段持续进行直到所有任务重新插入并恢复完整可行解。

(38) $Regret(i) = \Delta G_s^{(2)}(i) - \Delta G_s^{(1)}(i)$

**● 算子选择。** 在ALNS框架中，破坏和修复算子根据其在搜索过程中的历史表现以自适应方式选择。设 $\Omega^-$ 和 $\Omega^+$ 分别表示破坏和修复算子集合。对于每个算子 $o \in \Omega^- \cup \Omega^+$，在第 $t$ 次迭代维护一个非负权重 $w_o^t$，反映其生成高质量解的有效性。在每次ALNS迭代中，通过轮盘赌机制选择一个破坏算子 $d \in \Omega^-$ 和一个修复算子 $r \in \Omega^+$，其中破坏算子 $d$ 的选择概率 $p_d^t$ 和修复算子 $r$ 的选择概率 $p_r^t$ 由式(39)和式(40)给出：

(39) $p_d^t = \frac{w_d^t}{\sum_{d' \in \Omega^-} w_{d'}^t}, \quad d \in \Omega^-$

(40) $p_r^t = \frac{w_r^t}{\sum_{r' \in \Omega^+} w_{r'}^t}, \quad r \in \Omega^+$

在每次ALNS迭代后，根据所得候选解的质量评估所选破坏和修复算子的表现。具体而言，为每个所选算子 $o \in \Omega^- \cup \Omega^+$ 分配一个非负分数 $\pi_o^t$，反映其对改进目标值或生成可接受解的贡献。在预定义的更新区间内，根据算子 $o$ 的累积分数和在该区间内的使用频率计算其平均分数 $\bar{\pi}_o^t$，即累积分数除以算子 $o$ 在更新区间内被选择的次数。然后使用平滑方案更新算子权重：

(41) $w_o^{t+1} = (1-\eta) w_o^t + \eta \bar{\pi}_o^t, \quad o \in \Omega^- \cup \Omega^+$

其中 $\eta \in (0,1)$ 为控制近期算子表现相对于历史经验影响的参数。设 $\mathcal{X}_s$ 为当前解，$\tilde{\mathcal{X}}_s$ 为经破坏-修复循环后得到的候选解，其目标值分别记为 $G_s(\mathcal{X}_s)$ 和 $G_s(\tilde{\mathcal{X}}_s)$。$\pi_o^t$ 的计算方法如下：若 $G_s(\tilde{\mathcal{X}}_s) < G_s(\mathcal{X}_{s,\text{best}})$，则 $\pi_o^t = \pi_1$；若 $G_s(\tilde{\mathcal{X}}_s) < G_s(\mathcal{X}_s)$，则 $\pi_o^t = \pi_2$；若 $\tilde{\mathcal{X}}_s$ 被接受，则 $\pi_o^t = \pi_3$；其他情况 $\pi_o^t = 0$，且满足 $\pi_1 > \pi_2 > \pi_3 > 0$。这种自适应权重更新机制使能持续生成高质量或改进解的算子在后续迭代中获得更高的选择概率，从而在搜索过程中维持探索与利用之间的平衡。

**● 接受准则。** 接受规则定义如下：若 $G_s(\tilde{\mathcal{X}}_s) \leq G_s(\mathcal{X}_s)$，则候选解始终被接受；否则，接受概率随目标恶化程度增加而降低。这种概率接受机制使搜索能够逃离局部最优，同时逐渐向解空间的高质量区域集中。具体而言，定义目标变化量：

(42) $\Delta G_s = G_s(\tilde{\mathcal{X}}_s) - G_s(\mathcal{X}_s)$

候选解按以下方式接受：

(43) $\text{Pr}(\text{accept } \tilde{\mathcal{X}}_s) = \begin{cases} 1, & \Delta G_s \leq 0 \\ \exp\left(-\dfrac{\Delta G_s}{\Theta(t)}\right), & \Delta G_s > 0 \end{cases}$

其中 $\Theta(t)$ 为时间依赖的温度参数。温度递减机制旨在增强早期阶段的全球搜索能力，同时逐步将搜索转向后期阶段的局部精化，从而提高算法的整体鲁棒性。线性冷却方案如下：

(44) $\Theta(t) = \Theta_0 + (\Theta_{\min} - \Theta_0) \cdot \min\left\{1, \dfrac{t}{t_{\max}}\right\}$

其中 $t$ 表示已运行时间，$t_{\max}$ 为预定义的时间限制，$\Theta_0$ 和 $\Theta_{\min}$ 分别表示初始温度值和最小温度值。

图3展示了ALNS启发式算法中使用的破坏和修复策略。考虑了三种破坏算子，包括随机移除、基于边际旅行成本贡献的成本移除以及联合移除空间和时间内接近任务的关联度移除。在修复阶段，移除的任务使用贪心插入（选择成本最低的可行插入）或后悔值插入（优先处理后悔值最大的任务）重新插入。

图3. ALNS启发式算法中使用的破坏和修复策略。

整体ALNS过程总结于算法2中。

**算法2 子问题的自适应大邻域搜索**

输入：可行初始解 $\mathcal{X}_{s,0}$；破坏算子集合 $\Omega^-$；修复算子集合 $\Omega^+$；最大迭代次数 $N_{\max}$ 和时间限制；

输出：最佳可行解 $\mathcal{X}_{s,\text{best}}$

1: 初始化 $\mathcal{X}_s \leftarrow \mathcal{X}_{s,0}, \mathcal{X}_{s,\text{best}} \leftarrow \mathcal{X}_s$

2: 初始化算子权重 $w^-, w^+$

3: **repeat**

4:  根据 $w^-, w^+$ 选择破坏算子 $d \in \Omega^-$ 和修复算子 $r \in \Omega^+$

5:  生成候选解 $\tilde{\mathcal{X}}_s \leftarrow r(d(\mathcal{X}_s))$

6:  **if** 根据接受准则 $\tilde{\mathcal{X}}_s$ 被接受 **then**

7:   $\mathcal{X}_s \leftarrow \tilde{\mathcal{X}}_s$

8:  **end if**

9:  **if** $G_s(\tilde{\mathcal{X}}_s) < G_s(\mathcal{X}_{s,\text{best}})$ **then**

10:   $\mathcal{X}_{s,\text{best}} \leftarrow \tilde{\mathcal{X}}_s$

11:  **end if**

12:  根据式(41)更新算子权重 $w^-, w^+$

13: **until** 满足停止准则

14: **return** $\mathcal{X}_{s,\text{best}}$

所提方法的整体求解框架如图4所示。

图4. 多类型GSE调度的整体求解框架。

## 5. 案例研究

### 5.1 初步介绍

本节使用天津滨海国际机场的航班数据来评估所提模型的性能。首先介绍实验中使用的数据集、参数设置和计算环境。其次检验所提基于ALNS的暖启动策略的有效性，并将其与几种经典启发式方法以及商业求解器的求解过程进行比较，进一步开展实验评估不同ALNS参数设置的影响。第三分析所提方法获得的整体调度结果，重点关注收敛行为以及不同准则对应的目标值。最后对关键参数进行敏感性分析，为所提方法和实际机场GSE调度运营提供管理洞察。

使用一天的机场运行数据进行计算实验和分析。基于现有实际机场运行研究文献中报告的工作负荷水平，采用每天每辆车七项任务的保守基准来确定各类GSE的车队规模（Andreatta et al., 2014a,b; Schyns, 2015; Soltani et al., 2020; Ahmadi and Akgunduz, 2023; Wu et al., 2023; Zhou et al., 2023; Bao et al., 2025; Zhou et al., 2025），机场的详细运行信息汇总于表3中，以说明实验问题的规模。具体而言，案例研究中考虑了六种飞机型号，涵盖窄体和宽体飞机。服务时间在不同飞机和服务类别之间有所不同，以反映异质性运营需求，表4中汇总的服务时间根据运营调查确定。任务时间窗根据航班计划和服务前后关系确定，其中最早可行服务时间基于运营流程和上游服务完成要求推导，而最晚可行服务时间受计划离港时间和下游服务完成要求约束。停机位之间的旅行时间根据停机位位置和机场空间布局估算。此外，各服务类别的任务分布遵循实际运营特征。具体而言，过站航班包含八项服务任务，而出港航班不包含行李卸载操作，因此包含七项服务任务，案例研究中总共有1512项服务任务。

**表3. 机场运行信息汇总**

| 实体 | 规模 |
|------|------|
| 出港航班（仅出港） | 64 |
| 过站航班 | 133 |
| 飞机型号 | 6 |
| 停机位 | 48 |
| 任务类型 | 8 |
| 总任务数 | 1512 |
| 车辆数 | 216 |
| 前后关系 | 1315 |

**表4. 各飞机型号和服务类别的服务时间（分钟）**

| 飞机型号 | 行李卸载 | 行李装载 | 餐饮 | 加水 | 排污 | 清洁 | 加油 | 牵引 |
|----------|----------|----------|------|------|------|------|------|------|
| A | 13 | 13 | 8 | 15 | 11 | 11 | 10 | 5 |
| B | 13 | 13 | 8 | 16 | 11 | 12 | 10 | 5 |
| C | 14 | 14 | 9 | 17 | 12 | 13 | 11 | 5 |
| D | 15 | 15 | 10 | 18 | 13 | 14 | 12 | 6 |
| E | 21 | 21 | 15 | 22 | 19 | 21 | 19 | 8 |
| F | 23 | 23 | 17 | 24 | 21 | 23 | 21 | 9 |

算法中的初始关键参数列于表5中，包括增强拉格朗日框架的协调参数和ALNS过程中使用的启发式控制参数。所列参数值基于初步数值测试选取，以确保数值稳定性和计算效率。

关键模型参数，包括主问题中的目标权重系数以及每种车型的车队规模，将在第5.4节中进一步探讨。所有计算实验均在Python中实现，并在一台配备Intel Core Ultra 9 285H处理器（运行频率2.90 GHz）和32 GB内存的64位系统上执行。

表5. 关键算法参数总结。

AL框架

| 参数 | 值 | 参数 | 值 |
|------|-----|------|-----|
| ρ? | 1 | T_max | 20 |
| ρ_max | 10000 | tL | 500 |
| τ | 2 | ε | 0.001 |
| κ | 0.9 | α, β | 0.8, 0.2 |

ALNS启发式

| 参数 | 值 | 参数 | 值 |
|------|-----|------|-----|
| 初始温度 | 300 | 最终温度 | 0.1 |
| 破坏比例 | [0.1, 0.25] | 每次ALNS运行时间 | 300 |
| π?, π?, π? | 5, 3, 1 | R_max | 5 |

5.2. 子问题求解过程结果

本节进行了两组实验：(i) 比较不同的基于启发式的暖启动生成方法和直接商业求解器求解方法；(ii) 研究ALNS关键组件的影响，包括破坏比例和解决方案接受准则，以评估所提出设计的有效性。实验聚焦于一次迭代中的水服务车辆子问题，其中300秒的启发式暖启动程序与1000秒的商业求解器相结合，以评估其性能。

在第一组实验中，考虑了两种用于暖启动生成的基线方法：(1) 仅改进的贪心插入启发式与局部搜索（GILS）；(2) 基于相同邻域移动和可行性检查的禁忌搜索（TS）。具体而言，GILS首先通过将所有未分配任务依次插入到所有车辆中最佳可行位置来构建初始可行多行程计划，其中位置的选择以在尊重时间窗、容量限制和行程序列约束的同时，使子问题目标函数的增量增加最小化。然后通过轻量级局部搜索进行细化，该局部搜索应用标准的重定位和交换移动，并且仅接受改进的解决方案。TS从相同的贪心初始解决方案开始，探索相同的移动集合，但允许非改进移动以逃离局部最优。除了这两种启发式暖启动基线外，还包含了一种使用商业MILP求解器Gurobi而不进行任何暖启动的直接求解方法作为参考。

在第二组实验中，设计了所提出的基于ALNS的暖启动方法的四个变体，以检查关键组件的影响。具体而言，两个变体通过采用较低和较高的移除比例来修改破坏比例，以评估解决方案质量和收敛行为对邻域扰动程度的敏感性。其余两个变体将所提出的温度递减接受准则替换为替代的接受规则：(i) 仅接受改进解决方案的贪心接受规则，以及(ii) 对数概率接受规则，其中接受概率是目标恶化的单调函数。所有比较方法的收敛行为（目标值表示行驶成本）如图5所示。

图5. 所提出方法与基线方法收敛行为的比较。蓝色曲线显示最佳可行解的演变，橙色曲线显示当前接受的启发式解，绿色曲线显示最佳下界。垂直虚线表示从启发式暖启动生成到基于MILP的优化的过渡。

结果表明，所提出的基于ALNS的暖启动策略在启发式阶段结束时和随后的MILP优化后，始终比所有基线方法获得更低的目标值。与GILS和TS暖启动相比，所提出的方法产生了质量明显更高的初始解，这使得商业求解器能够更有效地进一步改进当前解。值得注意的是，当不提供暖启动时，商业求解器无法在规定的1300秒时间限制内获得可行当前解。经过预求解后，生成的MILP仍然包含超过700,000个变量和260,000个约束。在分支定界过程中，探索了超过4000个节点，最大深度为49，而求解器仅能将在终止前将最佳下界改进到28.54。此外，消融研究表明，破坏比例和解决方案接受机制是在探索和开发之间取得平衡的关键因素。具体而言，所提出的基于温度的策略在早期搜索阶段鼓励探索，并逐渐转向后期阶段的开发，而过大或过小的破坏比例都会对识别高质量解决方案产生不利影响。

5.3. 多类型服务车辆调度结果

本节评估了所提出的两级增广拉格朗日框架在多种GSE集成调度中的性能。实验研究了增广拉格朗日公式在求解过程中的收敛行为，以及主问题确定的全局任务开始时间与服务类型子问题获得的局部优化计划之间的渐进对齐情况。然后从主层级延迟和鲁棒性性能以及不同类型服务车辆车队产生的行驶成本方面评估所得计划。此外，所提出的框架与仅基于主层级全局开始时间直接执行计划的基线方案进行了比较。

所提出的增广拉格朗日框架的收敛行为如图6所示，从每次迭代的子问题解中获得的主层级和子问题层级目标值如图7所示。通过逐渐增加罚参数ρ，主问题与服务类型子问题之间的耦合逐渐增强，这将残差r驱向零。如图6所示，残差在协调过程中稳步下降，并在约14次迭代后接近零，表明全局和局部任务开始时间逐渐达成共识。在早期迭代中，局部最优子问题解的聚合仍然在全局上是不可行的，并导致主层级在延迟和鲁棒性方面表现不佳。具体而言，如图7所示，总延迟最初约为200分钟，而鲁棒性指标保持在接近零的水平。随着全局和局部任务开始时间逐渐对齐，子问题解在全局上变得可行，主层级延迟和鲁棒性目标逐渐改进。延迟下降到约32.8分钟，而收敛后鲁棒性指标增加到约5.1分钟。同时，分块优化过程保留了合理的路由方案，防止了不可行解决方案或过高的行驶成本。虽然总行驶成本最初随着更强的共识执行限制了局部最优路由决策而增加，但在最终迭代中逐渐稳定在1240.8左右。结果表明，所提出的框架在增广拉格朗日方案中有效地协调了全局可行性和局部效率。

除了与直接聚合子问题层级解而不进行协调的方案进行比较外，还考虑了另一个基线，其中全局任务开始时间固定为主问题获得的初始解，并随后用于指导子问题调度。比较结果如图8所示。固定全局开始时间的基线无法为补水服务生成可行解，对于剩余的服务类型，其行驶成本高于所提出的AL协调方法。这表明，当主问题被孤立求解时，它仅关注全局延迟和鲁棒性目标，而所得任务开始时间并未考虑服务特定的可行性和局部成本效率。通过迭代协调可行的主问题和子问题解，所提出的AL协调框架逐渐对齐全局和局部计划，确保两个层级的可行性，同时考虑主问题和服务类型子问题的目标以获得有效解。

图8. 所提出的AL协调方法与仅主问题基线之间的服务类型行驶成本比较。

为进一步检验所提出协调框架的性能，考虑了基于贪心和局部最优决策的基线。具体而言，对于每架航班，地面服务任务根据预定义的优先和非重叠关系依次调度，每个任务被分配满足航班内约束的最早可行开始时间。对于执行顺序可交换的任务对，序列根据局部时间考虑贪心地决定，选择导致后续任务延迟最小的顺序。一旦所有任务开始时间固定，这些全局时间被独立地施加于每种服务类型。对于每个服务车队，使用贪心插入策略构建车辆路线，其中任务按固定开始时间的递增顺序处理，并在车辆路线中分配到可行位置，受可行性约束。在所有插入选项中，选择增量行驶成本最小的选项。表6比较了所提出的基于AL的协调框架与贪心局部基线的调度性能。结果表明，贪心基线实现了更低的航班延迟，因为它基于最早可行和局部最优决策分配任务开始时间。然而，由于本研究中的鲁棒性定义为优先相关任务对之间的最小内部时间间隔，贪心策略本质上导致鲁棒性值接近0分钟。相比之下，所提出的框架通过最大化优先相关任务之间的最小内部任务间隔的max-min协调机制，将总车辆行驶成本降低了约46.1%，同时提高了计划鲁棒性。这些结果突出了所提出的协调框架与贪心局部基线相比，在延迟、鲁棒性和路由效率之间实现了更平衡的权衡。

表6. 所提出的基于AL的协调框架与贪心局部基线之间的性能比较。

| | 基于AL的协调 | 基线 | 相对变化 |
|---|---|---|---|
| 延迟（分钟） | 32.8 | 26.6 | ?23.3% |
| 鲁棒性（分钟） | 5.1 | ? | ? |
| 行驶成本（分钟） | 1240.8 | 2302.7 | 46.1% |

图9展示了最终调度结果中获得的四个可行飞机地面服务任务执行场景。所得计划符合机场运营中的关键运营约束。具体而言，行李卸载在行李装载之前完成，牵引任务在所有其他地面服务完成后安排，行李处理和加油操作在时间上分离以满足安全要求，污水服务和补水任务不同时执行。这些执行模式证实了所获得解决方案在复杂服务交互约束下的实际可行性。

5.4. 参数敏感性分析

本节对模型的几个关键参数进行敏感性分析，以检查不同的管理偏好和运营约束如何影响调度解决方案。具体而言，研究了三组参数。首先，通过分析主问题中两个目标之间的协调来研究，通过改变它们的相对重要性，包括采用不同权重系数的线性加权总和公式以及强制最小鲁棒性要求的ε约束公式。其次，通过调整每辆车辆允许的最大行程数来检查工作量平衡的影响，这会影响任务在车辆中的分布以及由此产生的行驶成本。第三，通过改变可用车辆的总数来评估车队规模的影响，以展示资源可用性与运营性能之间的关系。这些实验提供了所提出方法相对于关键建模参数的敏感性见解，并为机场地面服务运营中的实际决策提供了定量指导。

使用线性加权总和和ε约束公式在不同管理偏好设置下调度性能的敏感性分析结果如表7所示。在线性加权总和公式下，延迟和鲁棒性目标随着分配的权重系数而变化。这允许决策者调整两个目标的相对重要性。然而，从不同权重组合获得的解决方案并不总是Pareto有效的。例如，与权重设置(0.7,0.3)下的解决方案相比，以(0.6,0.4)获得的解决方案被支配，因为它表现出更大的延迟、更高的行驶成本和更低的鲁棒性。在ε约束公式下，决策者可以基于专业知识或历史性能调节最小鲁棒性要求，同时优化延迟和行驶成本。此外，随着鲁棒性区间增加，服务车辆的时间窗变窄，这导致可行解空间收缩和行驶成本增加，而过大的鲁棒性区间可能使全局调度问题不可行。因此，在实际调度中，建模方法和参数设置的适当组合对于实现平衡且可实施的调度解决方案至关重要。

# 线性加权求和与ε-约束方法下不同管理者偏好设置对调度性能的敏感性分析

其中"inf."表示模型在相应参数下不可行。

## 线性加权求和 (α, β)

| (α, β) | (0.1, 0.9) | (0.2, 0.8) | (0.3, 0.7) | (0.4, 0.6) | (0.5, 0.5) | (0.6, 0.4) | (0.7, 0.3) | (0.8, 0.2) | (0.9, 0.1) |
|---|---|---|---|---|---|---|---|---|---|
| 延误（分钟） | 45 | 42.2 | 40.3 | 37.2 | 35.4 | 34.6 | 33.2 | 32.8 | 32.6 |
| 鲁棒性（分钟） | 6.7 | 6.4 | 5.9 | 5.7 | 5.5 | 5.1 | 5.2 | 5.1 | 4.9 |
| 行驶成本（分钟） | 1527.4 | 1446.8 | 1403.7 | 1388.2 | 1358.5 | 1317.4 | 1247.1 | 1240.8 | 1222.7 |

## ε-约束方法

| ε | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 延误（分钟） | 32.6 | 33.2 | 34.6 | 35.4 | 37.2 | 40.3 | inf. | inf. | inf. |
| 鲁棒性（分钟） | 1.0 | 2.1 | 3.0 | 4.0 | 5.1 | 6.0 | inf. | inf. | inf. |
| 行驶成本（分钟） | 1222.7 | 1247.1 | 1317.4 | 1358.5 | 1388.0 | 1438.5 | inf. | inf. | inf. |

除行驶成本外，单类型GSE调度中还考虑的优化目标包括机队的负载均衡和车辆的有效利用率（Li等，2017；Liu等，2019；Guo等，2020）。在实际运营中，过度的工作负荷不平衡可能导致运营风险和鲁棒性降低，而过于保守的车辆使用方式则可能导致运营成本增加。通过初步分析发现，机队内部的负载均衡程度与每辆车允许的最大行驶次数 $R_{max}$ 密切相关。因此，设计以下敏感性实验来研究 $R_{max}$ 和机队规模对调度性能的影响。

第二组实验通过改变每辆车允许的最大行驶次数 $R_{max}$ 来研究负载均衡的影响。该参数直接影响服务任务在车辆之间的分配方式。具体来说，$R_{max}$ 被设置为四个不同的递增值（3、4、5、6）。对于每个设置，分析车辆行驶次数的分布以反映机队内部的负载均衡程度。此外，计算最终调度方案的总行驶成本，以评估不同行驶次数限制对路径效率的影响。结果如表7和图10所示，其中表8中的方差代表机队内部的负载均衡程度，数值越大表示车辆工作负荷的分布越不平衡。当 $R_{max}$=3时，调度问题变得不可行，因为过于严格的行驶次数限制降低了机队的服务容量。当 $R_{max}$ 从4增加到6时，总行驶成本降低，而车辆行驶次数的方差增大，揭示了路径效率与负载均衡之间的权衡。然而，增加 $R_{max}$ 并不会显著改善全局延误或鲁棒性。这表明更严格的行驶次数限制会导致车辆工作负荷分布更均匀，但行驶成本更高，而更宽松的限制则以工作负荷不平衡为代价降低了行驶成本。

下载：下载高分辨率图片（201KB）
下载：下载全尺寸图片

**图10.** 不同最大行驶次数限制下的三个考虑目标。

**表8.** 机队内部的负载均衡程度。

| $R_{max}$ | 执行k次行驶的车辆数量 | 方差 |
|---|---|---|
| | k=0 | k=1 | k=2 | k=3 | k=4 | k=5 | k=6 | |
| 3 | inf. | inf. | inf. | inf. | inf. | inf. | inf. | inf. |
| 4 | 0 | 8 | 9 | 7 | 4 | 2 | 6 | 2 | 7 | 1.03 |
| 5 | 0 | 7 | 17 | 7 | 3 | 0 | 22 | 1 | 6 | 1.49 |
| 6 | 1 | 7 | 6 | 8 | 5 | 5 | 2 | 6 | 15 | 17 | 18 | 2.94 |

不同最大行驶次数限制下的车辆行驶次数分布和行驶成本，其中"inf."表示模型在相应参数下不可行。

第三组实验通过改变每辆车分配的平均任务数来考察机队规模的影响。具体来说，每辆车的平均任务负载设置为三个递增水平（6、7和8），相应地导致机队规模分别为252、216和189辆车。结果如图11所示。当机队规模从189辆车增加到252辆车时，总航班延误减少，表明更大的机队有效地缓解了地面服务运营中的运力短缺问题。同时，由于任务分配更加分散，总行驶成本随机队规模增加而上升。相比之下，增加车辆可用性的对改善计划鲁棒性的效果有限。这些结果表明，扩大机队是减少延误的有效方式，但在鲁棒性方面收益有限，并可能带来额外的运营成本。

下载：下载高分辨率图片（199KB）
下载：下载全尺寸图片

**图11.** 不同机队规模下的三个考虑目标。

## 6. 结论与未来工作

本文研究了一种多类型地面支持设备（GSE）运营的集成调度问题，其中异质服务任务在有限信息共享条件下由多个运营利益相关方执行。所考虑的问题涉及具有复杂优先级关系的任务、时空冲突、车辆容量约束以及多次行驶执行特征。为应对有限信息共享和集成调度问题大规模性质带来的挑战，提出了一种基于两级增广拉格朗日的协调优化框架。在该框架中，主问题通过联合最小化航班出发延误和增强计划鲁棒性来确定全局任务开始时间，而一组服务类型子问题独立优化车辆路径规划和局部调度决策。为高效求解所产生的大规模和强耦合问题，将基于ALNS的温启动策略嵌入增广拉格朗日协调过程中，以提高求解效率和质量。

计算实验表明，所提出的方法收敛稳定，并能产生高质量的可行调度方案。与贪婪或无协调的基线方法相比，所提出的框架在保持计划鲁棒性的同时降低了总车辆行驶成本，代价是航班延误的适度增加。敏感性分析进一步揭示了管理者偏好和运营参数对调度性能的影响，突出了在不同目标权重设置和ε-约束水平下延误性能、鲁棒性和车辆行驶成本之间的权衡。关于负载均衡和机队规模的额外实验表明，更严格的行驶次数限制和更小的机队可以提高工作负荷公平性和延误性能，但代价是更高的行驶成本，而更宽松的约束虽降低了行驶成本，但可能导致工作负荷不平衡。

尽管所提出的框架具有优势，但仍有多项扩展可在未来研究中探讨。首先，当前模型主要关注停靠廊桥机位的离港操作。未来研究可纳入额外的优化目标和运营约束，以联合建模到达航班、远机位操作、摆渡车调度和旅客上下机过程，从而实现更为全面的机场过站协调框架。其次，增广拉格朗日协调框架采用单调递增的惩罚参数来促进主问题与子问题解之间的一致性。可进一步研究更具自适应性的惩罚更新策略，以更好地平衡收敛速度和求解质量。最后，尽管引入了鲁棒性指标以增强计划的稳定性，但这可能导致保守的调度决策。纳入不确定性信息，如天气状况和延误分布，可以实现更为精细的鲁棒性度量。

## CRediT作者贡献声明

| 作者 | 贡献 |
|---|---|
| Yutong Wei（魏雨桐） | 概念化、方法论、软件、原稿撰写 |
| Jian Zhang（张健） | 数据整理、方法论、监督、审稿与编辑 |
| Haiyan Zhang（张海燕） | 调查研究、软件、原稿撰写 |
| Jie Ouyang（欧阳杰） | 资源、监督、验证 |
| Xunming Yuan（袁训明） | 概念化、数据整理、调查研究 |

**Yutong Wei | Haiyan Zhang | Jie Ouyang | Xunming Yuan**

江苏省城市智能交通系统重点实验室，东南大学交通运输学院智能交通与空间信息学系，南京，211189，中国