多蚁群协同进化的滑行道调度优化

冯兴杰，杜姗姗

（中国民航大学 计算机科学与技术学院，天津300300）

0 引 言

国内外许多学者对滑行道调度问题进行了研究，文献［1，2］都尝试用遗传算法解决本问题；文献 ［3］提出了一种新的调度策略，建立了对应的模型，并采用floyd算法为每个航班提供多条无障碍的理想路径；文献 ［4］应用A＊算法对航班滑行轨迹进行了预测；文献 ［5］采用了蚁群算法解决本文问题。然而这些方法都没有考虑航班间的调度优先级顺序。

本文提出了运用多蚁群协同进化的思想解决滑行道调度问题。对每个航班的滑行调度都生成一个种群，利用蚁群算法善于解决智能寻径等问题的特点，在种群内部用来搜索指定端点的滑行路径，并对滑行路径进行冲突检测与解决，保证滑行的安全性；利用合作型协同进化算法解决航班的调度优先级顺序，各种群之间协同进化，形成一个协同的滑行调度计划。实验结果表明，该算法具有显著的优势。

1 问题及模型

1.1 问 题

滑行道调度［6－8］问 题 （aircraft taxi scheduling problem，ATP）是保证航班没有滑行冲突的条件下，根据航班既定的滑行起点和终点、开始滑行时间、进离场类型和航班类型，确定最优滑行路径以及航班到达每个节点的时间，使总滑行时间最少。

机场滑行道布局抽象化为一个网络图G ＝（V，E），其中，V 代表滑行道与停机位以及跑道的交点、滑行道和滑行道的交叉点；E 代表滑行道、跑道以及脱离道，如图1 所示。A ＝｛1，…，n｝代表航班的集合，其中，Aarr∈A 表示进港航班；Adep∈A 表示离港航班。R＝｛R1，R2，…，Ri…，Rn｝表示所有航班滑行路径，其中，Ri＝｛ui1，ui2，ui3，…，uiki｝表示航班i滑行路径。

图1 机场网络

飞机滑行时可能遇到3种类型冲突［9］，分别为交叉冲突、超越冲突、对头冲突。

1.2 模 型

定义变量如下：

A：航班数；ziju∈ ｛0，1｝，表示当航班i在航班j 之前到达节点u时，ziju＝1，反之，ziju＝0；tiu为航班i到达节点u的实际时间；下标uik1表示航班i的滑行起点；下标uiki表示航班i的滑行终点，dsep表示航班间安全滑行距离。本文航班i的滑行时间是指航班从机器开始发动到机器关闭的时间。目标函数为

为使调度更加公平和合理，本文在模型中引入了航班的出发延误时间，即离港航班在停机坪的等待时间。其中，tid为第i个航班出发时的延误时间，k1和k2表示权值系数。

约束条件

其中，式 （2）表示序列约束，当节点u 是航班i 和航班j的公共节点时，只能按顺序先后经过，不能同时到达；式（3）表示交叉冲突约束，航班i和航班j 在到达u 的时间必须满足最小安全间隔dsep；式 （4）表示超越冲突约束，先到达节点u的航班必须先到达节点v；式 （5）表示对头冲突约束，到达节点u 的航班必须先到达节点v；式 （6）表示进港航班i在预计到港时间EATi着陆，并立即脱离跑道的时间；式 （7）表示航班i从停机坪的推出时间OBTi，这个时间也就是离港航班的开始滑行时间；式 （8）表示航班必须在预计目标离港时间TTDi到达跑道入口准备起飞。

2 基于蚁群算法的滑行道优化调度算法

蚁群算法，是一种有效的启发式仿生优化算法。该算法具有正反馈性、强启发性、协调性以及并行性，很善于处理滑行调度这种复杂的路径寻优问题。

本文蚁群算法分为两个部分。首先，根据协同进化算法解决航班的调度优先级顺序；然后在各种群间根据协同进化的思想，共同进化搜索出协同调度的优化方案。

2.1 机场网络的数据结构

在基于蚁群算法的滑行道调度寻优设计时，首先需要定义数据结构。数据结构分为节点结构和边结构，其中节点的存储采用邻接表结构。在节点的存储数据结构中，引入了航班号flightList链表和时间timeList链表，分别用于记录经过节点的航班和时间。

2.2 转移策略

蚂蚁k在搜索滑行路径时，由当前节点选择下一个未被访问的可行节点时，其转移策略是轮盘赌，概率按式（9）所示，在可行节点集合C中选择下一个节点 （i，j）

其中，τ（i，j，r）和η（i，j，r）分别表示将要访问节点（i，j，r）的信息素信息和启发信息；α和β分别表示路径上的信息量对以后选择路径的影响程度和启发式信息的重要程度。

在滑行道优化调度时，机场网络的存储在邻接表中，所以通过邻接表的查询很快找到下一个可行节点，减少路径规划时搜索的范围。

2.3 信息素更新

蚂蚁在搜索路径时，当出现不可行滑行路径，就对当前经过的路径节点信息素进行一定的挥发，避免蚂蚁再次搜索不可行路径。

