面向港湾机坪的停机位指派优化

姜伟华，王雅莎，姜雨，胡志韬，张洪海; JIANG Weihua; WANG Yasha; JIANG Yu; HU Zhitao; ZHANG Honghai

2025年5月14日 23:34 星期三

网刊加载中。。。

使用Chrome浏览器效果最佳，继续浏览，你可能不会看到最佳的展示效果，

确定继续浏览么?

复制成功，请在其他浏览器进行阅读

面向港湾机坪的停机位指派优化 PDF

- ORCID：
姜伟华 ¹
- ORCID：
王雅莎 ²
- ORCID：
姜雨 ²
✉
- ORCID：
胡志韬 ³
- ORCID：
张洪海 ⁴

1. 南京航空航天大学金城学院, 南京 211156； 2. 南京航空航天大学民航学院, 南京 211106； 3. 东南大学交通学院, 南京 211189； 4. 南京航空航天大学通用航空与飞行学院, 南京 211106

中图分类号： V351.11

最近更新：2023-12-22

DOI：10.16356/j.1005-2615.2023.06.014

摘要

停机位指派问题是机场运营管理的核心问题。现有的停机位指派问题研究集中在提高停机位的利用效率上，而忽略了停机坪的运行安全。针对这一问题，本文以最大化近机位利用率和最小化鲁棒性损失为目标，提出一个考虑港湾安全约束的停机位指派模型；提出一种可精确求解面向港湾机坪的停机位指派问题的分支定价算法；利用机场实际数据验证提出的模型和算法。实验结果表明，在小、中、大规模算例中分支定价的最优解比CPLEX分别改进了0.3%、17.3%、26.7%，在中大规模算例中有明显的优势。在小、中、大规模算例中，本文的设计能分别预先避免27.16%、16.35%、11.01%的航空器发生港湾冲突。在提高近机位利用率和指派计划鲁棒性的同时，提高了机坪的安全性。

关键词

航空运输; 大规模优化问题; 停机位指派; 港湾机坪; 分支定价

近年来，中国民航事业保持高速发展态势，民航运输总量持续增长。优化机场场面资源管理对缓解机场负荷、提高机场运行效率有重要作用。停机位指派是机场场面运行管理工作中的核心问题，尤其在大型机场中停机坪空间拥挤，航空器停放距离较近，容易造成滑行冲突。研究停机位的优化指派问题对提高机位利用效率和机坪安全性有重要意义。

停机位指派问题有多种优化目标，国内外学者针对不同优化目标进行广泛的研究。Yu等^［

1］以最小化旅客的步行距离和最大化机位鲁棒性为目标，建立停机位预指派模型；Liu等^{［参考文献 2

百度学术}2］以停机位空闲时间离散度最小为目标，优化停机位指派；Maharjan等^{［参考文献 3

百度学术}3］考虑航空器滑行至不同机位的燃油消耗差异，最小化航空器的总滑行成本；姜雨等^{［参考文献 4

百度学术}4］最小化旅客中转步行距离和远机位旅客数，建立多目标的停机位实时指派模型；王超等^{［参考文献 5

百度学术}5］考虑不同发动机的燃油流率，最小化滑行中的燃油消耗。

停机位的指派受到多种因素限制。一些学者扩展了停机位指派问题的基本约束，Li等^［

6］结合航空器前后间隔时间的弹性缓冲时间约束，提高机位指派方案的抗干扰性；在机坪安全问题上，Wang等^{［参考文献 7

百度学术}7］建立考虑相邻机位机型限制的停机位指派网络流模型；余青华^{［参考文献 8

百度学术}8］提出基于机坪管制移交的U形机坪运行优化策略，实时解脱机坪内的航空器冲突。

停机位指派问题是一个NP‑Hard问题^［

9］，在求解算法上，国内外学者取得较多的研究成果。启发式算法被广泛地用于停机位指派问题的求解。李倩雯^{［参考文献 10

百度学术}10］提出一种免疫遗传算法，改进了停机位指派问题中常用的传统遗传算法；Diepen等^{［参考文献 11

百度学术}11］在模糊推理系统中引入了蜂群优化算法求解考虑不确定性的停机位指派问题，具有快速收敛性能；Benlic等^{［参考文献 12

百度学术}12］提出了求解机位指派问题的突破局部搜索算法，它可以自适应调整邻域算子。

与启发式方法不同的是，精确式算法能得到停机位指派问题的精确最优解，但求解难度更大。Castaing等^［

13］建立考虑不确定性的停机位指派随机优化模型并设计随机优化算法求解；Guépet等^{［参考文献 14

百度学术}14］提出了一种更紧凑的停机位指派整数规划模型，并设计基于空间和时间的分解算法来减少案例的规模，由求解器精确求解分解的案例；Karsu等^{［参考文献 15

百度学术}15］将停机位指派问题建模为非线性规划模型，并开发分支定界搜索算法提高精确解的质量；李云鹏等^{［参考文献 16

百度学术}16］结合航班延误构建停机位指派的整数规划模型，用CPLEX对31个停机位的指派问题进行精确求解。

近年来，一些学者从建模方法的角度强化停机位指派模型，尤其是基于分支定价的方法。Diepen等^［

11］将列生成嵌入分支定界框架，设计了大规模停机位指派问题的精确求解算法；Li等^{［参考文献 6

百度学术}6］提出了一种基于子模块化方法的定价方法，在停机位指派中最小化到达航班地面延误。

