贪心策略求解单元地面等待模型

王煜清

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

贪心策略求解单元地面等待模型

王煜清

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

1　问题的提出

近年来，航空业发展迅猛，飞行流量的急剧增加也引起了机场空域和地面的拥挤。在繁忙的大机场，飞行高峰时段造成的交通流量饱和，影响了航班的正常运行。这不仅造成了旅客时间上的损失，也对航空公司造成了大量的人力和财力浪费。目前，空中交通流量管理的解决方法有长期、中期和短期3种策略。地面等待策略（Ground Holding Policy，GHP）是短期策略中处理交通流量问题的一种重要方法。本文研究单机场地面等待策略如何求解最优解的问题。

首先，对需要解决的问题建立一个数学模型。在建立单机场的地面等待模型时，现做出如下假设：

（1）在时间区间［0，T］内，在目的机场G，着陆的航班出现拥挤，并且机场G是空中交通网络唯一的容量受限单元。

（3）在时间区间［0，T］内，机场容量c（T）已知。根据c（T）变化，把时间区间［0，T］划分为n个着陆时间段，每个着陆时间段内有且仅有一架航班着陆。航班Fi的地面等待成本系数已 知。

（4）不考虑航班提前降落，等待时间不超过设定的最大等待时间。

对于单机场地面等待问题而言，在满足目的机场G容量限制的条件下，求出每个航班的最优地面等待时间，使得总的等待损失最小。因此，可以得到目标函数为：

式中：ti1为航班预计着陆时间；ti2为航班实际着陆时间；gi为航班Fi地面等待时间。

约束条件：

表1

式（3）表示航班不能提前着陆，最大等待时间不超过设定的∂个着陆时间段。式（8）表示着陆航班数要满足该时间段内的容量要求。

2　算法原理

结合实际情况，选取有代表性的10架航班进行算法描述，相关算例数据见表1和表2。

假设各个航班的地面延误损失系数如表1。

每个航班的基本信息如表2。

表2

假设就是在14:00～14:20这20分钟内有上述10个航班发生了冲突，根据当时的机场容量，按每两分钟一个时隙，共分成10个时隙，并设定每架航班的最大延迟为5个时隙（∂=5）。

算法的基本思想是在所有航班不超过最大延迟的情况下，尽量让地面延迟损失系数大的航班延误的时隙尽量少，采用的思想是贪心策略的思想，选取当前的最优解作为全局最优解。

对于上述的10个航班，F1，F2，F3，都在第一个时隙发生冲突，根据贪心策略，选取其中地面延误损失系数最大的航班F3进行降落，并为每个航班记录下当前的时延，用变量ɑ表示。F3在时隙1降落，其时延为0，然后把剩下的F1，F2加入到时隙2的队列中。

对于时隙2的等待队列，此时共有4个航班（原有的F4，F5，和从时隙1淘汰下来的F1，F2）。然后再按照如同时隙1同样的处理方式处理时隙2。

其余的时隙也是以此类推，但是有一个问题必须考虑，航班的饿死现象。航班的最大等待延迟是确定的，在对每个航班进行延迟的时候，不能超过最大等待时延。算法对这种情况的处理方法是，当一个航班的当前等待时延ɑ=∂时，不在对其进行延迟，而是直接将它分配到当前的时隙中。

3　算法正确性的证明

通过基于贪心策略的航班分配算法，可以求得此航班模型的最优解。下面给出算法正确性和有效性的证明。

（1）我们发现，在上面建立的数学模型中，所有航班的延迟时隙数量之和β是一定的。因为对于相互冲突的n个航班，选择其中任何一个航班的降落，其余n-1个航班的ɑ都要加1。β每次加一，对应的就是目标函数值加上相应的航班地面延迟损失系数。所以贪心算法选取地面损失系数最大的降落，其余的航班ɑ加1，在不超出最大等待时延的情况下是可以得到最优解的。