为避免算法在搜索过程中陷入局部最优，本文引自文献 ［10］的动态信息素更新策略，对信息素进行局部更新和全局更新。

（1）信息素的局部更新：蚂蚁k 每经过节点（i，j，r），都用式 （10）对边（i，j，r）进行信息素更新

其中，ε∈ （0，1）为信息素的局部蒸发率，τ0为信息素的初始值。

（2）信息素的全局动态更新：当迭代一次后，用式（11）对滑行时间最短的路径进行信息素的更新

其中，ρ∈ （0，1）表示信息素的全局蒸发率；dm表示当前滑行时间最小值；dl表示当前迭代的滑行时间最小值。

在开始迭代时，dm和dl的差距可能很大，通过式 （12）可以大幅度地增强最短滑行时间上的信息素浓度，吸引更多的蚂蚁选择这个路径，使dm和dl的差距逐步缩小，当Δτij变为0时，本次迭代的具有最短滑行时间的路径只进行信息素挥发，避免了因信息素的过分加强而造成算法陷入局部最优。

2.4 适应值函数

蚂蚁k在迭代第t次时的适应函数如下

式中：T1（t）和T2（t）——蚂蚁k第t次迭代时的滑行时间和出发延误时间；k1和k2——滑行时间和延误时间的权值。

2.5 基于两阶段锁的冲突解决算法

航班滑行过程实质是对资源的预约过程。在机场网络有限的资源中，滑行道、停机位、脱离道、跑道等待点、各网络节点都视为资源，航班相当于事物，因此在某一时段内，所有航班的滑行过程，相当于对共享资源的调度分配问题。

航班间的冲突实质是资源的冲突，当航班申请对节点资源的占用时，就是对该节点资源加S锁，当多个航班申请时，按照优先级的高低逐个进行加S锁，优先级高的航班j若加锁成功，则航班j 就对该节点的时间窗［ETj，LTj］加锁；优先级低的航班i也申请已经被锁住的该时间段时，加锁失败，则航班i只能向前回溯，当修改其中的一部分时，就要在满足约束的条件下进行反推，并同时修改相关的部分，否则，会导致不可预料的错误，最后将其占用资源的时间顺延至［ETj，LTj］之外的安全时刻。这样可以保证调度的每个航班都是安全的，没有冲突的，更符合实际的操作规则。

交叉冲突检测与解决算法如下：

超越冲突和对头冲突的解决方法是，让先经过公共边（互逆边）一侧端点的航班，也先经过另一端点；然后调用上述算法确定经过节点k的具体时间点。

3 多蚁群协同优化的滑行道调度

3.1 滑行道调度顺序问题

由于在给定时间内，滑行道调度通常要涉及调度多个航班，它们之间是相互影响的，其中一个航班的滑行时间短，不能代表全局滑行时间最短。因此，航班之间的调度顺序，对总调度结果是有很大影响的。而在前人的研究中却很少涉及航班调度优先级顺序的研究和大面积延误下的随机调度优化。为此，本文在采用协同进化算法，来规划航班的调度顺序，用蚁群算法优化滑行路径。

3.2 多蚁群协同进化算法

借鉴协同进化的思想，采用分而治之的策略。将复杂的多个航班协同路径规划度问题分解为多个单航班路径规划问题，通过单个航班规划之间的迭代求解以及多航班之间协同约束的处理，实现对多个航班的协同调度，从整体上解决调度顺序问题。

在滑行道调度时，将每个航班调度对应一个蚁群，所有蚁群构成一个协同体。在每次迭代时，各蚁群的进化顺序是随机的，各蚁群均采用协同进化算法进行路径搜索。在求解蚁群k 的最优解时，将蚁群k 的每个个体与所有完成进化蚁群的最优个体作为整体解，并进行综合评价，保存历史最优解，经过不断迭代，从而找出最优解。

算法描述：

（1）构造各初始蚁群及其初始信息素，迭代次数j＝0。每个航班的滑行路径由n只蚂蚁进行搜索。令总最小滑行时间time＝＋∞，已经完成进化的蚁群个数为Num。

（2）令Num＝0，初始化各蚁群搜索环境。

（3）随机选择一个没有进化的种群Bi进行进化。

（4）将已完成进化种群B1，B2…Bi－1，Bi＋1…Bj的最优个体经过节点的时间进行标记，将其占有的时间段加锁。

（5）对Bi进行蚁群路径搜索算法，其个体适应度值取决于当前已进化蚁群的最优个体形成的新环境，记录Bi的最优个体。

（6）Num＋＋，若还有没进化的蚁群，则转 （3）；否则，判断是否达到最大迭代次数，若没有，更新time值，使其记录历史最优值，j＋＋，转 （2），否则，转 （7）。

（7）输出最终调度顺序和滑行路径。

算法流程，如图2所示。

图2 算法流程

4 实 验

为验证本文算法的有效性，机场以图1所示简单虚拟机场为例，机场有3条跑道，停机坪位于滑行道网络的中心，并且多个停机坪进口和出口。航班数据以文献 ［11］的8个航班实例进行实验验证。