纵观过往相关研究，大多较为注重机场运行效率的提升，忽视机位分配与机坪运行安全问题之间的联系，但目前停机坪的安全问题日益突出。在求解算法上，高效精确的求解大规模停机位指派问题仍面临着很多挑战。在求解停机位指派问题的分支定价算法上也存在许多待改进的设计。因此，本文设计一种结合停机位运行效率和港湾安全约束的停机位指派优化方法，扩展传统的停机位指派模型，在预先避免冲突的条件下提高机型的运行效率，并设计高效精确求解停机位指派问题的分支定价方法。

1 面向港湾机坪的停机位指派问题

停机位指派问题是在未来的一段规划期间，为机场内的航空器安排合理的停机位，使每一架航空器都停放在合适的位置，并满足整体的优化目标。停机位指派是一个大规模的多目标多约束的优化问题。在大型机场中限制停机位指派的因素有很多，在该问题中要尽量提高近机位资源的利用率，同时兼顾航空器的安全性，尽量避免机坪内两架航空器的冲突。

在大型机场中由于机坪空间布局的限制，需要考虑更严格的安全限制。本文提出面向港湾机坪的停机位指派问题，定义“港湾机坪”为机位间物理空间相对拥挤，机坪滑行路线、停止等待点重合交错的机坪区域，在充分分析“港湾机坪”内航空器运行冲突机制的基础上，优化停机位指派。

2 模型构建

2.1　模型假设

本文针对港湾机坪的停机位分配问题的假设和规则如下：

（1）不考虑航空器的拖曳，将进场航班和对应的离场航班看作一个分配单位。

（2）确定性假设，本文做确定性优化，不考虑停机位指派问题中的随机性。

（3）信息完备假设，与航空器和机场机位有关的信息是已知的，包括航班的到达时间和起飞时间、机型等，机场的机位容量、机位分布、机坪滑行路线等。

2.2　模型构建

机场的停机位集为 $G$ ，停机位为 $k$ （ $k \in G$ ），近机位集为 $G_{0}$ ，远机位集为 $G_{n + 1}$ 。在规划周期内该机场起降的航空器节点 $i \in F = {1,2, \dots, n}$ 。航空器 $i$ 的计划进场时间为 $a_{i}$ ，计划离场时间为 $d_{i}$ 。本文将停机位指派问题建模为商品流模型，航空器作为商品在机位上流动。定义停机位指派问题的决策变量 $x_{i, j}^{k}$ 如下