（2）如果考虑航班达到最大的等待延迟，即航班的ɑ=β，不能在将此航班延迟，此航班立即降落，这样仍可保证得到的是最优解。反证法：假设这种情况不是最优解，也就是说此航班不分配此时隙时有最优解产生。那么，此航班必须分配到前面的某个时隙中，而这样会造成前面已分配的航班向后延迟，由于我们按照（1）的方式，是按照地面损失系数由大到小分配下来的，并且总的时隙数之和β一定，所以这样分配得到的目标函数值肯定更大。所以，原解为最优解。

4　算法计算结果分析

针对上述的问题实例，用该算法进行计算。最终得到了一个最优解，即航班序列（F3，F5，F6，F8，F2，F1，F4，F7，F10，F9），上面航班对应的延迟时隙数为（0，0，0，0，4，5，5，5，4，5），后面的航班看似延迟很大，其实是由于∂条件限制导致的，因为前面拖延下来的航班达到了值，必须要求降落。结合表1进行计算，最后得出的目标函数值（总的等待费用）为11137元。而如果我们按照FCFS进行航班的编排，最后目标函数值为17996元，说明该算法是有效的。该算法的优点是，在满足限制条件的情况下，它求得的解是最优的。基于人工鱼群、遗传算法、模拟退火等算法求得的是近似值，而非最优解。

5　结语

本文给出了基于贪心算法思想的单机场地面等待策略最优解求解问题，该算法可用于解决实际工作中的一些相关问题，具有一定的实际意义。该算法之所以能求得最优解，因为其只限于这种特定的数学模型，算法的通用性不强，如果是多机场、机场容量动态变化时，本算法并不适用。通用性方面，目前基于搜索的算法优于本算法，但它们的缺点是只能得到近似值，而且计算繁琐。

［1］王飞，徐肖豪，张静．基于人工鱼群算法的单机场地面等待优化策略［C］，2009.2.

［2］Thomas H.Cormen，Charles E.Leiserson等.算法导论［M］．殷建平，徐云等译．北京：机械工业出版社，2013.1.

［3］徐肖豪，李雄．航班地面等待模型中的延误成本分析与仿真［C］，2006.2.

［4］胡明华，徐肖豪．空中交通流量控制的地面保持策略［C］，1994.11.

Air Traffic Flow Management；Ground Waiting Strategy；Single Airport

Greedy Strategy for Solving Unit Ground Waiting Model

WANG Yu-qing
（College of Computer Science，Sichuan University，Chengdu 610065）

1007-1423（2015）29-0018-03

10.3969/j.issn.1007-1423.2015.29.005

王煜清（1991-），男，山东临沂人，研究生，研究方向为图形图像处理

2015-09-22

2015-10-12

目前大型机场拥塞问题日益严重。当拥塞发生时，航班的等待是难免的，如何减少因航班等待引起的开销，是值得研究的问题。一般来说，飞机的地面等待费用小于在空中等待的费用，所以，将空中等待转化为地面等待，可以减少等待费用，由此产生了很多地面等待的策略。在现实情况下，由于飞机的机型等因素，使得每个航班单位时间的等待费用也不尽相同，对一个时间段内需要降落的航班进行一个合理的次序编排，可以进一步地缩小由于等待造成的经济损失。研究单个降落机场在一个时间段内如何有效地解决航班拥塞问题，通过建立相应的数学模型，给出求解该模型的算法，并证明算法的正确性。

空中交通流量管理；地面等待策略；单机场

At present，the problem of large airport congestion is becoming more and more serious.When congestion occurs，the flight waiting is inevitable，how to reduce the overhead caused by flight waiting is a problem worthy of study.Generally speaking，the ground of the aircraft is less than the cost of waiting in the air，so the air will be waiting for the ground to wait，can reduce the cost of waiting，resulting in a lot of ground waiting for the strategy.In reality，due to the aircraft's model and other factors，so that the cost of waiting for each flight unit time is not the same，the need for a period of time to land a reasonable sequence of flight arrangements，can further reduce the economic losses due to waiting.Studies how to solve the problem of flight congestion in a single landing airport，and gives the algorithm of solving the model，and proves the correctness of the algorithm.