目视回收流程优化问题研究*

于静远 郑 锦

（91404部队91分队 秦皇岛 066000）

1 引言

1.1 问题研究背景

目视回收优化问题来源于飞机回收流程，在跑道资源紧缺，飞机油量有限的前提下，如何更好更快更安全地回收飞机，即在安全回收的前提下，提供一种既快速又稳定的调度方案，就是这一优化问题的主要内容。

机场的飞机起飞降落调度是典型的单机调度问题。在理论上，它可以看作是其他调度问题的特殊形式。相比一般单机调度问题，目视回收优化问题具备多目标、动态性等特点，这些问题都需要特别考虑分析。

1.2 问题研究难点

目视回收优化问题的难点有两个。

一是该问题的优化目标多。优化目标多意味着问题的目标函数会很复杂，若优化目标之间相互制约，则在设计优化函数时还需要另外设计启发式算法来决定目标函数。

二是该问题的动态优化特性。具有实时性，因此在设计算法时只能考虑动态优化算法。同时与时间相关的突发事件的不确定性，这可能需要额外引入概率分析的手段分析问题。

2 问题描述

目视回收航线问题是回收飞机的第I类回收模型。在此模型中，在等待区域有若干飞机排成一个队列等候降落。飞机必须按排成的队列顺序依次进行降落。每架飞机着陆时的总重量（即机重加油量）必须满足给定的安全着陆重量的范围，否则必须进行备降。在飞机着陆时有可能发生逃逸事情（钩锁失败）或复飞事件（跑道故障），复飞的飞机需要进入复飞航线进行重新着陆。在飞机着陆过程中，必须保证任意两架连续着陆的飞机的着陆时间满足最小的时间间隔。

可将该问题大体上分为五个状态（航线），分别为等待状态，进近状态，复飞状态，着陆状态和备降状态。如图1为目视回收航线调度的俯视示意图。图2为目视回收的复飞航线图。

图1 目视回收航线俯视图

图2 目视回收的复飞航线图

2.1 子问题划分

该问题可以分解为两个子问题来求解。

第一个子问题是，在不发生任何逃逸事件或跑道故障事件的情况下，各飞机的最优离开等待状态的时间如何确定的问题。

第二个子问题是，在某一时刻t（正整数），正在着陆的飞机发生逃逸事件或跑道故障事件，该飞机应插入到处于等待状态的飞机的哪个位置的问题。

2.2 静态子问题描述

下面给出静态子问题的决策变量，约束条件以及目标函数。

1）决策变量

第i队飞机过检查点退出等待进入进近航线的时刻xi；

2）约束条件

（1）第1队飞机从检查点退出等待进入进近航线的时刻x1=0；

（2）xi≥xi-1+mΔti=2，…，l

m为每队飞机的数量，Δt为任意两架飞机的着陆时间间隔。

3）目标函数

其中，f1为安全着陆的飞机数目（最大化），f2为回收所有飞机的总时间（最小化），f3为飞机总的放油量（最小化）；Wi，j为飞机的机身重量（kg）；为飞机的初始油量（kg）；为从检查点到跑道着陆的时间间隔。

不难发现，三个目标函数中，f1为第一优化目标，f2次之，f3最弱。因此，总的目标函数可写成

f=α1f1-α2f2-f3

这里α1≫α2≫0。

2.3 动态子问题描述

在基于静态子问题模型的基础上，我们考虑动态子问题，即在某一时刻t，正在着陆的飞机j发生逃逸事件或者跑道故障的情况下，如何对现有方案进行重新调度，以实现最优化2.2节所提及的三个目标函数的目的。

下面给出动态子问题的决策变量，约束条件以及目标函数。

1）决策变量

（1）在当前时刻仍处于等待状态的各队飞机退出等待进入进近航线的时间xi；

（2）第k次发生复飞的第i队第j架飞机的复飞时间长度yi，j，k；

（3）第k次发生复飞的第i队第j架飞机的复飞时刻zi，j，k。

2）约束条件

（3）若第i队飞机j未曾复飞，则

即任一飞机与复飞的飞机降落到跑道的时间间隔不小于Δt；若第i队飞机j已复飞，则

（5）Pt+Pf=1，Pt，Pf∈{0，1}。任一时刻最多只发生一次逃逸或复飞。

3）目标函数

与2.2节目标函数一致，但其中f2变为

3 算法求解与分析

3.1 静态子问题求解

根据2.3节的目标函数可知，退出等待时刻xi越小，则f1越大，f2越小，f3越大，因此xi应尽量的小，该问题的最优解为

直观上来看，各架飞机只要在满足安全时间间隔的前提下尽可能早地离开等待航线，进近，着陆即可。

3.2 动态子问题求解

在动态子问题中，最核心的约束有两个，分别为约束b）和约束c）。

这两个约束实际上是由复飞后的飞机插入到未着陆的飞机编队序列中的位置决定的，即需要复飞的飞机应处于未着陆的若干架飞机的什么位置。

如图3所示，一旦复飞的飞机插入的位置确定，则yj，k的值以及等待区域的飞机新的值就可以根据前面提到的约束来确定。因此，新的飞机调度方案可确定为

图3 复飞飞机yi*，j*插入位置的选择

复飞的飞机插入的位置为p之后，则对飞机（编队）p以及p之前的飞机，调度方案不变，受到影响的只有p之后的飞机。对于新的调度方案，有两种情况要分别讨论。

第一种情况，在p位置上的是一个飞机编队，处在进近航线中，为状态S2或S3，如图4所示。此时计算的值。由于目标函数的要求，xp越小越好，因此可得关系式：

图4 复飞插入后新调度方案示意图

则飞机h（h＞p）的新调度时间，若飞机的状态为S1或S5，则

若飞机状态为S2或S3，则x不变，完善边界条件，得：

即后续所有飞机均延迟Δt的时间即可。

第二种情况，p位置上是一架正在复飞的飞机，为状态S4，如图5所示。

图5 复飞插入后新调度方案示意图

飞机h（h＞p）的新调度时间，与第一种情况相同。

4 结语

目视回收航线问题表面上看起来比较简单，但经过仔细研究可以发现问题本质上是非常有深度的。首先是问题的描述方面，将这一实际应用问题抽象出来，采用时空状态图的方式去理解。再者，在问题的决策求解方面，由于复飞和甲板故障事件的突发性、实时性和不确定性，导致了在决策时除了考虑当前格局的优度，还要考虑当前局面的稳定和可靠程度。