x_{i, j}^{k} = \{\begin{matrix} 1 & 航空 器 i 和 j 连续 停放 在停 机位 k \\ 0 & 其他 \end{matrix}

（1）

基于弧变量建模有利于减少决策变量数量和避免出现二次项，本文额外定义虚拟航空器起始节点 $s$ 、虚拟航空器终止节点 $t$ 。虚拟航空器节点 $s$ 的时间窗为规划最早时间， $t$ 是时间窗为规划最晚时间。

由于航班国内外属性、航空公司、航空器机型和航空器大小等因素的限制，停机位和航空器间存在着兼容性约束。因此，本文定义允许停放航空器 $i$ 的机位子集 $G_{i} \subseteq G$ ，且 $G_{i} \neq \emptyset, \forall i \in F$ 。定义允许停放在停机位 $k$ 上的航空器子集 $F_{k} \subseteq F$ 。注意到当 $k \in G_{i} ⋂ G_{j}$ ，航空器 $i$ 和 $j$ 都允许停放在停机位 $k$ ， $x_{i, j}^{k}$ 允许取1或0，否则 $x_{i, j}^{k} = 0$ 。

2.2.1　基本约束

（1）流量平衡约束

在弧变量模型中，构成停机位指派可行方案的约束首先是流量平衡约束

\sum_{l \in {F_{k}, s}} x_{l, i}^{k} - \sum_{j \in {F_{k}, t}} x_{i, j}^{k} = 0 \forall i \in F, \forall k \in G

（2）

\sum_{i \in F_{k}} x_{s, i}^{k} \leq 1 \forall k \in G

（3）

\sum_{i \in F_{k}} x_{i, t}^{k} \leq 1 \forall k \in G

（4）

式（2）表示航空器节点的流量守恒；式（3，4）表示所有机位上的流从起始节点 $s$ 流入终止节点 $t$ 。

（2）唯一性约束

\sum_{k \in G} \sum_{j \in {F_{k}, t}} x_{i, j}^{k} = 1 \forall i \in F

（5）

式（5）表示每个航空器 $i$ 必须被分配到一个停机位。

（3）时间间隔约束

\begin{matrix} x_{i, j}^{k} (a_{i} - d_{j} - b) (a_{j} - d_{i} - b) \leq 0 \\ \forall i, j \in {F_{k}, s, t}, \forall k \in G \end{matrix}

（6）

式（6）保证分配到同一停机位的航空器满足一定的前后间隔， $b$ 为连续停放在同一停机位的航空器最小时间间隔。

（4）负载均衡约束

\sum_{i \in {F_{k}, s}} \sum_{j \in {F_{k}, t}} x_{i, j}^{k} \leq N + 1 \forall k \in G

（7）

式（7）限制计划周期内停放在同一个停机位上的航空器数量上限为 $N$ ，均衡了各停机位的负载。

（5）弹性缓冲时间约束

\begin{matrix} x_{i, j}^{k} (T - Δ_{i, j} - Δ_{j, p}) + M x_{j, p}^{k} \leq M \\ \forall k \in G, \forall i, j, p \in {F_{k}, s, t} \end{matrix}

（8）

式（8）表示对停放在同一机位 $k$ 上的航空器间隔时间的弹性缓冲时间约束， $M$ 为极大正数。当航空器 $i 、 j 、 p$ 先后停放在停机位 $k$ 上时，航空器 $i$ 和 $j$ 之间的时间间隔为 $Δ_{i, j}$ ，航空器 $j$ 和 $p$ 之间的时间间隔为 $Δ_{j, p}$ 。为提高指派方案对进场时间和离场时间随机性的抗干扰能力，航空器 $j$ 前后两段间隔时间的总和应不小于预先设定的阈值 $T$ 。

2.2.2　港湾约束

在港湾机坪中，由于机坪空间布局、航空器构型、滑行路线和滑行规则的限制，航空器之间存在着静态冲突和动态冲突。

静态冲突必须预先避免。如图1所示，当大型航空器F1停在停机位G1时，相邻的停机位G2不能使用或只能停放较小的航空器F2。

图1 港湾机坪静态冲突示意

Fig.1 Static conflict in harbor apron

由于空间局限和滑行路线的重合，时间窗临近的航空器在港湾机坪容易产生动态冲突。如图2所示，港湾a中停放在停机位G4的航空器F2阻碍了航空器F1通过G4，使F1只能停放在停机位G1、G2或G3；港湾b中，航空器F3和F4相向滑行，需要管制等待或更改滑行路线。但这种解决方案增加了管理者的负荷，容易导致冲突的连锁反应。

图2 港湾机坪动态冲突示意

Fig.2 Dynamic conflict in harbor apron

基于“预防为主”的原则，通过停机位指派提前避免港湾动态冲突。当同一港湾机坪内的停机位 $k$ 和 $l$ 存在滑行路线冲突，且 $k \in G_{i}$ ， $l \in G_{j}$ ， $m i n (| a_{i} - a_{j} |, | d_{i} - d_{j} |, | a_{i} - d_{j} |, | d_{i} - a_{j} |)$ $\leq τ$ ，其中 $τ$ 为机坪滑行冲突的时间阈值，则航空器 $i$ 和 $j$ 不允许同时停放在停机位 $k$ 和 $l$ 。

为统一表示考虑静态冲突和动态冲突，本文定义港湾冲突集合 $Q \subseteq F^{2} \times G^{2}$ ，其中冲突组合 $(i, k, j, l) \in Q$ ，表示如果航空器 $i$ 停放在停机位 $k$ ，则航空器 $j$ 不允许停放在停机位 $l$ 。

为港湾冲突集合 $Q$ 的所有元素构建港湾冲突约束

\sum_{p \in {F_{k}, t}} x_{i, p}^{k} + \sum_{p \in {F_{k}, t}} x_{j, p}^{l} \leq 1 \forall (i, k, j, l) \in Q

（9）

通过停机位预指派将有潜在冲突的航空器指派在合适的位置，有利于避免航空器发生冲突时的等待，提高机坪安全性和运行效率。

2.2.3　模型目标

目标1 最大化近机位使用率

在停机位指派问题中，近机位相对远机位存在明显优势，航空器应尽量地停放在近机位。

m a x z_{1} = \sum_{k \in G_{0}} \sum_{i \in {F_{k}, s}} \sum_{j \in {F_{k}, t}} x_{i, j}^{k} - |G_{0}|

（10）

式（10）表示最大化停放在近机位上的航空器数量，其中 $|G_{0}|$ 为近机位的数量。

目标2 最小化鲁棒性损失

以最大化近机位使用率为目标，会生成大量的最优方案，这些方案中机位的空闲时间大致相同，但是空闲时间的分布可能有较大差异。合理的空闲时间有利于提高指派计划的鲁棒性，减少同一机位上的航空器冲突。

定义指派到同一停机位 $k$ 上连续停放的两个航空器 $i$ 和 $j$ 之间的期望冲突时间为 $c_{i, j}^{k}$ 。航班延误时间和预期冲突时间的关系如图3所示，其中 $a_{i}^{'}$ 和 $d_{i}^{'}$ 为航空器 $i$ 的实际进离场时间， $a_{j}^{'}$ 和 $d_{j}^{'}$ 为航空器 $j$ 的实际进离场时间。根据特定机场航班延误的历史数据拟合航班延误分布，从而计算航空器在停机位上的预期冲突时间。拟合计划时间间隔 $Δ_{i j}$ 与航班预期冲突时间 $c_{i, j}^{k}$ 的函数

c_{i, j}^{k} = f (Δ_{i j})

（11）

图3 航班延误时间与预期冲突时间关系

Fig.3 Relationship between flight delay time and expected conflict time

定义停机位指派计划的鲁棒性损失为冲突时间 $c_{i, j}^{k}$ 之和，优化目标为

m i n z_{2} = \sum_{k \in G} \sum_{i \in {F_{k}, s}} \sum_{j \in {F_{k}, t}} c_{i, j}^{k} x_{i, j}^{k}

（12）

鲁棒性较高通常表现为同一机位上航空器的时间间隔较大且均匀，但在资源有限的情况下，这将影响近机位利用率；近机位利用率高通常导致近机位上的航空器拥挤，这使指派计划吸收扰动的能力降低。结合两个优化目标的关系，本文使用 $ε$ 约束法来处理多目标。将目标2作为参考目标，并将目标1限制为不小于 $ε$ 的约束。通过求解目标1在上述约束下的最优值 $z_{1}^{*}$ ，确定 $ε$ 取值为 $ε = δ z_{1}^{*}$ ，其中 $δ$ 为 $[0,1]$ 内的松弛系数。

松弛约束如下

\sum_{k \in G_{0}} \sum_{i \in {F_{k}, s}} \sum_{j \in {F_{k}, t}} x_{i, j}^{k} - |G_{0}| \geq |δ z_{1}^{*}|

（13）

在机场网络图 $G$ 上，构建面向港湾机坪的停机位指派模型，其中目标为式（12），约束为式（1~9）及松弛约束式（13）。

3 算法设计

本文基于分支定价算法（Branch and price， B&P）的框架，将上述的停机位指派模型重构为基于集合划分的模型，并实现优化求解。分支定价是分支定界（Branch and bound， B&B）和列生成算法（Column generation）的组合算法。

在本文面向港湾的停机位指派问题中，“列”指单个停机位上的可行航空器序列，“列”的生成指用子模型生成单个停机位上可行的航空器停放方案。算法基本流程为：首先将基于弧的停机位指派模型转化为集合划分模型，包括一个列变量建模的主模型和一个主模型提供有效列的子模型；其次在内部调用列生成求解线性松弛的集合划分模型，在外部调用分支定界算法添加整数约束寻找整数最优。

定义满足上述约束式（1~9）的航空器序列方案集合为 $P$ ，其中停机位 $k$ 上的方案为 $r \in P_{k}, \forall k \in S$ 。定义决策变量 $θ_{r}^{k}$ 为

θ_{r}^{k} = \{\begin{matrix} 1 & 选择 方案 r \in P_{k} \\ 0 & 其他 \end{matrix}

（14）

定义方案 $r \in P_{k}$ 的决策变量 $b_{i j r}^{k}$ 为

b_{i j r}^{k} = \{\begin{matrix} 1 & 航空 器 i 、 j 连续 停放 在方 案 r \in P_{k} \\ 0 & 其他 \end{matrix}

（15）

由变量定义可知，弧变量 $x_{i, j}^{k}$ 与变量 $θ_{r}^{k}$ 、 $b_{i j r}^{k}$ 的关系如下

x_{i, j}^{k} = \sum_{r \in P_{k}} θ_{r}^{k} b_{i j r}^{k}

（16）

根据式（16），将上述基于弧的模型转化为基于集合划分的模型。

3.1　主模型

m i n z_{2} = \sum_{k \in G} \sum_{r \in P_{k}^{'}} c_{r}^{k} θ_{r}^{k}

（17）

\sum_{k \in G} \sum_{r \in P_{k}^{'}} a_{i, r}^{k} θ_{r}^{k} = 1 \forall i \in F

（18）

\sum_{r \in P_{k}^{'}} θ_{r}^{k} \leq 1 \forall k \in G

（19）

\sum_{r \in P_{k}^{'}} a_{i, r}^{k} θ_{r}^{k} + \sum_{r \in P_{l}^{'}} a_{j, r}^{l} θ_{r}^{l} \leq 1 \forall (i, k, j, l) \in Q

（20）

\sum_{i \in F} \sum_{k \in G_{0}} \sum_{r \in P_{k}^{'}} a_{i, r}^{k} θ_{r}^{k} \geq ⌊δ z_{1}^{*}⌋

（21）

θ_{r}^{k}, θ_{r}^{l} \geq 0 \forall r \in P^{'}

（22）

式（17）表示最小化鲁棒性损失，其中 $c_{r}^{k}$ 为停机位 $k$ 方案 $r$ 的预计冲突时间之和；式（18）表示航空器指派的唯一性约束，停机位 $k$ 方案 $r$ 包含航空器 $i$ ，则 $a_{i r}^{k}$ 取1，否则取0；式（19）表示每个停机位不能选择超过一个方案；式（20）为港湾安全性约束；式（21）代表松弛的最大化机位利用率的约束；式（22）将集合划分模型的布尔列变量松弛为连续变量。注意，该模型使用航空器序列方案集合 $P$ 的方案子集 $P^{'}$ ，子集的规模远远小于潜在的方案总集 $P$ 。因此，本文使用求解器直接求解限制规模的主模型。

3.2　子模型

基于DW分解的思想，将子模型按停机位 $k$ 分块，为每个停机位分别构建子模型 $S P_{k}$ 。

求解主模型，得到约束式（18~21）对应的对偶变量为 $π_{i} (\forall i \in F)$ 、 $π_{k} (\forall k \in S)$ 、 $π_{q} (\forall q \in Q)$ 和 $γ$ 。停机位 $k$ 为近机位，则 $T_{k}$ 为1，否则为0。子模型 $S P_{k}$ 的优化目标为

m i n \bar{c_{r}^{k}} = \sum_{(i, j) \in A^{k}} (c_{i, j}^{k} + π_{i} + T_{k} λ_{0}) b_{i j r}^{k} + \sum_{(i, k) \in Q (i, k), (i, j) \in A^{k}} π_{q} b_{i j r}^{k} + π_{k}

（23）

约束条件为

\sum_{l \in {F_{k}, s}} b_{l i r}^{k} - \sum_{j \in {F_{k}, t}} b_{i j r}^{k} = 0 \forall i \in F_{k}

（24）

\sum_{i \in F_{k}} b_{s i r}^{k} \leq 1

（25）

\sum_{i \in F_{k}} b_{i t r}^{k} \leq 1

（26）

\sum_{i \in {F_{k}, s}} \sum_{j \in {F_{k}, t}} b_{i j r}^{k} \leq N + 1

（27）

\begin{matrix} b_{i j r}^{k} (T - Δ_{i, j} - Δ_{j, p}) + M b_{j p r}^{k} \leq M \\ \forall k \in G; \forall i, j, p \in {F_{k}, s, t} \end{matrix}

（28）

b_{i j r}^{k}, b_{j i r}^{k}, b_{j p r}^{k} \in \{0,1\}

（29）

式（24~26）为式（2~4）的流量平衡约束；式（27）为式（7）的负载均衡约束；式（28）为式（8）的弹性缓冲时间约束；式（29）为子模型的布尔决策变量。

子模型的求解是列生成算法的核心问题，列生成的每次迭代过程都需要调用子模型算法寻找当前满足进基条件的列加入主模型。本文的子模型是一个典型的资源受限的最短路问题，即在一个节点为 ${F_{k}, s, t}$ 的子图上，找到一条从虚拟起点 $s$ 出发到虚拟终点 $t$ 、目标值最小的路径。路径目标值小于0的是最小化鲁棒性损失的有效列。标签算法是一类求解最短路径问题的经典算法，本文采用标签算法求解引入对偶变量的子模型，为主模型提供列方案。

3.3　加速策略设计

为提高分支定价算法的效率，本文使用和设计多种加速策略。

（1）基于弧的分支变量

在大规模问题中，基于列变量 $θ_{r}^{k}$ 分支可能导致求解困难，因为分支变量规模庞大，且易导致二叉树不平衡。本文使用分支定价求解车辆路径问题（Vehicle routing problem，VRP）时常用的分支策略，将集合划分模型中的决策变量 $θ_{r}^{k}$ 重新映射到弧模型中的决策变量 $x_{i, j}^{k}$ ，即式（15）。交替使用最不可行策略和最大偏移策略选择分支变量 $x_{i, j}^{k}$ ，即最接近0.5的变量和取整能带来最大目标增益的变量。

（2）子模型支配关系预估和添加多列

为提高列的数量和质量，一次性向主模型中添加所有子模型的列方案。但随着问题规模尤其是停机位数量的扩大，需要求解的子模型数量也随之增长。通过预实验发现，在列生成迭代后期，大多子模型已经无法产生最优值小于0的有效列。因此，设计子模型支配关系预估原则，来避免计算无法生成有效列的被支配的子模型，节省求解时间。子模型 $S P_{k}$ 和 $S P_{l}$ 的支配关系预估原则为：已知 $c_{i, j}^{k} = c_{i, j}^{l}$ ，若停机位 $k$ 和 $l$ 均不是港湾机位，即对偶变量 $π_{q} = 0$ ，且满足对偶变量 $π_{k} \geq π_{l}$ ， $T_{k} γ \geq T_{l} γ$ ，则子模型的最优值满足 $\bar{c_{r}^{k}} \geq \bar{c_{r}^{l}}$ ，即 $S P_{k}$ 被 $S P_{l}$ 支配。在算法中，记录最优值 $\bar{c_{r}^{l}} \geq 0$ 的无效子模型 $S P_{l}$ ，若子模型 $S P_{k}$ 被无效子模型 $S P_{l}$ 支配，即 $\bar{c_{r}^{k}} \geq \bar{c_{r}^{l}}$ ，则 $\bar{c_{r}^{k}} \geq 0$ ，那么不计算子模型 $S P_{k}$ 。

4 算例分析

4.1　算例设计

采用广州白云国际机场（IATA代码：CAN）典型高峰周（国庆）内的航班数据构建测试案例。CAN是我国3大枢纽机场之一，机场内有两个航站楼和224个机位，包括142个近机位。机场内形成大量港湾机坪，如图4所示。提取CAN的机位数据和航空器（航班）数据，部分示例见表1和2。

图4 广州白云国际机场平面布局图

Fig.4 Layout of Guangzhou Baiyun International Airport

表1 停机位信息

Table 1 Gate information

编号	指廊/站坪	国际/国内	近/远	机位等级
101	东一指廊	国际	近	E
125	东三指廊	国内	近	D
135	东三远	混用	远	C

表2 航空器信息

Table 2 Airport information

编号	机型等级	计划进场	计划离场	属性
1	E	09：20：00	12：40：00	国际
2	C	09：25：00	10：25：00	国内
3	E	10：25：00	11：35：00	国内

设置规划周期为24 h，构建30个不同规模的测试算例，包括10个小规模算例、10个中规模算例、10个大规模算例。小规模算例中停机位数不超过20，航班数少于100；大规模算例停机位数大于70，航班数量超过300；其余为中规模算例。部分算例信息见表3。表3中， $i d$ 代表算例编号， $S i z e$ 代表算例的规模， $m$ 代表可用的停机位数量， $n$ 代表待分配的航空器数量， $R a t i o = n / m$ 表示机位的日均负载量， $A v e r a g e$ 表示每架航空器的平均可用停机位数量， $| Q |$ 代表港湾冲突的数量。

表 3 算例信息

Table 3 Instance information

$i d$	Size	$m$	$n$	$R a t i o$	$A v e r a g e$	$\| Q \|$
1	小	10	30	3	9.53	264
2	小	10	40	4	8.97	384
3	小	16	69	4.31	14.16	5 148
4	小	16	64	4	14.47	4 344
5	小	16	55	3.44	13.22	2 597
6	小	16	61	3.81	12.31	2 863
7	小	20	50	2.5	16.88	0
8	小	20	60	3	16.57	0
9	小	20	56	2.8	16.46	0
10	小	20	65	3.25	16.43	0
11	中	30	100	3.33	25.63	2 687
12	中	30	120	4	26.43	5 107
13	中	33	128	3.88	25.86	11 798
14	中	40	100	2.5	22.32	1 896
15	中	40	130	3.25	22.42	4 140
16	中	42	239	5.69	35.2	14 867
17	中	47	151	3.21	25.6	9 888
18	中	50	150	3	43	43 250
19	中	50	172	3.44	42.67	57 028
20	中	50	182	3.64	43.46	67 014
21	大	75	368	4.91	44.33	41 620
22	大	75	355	4.73	45	31 520
23	大	75	367	4.89	45.37	39 846
24	大	75	357	4.76	43.99	37 468
25	大	75	360	4.8	42.79	41 706
26	大	97	323	3.33	60.16	20 048
27	大	97	316	3.26	60.71	16 265
28	大	97	328	3.38	60.86	22 390
29	大	97	329	3.39	61.1	15 700
30	大	97	326	3.36	61.38	21 329

4.2　算法效率分析

为检验分支定价方法的有效性，使用CPLEX求解器直接求解第二节提出的基于弧的停机位指派模型，与B&P算法对比计算的精度和速度。设置松弛系数 $δ$ 为0.8，单个机位的负载上限 $N$ 为8，弹性缓冲时间阈值 $T$ 为30 min，最大求解时间为60 min。此外，通过预实验发现，大规模算例在近机位航空器数量约束下难以在求解时间内产生可行解。一方面由于航空器总量大都近机位数量有限，另一方面目标1的整数系数使分支定价算法在迭代中容易退化，难以收敛。因此，在大规模算例的实验中，设置松弛系数为0，即不考虑近机位使用率的约束。

选取广州白云国际机场两年的航班数据进行航班延误分布统计，并拟合航班与其冲突时间和航班计划间隔时间的函数关系，式（11）中的 $f (\cdot)$ 为

c_{i, j}^{k} = f (Δ_{i j}) = 52.4 \cdot e^{- {(\frac{Δ_{i j} + 38.3}{52.9})}^{2}}

（30）

各规模算例的平均求解情况见表4。表4中 $m$ 为该规模算例平均停机位数量， $n$ 为平均航空器数量； $U B_{C P L E X}$ 和 $U B_{B P}$ 分别为CPLEX和B&P的平均最优整数解，即得到的最优可行方案目标值， $L B_{C P L E X}$ 和 $L B_{B P}$ 分别为CPLEX和B&P得到的分支定价平均最优松弛下界。B&P对比CPLEX在解的质量上改进为 $Δ = (U B_{C P L E X} -$ $U B_{B P})$ $/ U B_{C P L E X} \cdot 100 %$ 。 $g a p_{C P L E X}$ 为 $(U B_{C P L E X} -$ $L B_{C P L E X}) / U B_{C P L E X} \cdot 100 %$ ， $g a p_{B P}$ 为 $(U B_{B P} - L B_{B P}) / U B_{B P} \cdot 100 %$ 。CPU为最大时间内收敛的算例的平均求解时间（s）。在大规模算例上，两种算法均无法在60 min内收敛，表4中不展示该时间。

表 4 两种算法的运行结果

Table 4 Results of two algorithms

算例信息			CPLEX				B&P				$Δ$
规模	$m$	$n$	$U B_{C P L E X}$	$L B_{C P L E X}$	$g a p_{C P L E X}$	CPU/s	$U B_{B P}$	$L B_{B P}$	$g a p_{B P}$	CPU/s	$Δ$
小	16.4	55	538.23	534.29	0.75	5.74	536.71	534.292	0.51	4.802	0.3
中	41.2	147.2	1 726.46	1 425.61	10.76	186.53	1 428.56	1 424.69	2.25	145.47	17.3
大	86	342.9	5 031.65	3 547.84	22.85		3 687.40	3 547.25	3.65		26.7

由表4可知，在求解时间上，B&P算法在小、中规模算例中的平均求解时间分别为4.80 s和145.47 s，少于CPLEX收敛所需的时间。在最优解的质量上，B&P有明显的优势，极大地逼近了理论最优解。在小规模案例中，两种算法的 $g a p$ 相近，最优解差距在0.3%以内；随着算例规模扩大，B&P算法在中、大规模算例中 $g a p$ 仅为2.25%和3.654%，远小于CPLEX的10.76%、22.85%。在中、大规模算例中，B&P算法求得的最小鲁棒性损失比CPLEX最优值分别少26.7%、17.3%，可见在B&P算法中，目标得到了明显的改善。

两种算法的最优解对比结果见图5。由图5可知，在小规模算例中两种算法的最优解基本一致；随着规模的扩大，CPLEX求解器难以解出更优的解，在多数算例中与B&P算法有着明显的差距。这是由于CPLEX内置采用通用求解整数规划的分支定界算法，难以有效地处理规模较大的弧边变量，也难以平衡地添加切割分支。本文重构基于路径的集合划分模型和设计的B&P算法能更有效地处理较大规模的停机位指派问题。可见，B&P算法能有效地求解面向港湾机坪的停机位指派模型，在较少的时间内得到高质量的解。

图5 各算例的最优值对比

Fig.5 Comparison of the optimal values of each instance

4.3　港湾约束分析

本文设计对照实验验证港湾安全约束的效果。在所有含港湾安全约束的算例中，用B&P算法求解去掉港湾安全约束的模型作为对照组。

对照组中各算例违反港湾安全约束的航空器占比如图6所示。由图6可知，冲突的航空器比例普遍在10%以上，甚至高达40%。随着算例规模的扩大，冲突比例整体上减少，这是由于停机位数量的增多为航空器提供了更大的更换空间，利于避免港湾冲突。

图6 对照组中违反港湾安全约束的航空器占比

Fig.6 Proportion of aircraft violating harbor safety constraints in the control group

对照组的计算结果见表5。表5中 $m$ 为该规模案例中含港湾安全约束的算例的平均停机位数量， $n$ 为平均航空器数量， $Q$ 为平均港湾约束数量；B&P列中的 $z_{1}^{*}$ 为B&P算法计算的目标1平均最优值， $z_{2}^{*}$ 为目标2平均最优值；B&P without harbor列中 $z_{1}^{'}$ 为去掉港湾安全约束后B&P算法计算的目标1平均最优值， $z_{2}^{'}$ 为目标2平均最优值； $Δ_{1}$ 为 $(z_{2}^{'} - z_{2}^{*}) / z_{2}^{'} \cdot 100 %$ ，代表考虑港湾安全约束后，对最优目标值的影响程度； $c o n f_Q$ 为对照组最优解违反的港湾安全约束数量， $c o n f_F$ 为其中冲突的航空器数量， $r a t i o_F$ 为冲突的航空器占航空器总数的比例，为 $(c o n f_F / a v g_n) \cdot 100 %$ 。

表5 对照组的运行结果

Table 5 Results of the control group

算例信息				B&P		B&P without harbor		$Δ_{1}$	$c o n f_Q$	$c o n f_F$	$r a t i o_F$ /%
规模	$m$	$n$	$Q$	$z_{1}^{*}$	$z_{2}^{*}$	$z_{1}^{'}$	$z_{2}^{'}$	$Δ_{1}$	$c o n f_Q$	$c o n f_F$	$r a t i o_F$ /%
小	14	53.17	2 600	51.33	447.63	51.33	443.55	0.017	11.5	15.17	27.17
中	41.2	147.2	21 767.5	124.8	1 428.56	124.8	1 424.64	0.002	17.9	24.3	16.35
大	86	342.9	28 789.2		3 687.40		3 545.45	0.051	29.5	37.6	11.01

由表5可知，对照组在小、中、大规模算例中分别有27.17%、16.35%、11.01% 的冲突航空器，说明本文的面向港湾机坪的停机位指派模型有效地预先避免了较大比例的冲突。理论上约束减少会增大解空间，从而可能产生更佳的最优值。但可以观察到，两组实验中近机位最大利用率（目标1）几乎没有差别，而鲁棒性损失目标（目标2）对应的 $Δ_{1}$ 仅分别为0.017%、0.002%、0.051%，说明停机位指派方案鲁棒性损失几乎没有因考虑港湾安全约束而增大，通过合理的调整航空器间隔时间的分布保持了鲁棒性。

可见，本文的模型能在几乎不影响最优值的情况下，避免潜在较多的港湾冲突，在优化机位利用时提高了机坪安全性。

4.4　算法参数分析

本文使用 $ε$ 约束法来处理最大化近机位利用率和最小化鲁棒性损失两个目标，使用松弛系数 $δ$ 连接两个目标， $δ$ 的取值直接决定了对近机位利用率的要求。选择部分算例分析 $δ$ 取值对目标的影响。

以算例8和11为例，调整 $δ$ 得到近机位航空器数量 $δ z_{1}^{*}$ 和最小化鲁棒性损失 $z_{2}^{*}$ 的关系曲线，如图7所示。由图7可知，鲁棒性损失和近机位利用目标的松弛系数 $δ$ 在整体上互斥。当松弛系数 $δ$ 达到一定阈值后，曲线呈较明显的上升趋势，说明近机位上航空器的进一步密集可能降低了停机位指派计划鲁棒性。理论上这是因为近机位航空器数量约束的增强使得解空间缩小，导致鲁棒性损失更大。实际上从图7可见，不同松弛系数下鲁棒性损失的上下限差距往往在5 min以内，占鲁棒性目标的比例很小。由此在实际应用中，机场管理者可以在模型有可行解的条件下提高松弛系数 $δ$ ，以少量的鲁棒性损失换取更高的近机位利用。

图7 不同松弛系数的最优值曲线

Fig.7 Curves of optimal values of different relaxation coefficients

5 结论

（1）本文提出面向港湾机坪的停机位指派问题。考虑停机位的利用效率和安全性，引入港湾安全约束，以充分利用近机位和减低鲁棒性损失为目标构建停机位指派模型。设计含多种加速策略的分支定价算法，精确求解该模型。在广州白云国际机场的运行数据上验证模型和算法的有效性。

（2）文中所提方法可以在优化停机位利用率的同时，可以通过调节机位上的航空器间隔来提高指派计划的鲁棒性，通过调整部分潜在冲突的航班，避免航空器冲突。同时针对港湾约束的建模思路和算法设计可以很好地扩展到其他考虑机位之间耦合性的约束，从而进一步提高机位指派计划的质量。

（3）未来的研究要进一步考虑不确定因素对停机位指派计划鲁棒性的影响。本文设计确定性模型对停机位进行预指派，实际运行中航空器进离场时间、滑行时间的不确定性等多种因素对停机位指派都有重要影响。此外，本文通过停机位指派的方式来减少港湾机坪的潜在冲突，未来要考虑结合更多的管制手段来减少航空器在机位滑行道上的冲突，从而提高停机位的利用效率和机坪安全性。

参考文献

YU C， ZHANG D， LAU H Y K. MIP-based heuristics for solving robust gate assignment problems［J］. Computers & Industrial Engineering， 2016， 93： 171-191. [百度学术]

LIU S， CHEN W H， LIU J. Robust assignment of airport gates with operational safety constraints［J］. International Journal of Automation and Computing， 2016， 13（1）： 31-41. [百度学术]

MAHARJAN B， MATIS T I. Multi-commodity flow network model of the flight gate assignment problem［J］. Computers & Industrial Engineering， 2012， 63（4）： 1135-1144. [百度学术]

姜雨，胡志韬，童楚，等.面向航班延误的停机位实时指派优化模型［J］.交通运输系统工程与信息， 2020， 20（5）： 185-190， 217. [百度学术]

JIANG Yu， HU Zhitao， TONG Chu， et al. An optimization model for gate re-assignment under flight delays［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（5）： 185-190， 217. [百度学术]

王超，任云鸿.面向节油减排的平行多跑道混合运行机场停机位分配模型［J］.交通信息与安全， 2021， 39（5）： 144-152. [百度学术]

WANG Chao， REN Hongyun. A model of gate allocation for parallel multi-runway hybrid operation from the perspective of fuel-saving and carbon emission reduction［J］. Journal of Transport Information and Safety， 2021， 39（5）： 144-152. [百度学术]

LI Y， CLARKE J P， DEY S S. Using submodularity within column generation to solve the flight-to-gate assignment problem［J］. Transportation Research Part C： Emerging Technologies， 2021， 129： 103217-103240. [百度学术]

WANG R， ALLIGNOL C， BARNIER N， et al. A new multi-commodity flow model to optimize the robustness of the gate allocation problem［J］. Transportation Research Part C， 2022， 136： 103491-103511. [百度学术]

余青华. 基于机坪管制移交的航站楼U型区运行优化研究［D］. 天津：中国民航大学，2020． [百度学术]

YU Qinghua. Research on operation optimization of U-shaped area of terminal building vasedon aircraft control transfer［D］. Tianjing： Civil Aviation University of China， 2020. [百度学术]

DENG W， ZHAO H， YANG X， et al. Study on an improved adaptive PSO algorithm for solving multi-objective gate assignment［J］. Applied Soft Compute， 2017， 59： 288-302. [百度学术]

李倩雯. 机场停机位优化分配模型构建［D］. 北京：北京交通大学， 2018. [百度学术]

LI Qianwen. Research on optimization models for airport gate assignment problem［D］. Nanjing： Nanjing University of Aeronautics and Astronautics， 2018. [百度学术]

DIEPEN G， AKKER J M， HOOGEVEEN H， et al. Finding a robust assignment of flights to gates at Amsterdam Airport Schiphol［J］. Journal of Scheduling， 2012， 15： 703-715. [百度学术]

BENLIC U， BURKE E K， WOODWARD J R. Breakout local search for the multi-objective gate allocation problem［J］. Computers and Operations Research， 2017， 78： 80-93. [百度学术]

CASTAING J， MUKHERJEE I， COHN A M， et al. Reducing airport gate blockage in passenger aviation： Models and analysis［J］. Computers and Operations Research， 2016， 65： 189-199. [百度学术]

GUÉPET J， ACUNA-AGOST R， BRIANT O， et al. Exact and heuristic approaches to the airport stand allocation problem［J］. European Journal of Operational Research， 2015， 246（2）： 597-608. [百度学术]

KARSU Ö， AZIZOĞLU M， ALANLI K. Exact and heuristic solution approaches for the airport gate assignment problem［J］. Omega， 2021， 103： 102422-102437. [百度学术]

李云鹏，张则强，管超，等.停机位分配问题的整数规划模型及启发式求解方法［J］.系统工程， 2020， 38（1）： 103-112. [百度学术]

LI Yunpeng， ZHANG Zeqiang， GUAN Chao， et al. Integer programming model and heuristic method for gate assignment problem［J］. Systems Engineering， 2020， 38（1）： 103-112. [百度学术]

请使用 Firefox、Chrome、IE10、IE11、360极速模式、搜狗极速模式、QQ极速模式等浏览器，其他浏览器不建议使用!

面向港湾机坪的停机位指派优化 PDF

摘要

关键词

1 面向港湾机坪的停机位指派问题

2 模型构建

2.1 模型假设

2.2 模型构建

3 算法设计

3.1 主模型

3.2 子模型

3.3 加速策略设计