实验时，各参数确定如下：种群大小为N＝30，迭代次数为M＝200，α＝1，β＝3。航班间的安全距离dsep＝200m。

本文在运行实验10次后，取接近均值的一个结果，实验结果对比如表1所示。飞机的调度顺序为：1－＞8－＞6－＞3－＞7－＞2－＞4－＞5。为了说明本文算法的有效性，与基于先来先服务调度顺序的普通蚁群算法 （即，给定调度顺序）进行了比较。给定蚁群算法的调度顺序为：7－＞8－＞2－＞1－＞4－＞3－＞6－＞5。虽然给定蚁群算法都能成功解决冲突，但存在4处冲突，从而致使航班在这些位置进行延误等待；而本文算法出现了2次冲突，分别在节点N23和N17处，较成功的选择其它路径，避开了冲突，最佳滑行路径时间表示在理想没有冲突的条件下的滑行时间，结果见表1。

表1 滑行结果对比

结果表明，给定顺序蚁群算法的总滑行距离为9500m，而基于本文算法的滑行距离为8500m，虽然本文算法的出发等待时间与普通蚁群算法相当，但滑行距离缩短了1000m，滑行时间也减少了215s，验证了本文算法的有效性。

航班的滑行调度就是确定每个航班的滑行路径和经过每个节点的时刻，下面给出了所有航班的优化调度结果。

5 结束语

本文针对滑行道调度优化问题提出了基于合作型的协同多蚁群调度优化算法。该算法将协同进化的思想引入蚁群调度算法，协同各个蚁群间的相互影响，并解决了调度优化时受调度顺序影响的问题。仿真结果表明，本文算法较给定顺序的蚁群算法，有效缩短了滑行时间和滑行距离，获得了更优的调度方案，验证了本文算法的有效性。但是本文没有考虑航班的机型、优先级，以及航班滑行速度的变化等因素，接下来研究的方向是考虑这些因素，使研究更符合实际情况。

［1］DONG Tiansheng，PENG Jian.Airport taxi scheduling optimization strategy for based on genetic algorithm ［J］.Journal of Computer Applications，2010，3 （2）：482－485 （in Chinese）.［蕫天圣，彭舰.基于遗传算法的机场滑行调度优化策略 ［J］.计算机应用，2010，3 （2）：482－485.］

［2］LIU Zhaoming，GE Hongwei，QIAN Feng.Airport scheduling optimization algorithm based on genetic algorithm ［J］.Journal of East China University of Science and Technology（Natural Science Edition），2008，34 （3）：392－398 （in Chinese）.［刘兆明，葛宏伟，钱峰.基于遗传算法的机场调度优化算法 ［J］.华东理工大学学报 （自然科学版），2008，34（3）：392－398.］

［3］MOU Deyi，LIU Jinfeng.The scheduling strategy model for airport taxiway based on ideal glide path ［J］.Journal of Dalian Jiaotong University，2011，32 （6）：41－45 （in Chinese）.［牟德一，刘金凤.基于理想滑行路径的机场滑行道调度策略模型［J］.大连交通大学学报，2011，32 （6）：41－45.］

［4］LI Nan，ZHAO Qing，XU Xiaohao.Research on taxing optimization for aircraft based on improved A＊ algorithm ［J］.Computer Simulation，2012，29 （7）：88－92 （in Chinese）.［李楠，赵擎，徐肖豪.基于A＊算法的机场滑行路径优化研究 ［J］.计算机仿真，2012，29 （7）：88－92.］

［5］DING Jianli，LI Xiaoli，LI Quanfu.Optimal scheduling model for hub airport taxi based on improved ant colony collaborative algorithm ［J］.Journal of Computer Applications，2010，30（4）：1000－1003 （in Chinese）.［丁建立，李晓丽，李全福.基于改进蚁群协同算法的枢纽机场场面滑行道优化调度模型［J］.计算机应用，2010，30 （4）：1000－1003.］

［6］Clare GL，Richards AG.Optimization of taxiway routing and runway scheduling ［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12 （4）：1000－1013.

［7］Wei B，Centarti F，Schmitt F，et al.Route－based detection of conflicting ATC clearances on airports［J］.arXiv preprint ar－Xiv：1304.6494，2013.

［8］Clare GL，Richards AG.Optimization of taxiway routing and runway scheduling ［J］.IEEE Transactions on Intelligent Transportation Systems，2011，12 （4）：1000－1013.

［9］ZHONG Yuming.Evaluation system study for airport ground running simulation ［D］.Nanjing：Nanjing University of Aeronautics and Astronautics，2009 （in Chinese）. ［钟育鸣.机场地面运行仿真评估系统研究 ［D］.南京：南京航空航天大学，2009.］

［10］WANG Peidong.Improved ant colony algorithm and its application in path planning problem ［D］.Qingdao：Ocean University of China，2012 （in Chinese）. ［王沛栋.改进蚁群算法及在路径规划问题的应用研究 ［D］.青岛：中国海洋大学，2012.］

［11］Roling PC，Visser HG.Optimal airport surface traffic planning using mixed－integer linear programming ［J］.International Journal of Aerospace Engineering，2008 （1）：11.