基于时间离散化的飞机降落问题研究

2018-05-07陈晨

现代计算机 2018年9期

陈晨

（四川大学计算机学院，成都 610065)

0 引言

近年来，中国经济高速发展，航空事业迅速发展，机场数量和规模，航班排版数量持续增长。在航空事业高速发展的今天，如何让航空公司的飞机调度更加合理高效地运行，为人们提供更快捷便利的服务，改善空中交通状况是众多专家学者关注的焦点。飞机降落问题也在此环境下应运而生，该问题是指对每一架进入机场的飞机分配一条跑道和一个安全的降落时间。每架飞机需要在事先预定好的时间降落在跑道上，同时，任何两架飞机之间必须有一定的距离间隔来保障安全。

1 模型建立

对于每一架进入目标机场雷达测距范围的飞机，都会收到来自空中交通管制的命令，为其分配一条降落跑道和一个降落时间。降落时间需要在最早降落时间和最晚降落时间之间。最早降落时间对应的是飞机以最快飞行速度飞行时的着陆时间。最晚降落时间对应的是飞机由于某些因素降低飞行速度造成延迟的最晚着陆时间。目标降落时间是我们希望飞机降落的时间。在目标降落时间之前或之后降落都会给机场带来一定的困扰，因此和目标降落时间的偏离会给机场带来一笔额外的开销。

对于飞机降落问题，我们给出以下理想模型：

P：飞机；

R：跑道；

Ei：飞机i的最早降落时间，i∈P；

Ti：飞机i的目标（最佳）降落时间，i∈P；

Li：飞机i的最晚降落时间，i∈P；

Sij≥0：当飞机i比飞机 j提前降落在相同跑道时，飞机i和飞机 j的最小间隔时间；

sij≥0：当飞机i比飞机 j提前降落在不同跑道时，飞机i和飞机 j的最小间隔时间。

决策变量如下：

δ2ij∀i,j∈P(i≠j)，二元变量，=1当且仅当飞机i比飞机 j提前降落在不同跑道；

zij∀i,j∈P(i＜j)，二元变量，zij=1当且仅当飞机 i和飞机 j降落在相同跑道；

yir∀i∈P，r∈R ，二元变量，yir=1当且仅当飞机i降落在跑道r上；

xi≥0，飞机i的计划降落时间。

模型PB具体需遵从以下约束：

2 理想情况模拟

利用时间分离化方法分解矩阵S。Sij代表先降落的飞机i和后降落的飞机 j降落所需的最小间隔时间。假设S可以分解成具有相同列向量a（非负项）和相同行向量b（非负项）的矩阵之和，即Sij=ai+bj,ai≥0,bj≥0。将每架飞机看作是分享同一个资源（跑道）的活动i，当飞机i提前于飞机 j降落在同一条跑道上时，两架飞机的安全时间间隔如下图所示。

图1 飞机i和飞机 j的安全时间间隔

使用这种分解方法，我们可以在有限数量的飞机降落场景中模拟飞机降落问题。每种飞行场景在时间窗对应一个着陆时间，一架飞机降落的场景数等于时间窗口中的时间槽。因此，飞机降落问题可以由下式表达：

其中，（10）表示同一时间每架飞机有且仅有一种降落场景，（11）表示在时间规划范围内，同一个时间最多允许一架飞机降落。H代表时间槽的集合，Scen(i)表示飞机i的场景集合。

3 求解目标

用cik表示飞机i在场景k情况下的降落开销，Ti表示i的预计（理想）降落时间，tik表示飞机i在场景k的实际降落时间，gi,hi分别表示tik比Ti提前和延迟到达的开销函数。

4 解决方案

对于任何分离时间矩阵S，总是可以通过rank2矩阵进行近似估算。有很多方法来逼近矩阵S。分离时间矩阵S与飞机机型（分别为重型heavy，中型medi⁃um，轻型light），用C表示飞机机型。线性变化如下式：

我们使用模型PB中的限制条件并把结果添加到PSC中。用tik表示飞机i在场景k情况下的降落时间，xi可以表示为 xi=sumk∈Scen(i)tikλik。飞机降落在哪条跑道上取决于场景和环境，定义runwikr=1表示飞机i在场景k的情况下降落在跑道r上，否则runwikr=0，那么yir可以表示成 yir=sumk∈Scen(i)runwikrλik。

只考虑重要的限制条件，算法如下：

1. 使用下边界矩阵初始化，(PB)=PSC(SLB,sLB)；

2.解(PB)，将结果记为λ；

3. 计算 xi=sumk∈Scen(i)tikλik,∀i∈P ；

4. 在相同跑道上找出满足条件 xi≤xj且xi+Sij＞xj的飞机i和飞机 j；

5. 在不同跑道上找出满足条件 xi≤xj且xi+sij＞xj的飞机i和飞机 j；

6. 如果发现违反不等式的条件，用 λik,δ1ij,δ2ij,zij表达的式子代入PB并重复步骤2，否则结束。

该算法得到的结果满足所有限制约束。