0 引言

随着中国民航业的快速发展，机场数量、航班数量以及航空器规模等持续增加，虽然各大机场建设正在快速发展，但是当前各机场的停机位、登机门等资源都相当有限，而飞机调度需求却与日俱增。为了缓解这种不平衡现象，相关部门必须使现有资源利用率达到最佳。

停机位是航班停靠在机场的固定位置，也是旅客进、离港时必经的场所，其利用率的大小直接决定了机场和航空公司的利益。停机位分配^[1]3是指在考虑机型大小、航班时刻、停机位大小等因素的情况下，为未来某个时间段范围内的进、离港航班指定最合适的停机位，保证机位与机型的匹配以及旅客行走路程较短。

针对停机位分配问题，国外学者提出了两种不同方法:一种是专家系统，通过将分配原则建立于知识库系统，并考虑较多的非量化准则；另一种是数学规划，以旅客行走路程最短为目标函数，利用0-1整数规划探讨分配的可行性。

相对于国外，由于我国民航事业起步晚，国内对于停机位分配问题的研究还不充分。目前主要是基于旅客行走路程最短或停机位利用率最大的单目标进行优化。

而本文针对机场停机位资源受限和不受限两种情况，在优先保证停机位利用率最大化的前提下，寻找旅客行走总路程最短的多目标停机位分配方案，更符合实际需求。

1 模型构建 1.1 约束条件

停机位分配问题考虑的是在一段时间内，如何为机场的m架航班X={x₁,x₂,…,x_m}，从n个停机位G={g₁,g₂,…,g_n}中选择合适的停机位进行分配，需要考虑的约束条件^[2]主要包括:

1) 适应性:大型机只能停放在大型机位上，小型机可以停放在任意停机位上；

2) 独占性:每架飞机只能被分配到一个停机位上；

3) 唯一性:同一机位最多只能停放一架飞机；

4) 安全性:两架飞机前后要有最小安全时间间隔。

1.2 问题假设及目标函数

问题假设:

1) 同一架飞机的进、离港停机位属于同一个，无需拖车；

2) 同一架飞机的进、离港人数相等。

目标函数:

1) 最大化停机位利用率。

为了最大化机场停机位利用率，停机位大小要与所停放的飞机机型匹配^[3-4]，即大型停机位要优先停放大型机，小型停机位必须停放中、小型机。对于中、小型机，优先为其分配小型停机位，倘若目前没有小型停机位，则将该中、小型机分配到空闲的大型停机位上；对于大型机，只能被分配到大型停机位上。如果目前暂无空闲停机位，则将到达的飞机停放在远机位上等候再次分配。

由于机型与停机位不匹配时会导致停机位资源浪费，因此最大化停机位利用率也就是最小化停机位资源的浪费。对于每个航班，在分配停机位时给定一个参数来表示停机位资源的浪费率:

${{y}_{ij}}=\left\{ \begin{matrix} 0,航班机型与停机位大小匹配 \\ 0.5,机型与停机位大小不匹配 \\ \end{matrix} \right.$

(1)

其中:i表示航班序号，j表示停机位序号。

所以目标函数可以表示为:

$\min {{f}_{1}}=\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{{{\theta }_{ij}}}\cdot }{{y}_{ij}}$

(2)

其中:

${{\theta }_{ij}}=\left\{ \begin{matrix} 1, & 航班i被分配到停机位j上 \\ 0, & 其他 \\ \end{matrix} \right.$

(3)

2) 最小化旅客行走路程。

旅客在机场的行走路程主要包括两段距离^[5]:对于离港乘客，指从安检口到登机口的距离；对于进港乘客，指从登机口到行李领取处的距离。机场停机位、安检口以及登机口的位置都是固定不变的，因此每个旅客的行走距离取决于登机口的位置，而机场旅客总的行走距离则取决于旅客总数量和登机口的位置。因此，将乘客数量较多的飞机停放在距离安检口、行李领取处较近的停机位，才能保证旅客行走总距离最短。

用a_i表示航班i的进港乘客从登机口(停机位j)到行李提取处的行走路程，用d_i表示航班i的离港乘客从安检口到登机口(停机位j)的行走路程，用p_i表示航班i的乘客数量，则目标函数可以表示为:

$\min {{f}_{2}}=\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{{{\theta }_{ij}}\cdot {{p}_{i}}({{a}_{i}}+{{d}_{i}})}}$

(4)

2 算法实现 2.1 简单禁忌搜索算法

一般而言，要设计一个禁忌搜索算法(Tabu Search,TS)，需要确定6个要素:初始解和适配值函数、邻域结构和禁忌对象、候选解的选择、禁忌表及其长度、藐视准则，以及终止准则。

简单TS算法的基本思想^[6]10是:给定一个当前解(初始解)和一种邻域，然后在当前解的邻域中确定若干候选解；若最佳候选解对应的目标值优于当前最优“best so far”状态，则忽视其禁忌特性，用其替代当前解和“best so far”状态，并将相应的对象加入禁忌表，同时修改禁忌表中各对象的任期；若不存在上述候选解，则选择在候选解中选择非禁忌的最佳状态为新的当前解，而无视它与当前解的优劣，同时将相应的对象加入禁忌表，并修改禁忌表中各对象的任期；如此重复上述迭代搜索过程，直至满足停止准则。

2.2 动态禁忌搜索算法

在动态禁忌搜索算法(Dynamic Tabu Search,DTS)中引入禁忌频率来记录每个禁忌对象出现在禁忌表中的次数。初始搜索时，为提高解的分散性，扩大搜索区域，使搜索路径多样化，将禁忌表长度设置得尽量小；当搜索过程接近最优解时，为提高解的集中性，减少分散，缩小搜索区域，将禁忌表长度设置得尽量大。

在算法实现中，用一个数组count存储每个对象的出现次数，若对象i进入禁忌表，则将数组元素count[i]加1并保存。当某个对象的count[i]值超过给定最大禁忌频率RATE时，则改变该对象的禁忌长度LEN(LENGTH)，从而达到约束效果。算法流程如图 1所示。

2.2.1 算法参数的确定

1) 初始解的产生方法。

由于禁忌搜索算法主要是基于邻域搜索^[6]6的，因此初始解的好坏直接影响禁忌算法的性能。因此，本文在描述“最大化停机位利用率”时提到了如何为每个航班选择合适的停机位，对于满足条件的若干停机位，可随机进行分配，从而产生算法的初始解。这样的初始解有利于算法更快地找到最优解^[7]。

2) 适配值函数。

在优先考虑停机位利用率的前提下，能够尽可能实现最小化旅客行走路程是本文需要讨论的内容。为了将该停机位分配问题转化为单目标优化问题，本文引入权重因子λ将两个目标函数结合起来，形成本动态禁忌搜索算法所需要的适配值函数:

$f=\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{{{\theta }_{ij}}\cdot {{y}_{ij}}+}\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{\lambda \cdot {{\theta }_{ij}}\cdot }{{p}_{i}}}({{a}_{i}}+{{d}_{i}})}=\sum\limits_{i=1}^{m}{\sum\limits_{j=1}^{n}{{{\theta }_{ij}}\cdot \left[ {{y}_{ij}}+\lambda \cdot {{p}_{i}}({{a}_{i}}+{{d}_{i}}) \right]}}$

(5)

其中:权重因子取值范围是[0,1]，当λ=0时表示以最大化停机位利用率目标函数f₁作为适配值函数。

3) 邻域结构。

采用2-交换法，在最佳解序列中任选两个航班i和j进行交换，得到若干邻域解，举例:

交换前航班序列为:x₁,x₂,…,x_i,…,x_j,…,x_m。

交换后航班序列为:x₁,x₂,…,x_j,…,x_i,…,x_m。

4) 禁忌表。

禁忌对象:适配值。

禁忌表结构:一维数组，用来存储被放入禁忌表的适配值。

禁忌长度:初始禁忌长度设置为LEN。

禁忌频率:记录同一个适配值进入禁忌表的次数，当该频率大于等于RATE时，修改该适配值对应的禁忌长度。

5) 候选解的选择方法。

对于有N个航班的序列，利用2-交换法可以得到的邻域个数为C_N²个。本文讨论的N值较大，因此采用随机抽取若干邻域，在其中选择适配值较小^[8]的CAN(CANDIDATE)个作为候选解集。选择合适的候选解作为当前最优解，并将其放入禁忌表。

6) 藐视准则。

当某适配值进入禁忌表时，会将其禁忌标志tag(初始值为0)置为1，即当tag=1时，该适配值不能被用作当前最优解放入禁忌表，除非所有候选解的tag都为1，且该适配值最小，才可以忽视其禁忌标志，将其重新放入禁忌表，并修改其禁忌长度。

7) 终止准则。

当迭代次数超出某个预先设定的值ITER时，程序终止，所得到的目前最优解BSF(Best So Far)即为程序找到的最优解。

2.2.2 算法伪代码

初始解X₀;

目前最优解BSF=X₀;

IF 迭代次数≤ITER

{ 交换初始解序列中任意两个航班编号，得到若干邻域解，从中选择适配值较小的CAN个作为候选解集N{X₀};

IF 满足藐视准则

{ 从N{X₀}中选择tag=1的最小值放入禁忌表，并修改其禁忌长度;

}

ELSE

{ 从N{X₀}中选择tag=0的最小值放入禁忌表，并修改其禁忌长度;

}

IF 禁忌对象的禁忌频率大于RATE

{ 修改其禁忌长度；

}

IF 最优候选解 ＜BSF

{

BSF=最优候选解;

}

}

ELSE

{ 程序结束运行;

输出最优解BSF;

}

2.2.3 实例演算

为了验证本动态禁忌搜索算法的优越性，本文的实际数据采用文献[1]中的航班信息，并对其停机位数据略作处理，使得目标函数值更具对比性。

本实例采用8个停机位，其中:6个大型停机位，编号分别为1、2、3、4、5、6；2个小型停机位，编号为7、8。为了对比的可靠性，本演算过程采用时间因素，将“最小化旅客行走路程”转化为“最小化旅客行走时间”问题进行计算。已知，1号和8号停机位到安检口和行李提取处的行走时间均为20min，2号和7号停机位到安检口和行李提取处的行走时间均为15min，3号和6号停机位到安检口和行李提取处的行走时间均为10min，4号和5号停机位到安检口和行李提取处的行走时间均为5min。

DTS算法中固定参数设置:在初始值序列中随机选取150个航班对进行交换，在得到的邻域解集中选择目标值较优的8个作为候选解集。该参数同时适用于停机位资源受限和不受限两种情况。

1) 停机位资源不受限情况下的算法应用。

选择某天一段时间内39架航班为测试对象，航班的具体信息见文献[1]中的表 5.1。为了简化计算，安全间隔时间已包含在航班离港时间中。机型Ⅲ表示大型机，Ⅱ表示中型机，Ⅰ表示小型机。

① 对比一:与文献[1]算法进行对比。

假设停机位初始状态为空闲状态。采用文献^[1]中的初始解序列(如表 1所示)，且设置相同参数:禁忌长度为3，最大迭代步数为100，最大候选解数量为5。

初始解对应旅客行走总时间为92 195min;文献^[1]中初始解对应旅客行走总时间为93 575min。

结果显示，所有航班均分配到停机位，对这些航班运用本文DTS算法进行优化，所得优化结果如表 2所示。

算法优化结果:全局最优解为77 675，比初始解对应的目标函数值减少了15.75%;文献[1]中旅客行走总时间为80 380min，比初始解对应的目标函数值减少了14.10%。

在算法参数相同的前提下，应用本文DTS算法对给定初始解序列进行搜索，得到的全局最优解优于参考文献[1]的最优解。

②对比二:确认本文DTS算法最优参数。

迭代次数、禁忌长度LEN和最大禁忌频率是本动态禁忌搜索算法的关键因素。当禁忌长度不同时，程序搜索到全局最优解的迭代次数会不同。在停机位资源不受限情况下，通过对比禁忌长度为定长和变长两种情况下的迭代次数，验证可变禁忌长度能够更快地实现全局寻优。对比数据如图 2~3所示。

观察图 2可知:禁忌长度为3或5时的曲线处于最底端，表明总体迭代次数较少，运行结果较优。

说明:图 3中的参数组a-b-c表示初始禁忌长度为a，最大禁忌频率为b，禁忌长度的变化量为c，即当某禁忌对象的禁忌频率达到b时，其禁忌长度变化为a+c。

观察图 3可知:参数组为3-5-2时的曲线处于最底端，表明总体迭代次数较少，运行结果最优。将其原始数据求平均值可求得算法寻优的平均次数为33。

结果表明，对于给定的航班信息，本文DTS算法最合适的参数为:初始禁忌长度为3，最大禁忌频率为5，禁忌长度变化量为2，最大迭代步数为33。

2) 停机位资源受限情况下^[9-10]的算法应用。

选择某天一段时间内31架航班为测试对象，航班具体信息见文献[1]中的表 5.4。

①对比一:与文献[1]算法进行对比。

假设停机位初始状态为空闲状态。采用文献^[1]中的初始解序列(如表 3所示)，并设置相同参数:禁忌长度为3，最大迭代步数为100，最大候选解数量为5。

结果显示:有5个航班没有分配到停机位，需在远机位等候调度。初始解对应的目标函数值为59 460。

对分配到停机位上的航班运用本文DTS算法进行优化，所得优化结果如表 4所示。

算法优化结果:全局最优解为45 880，比初始解对应的目标函数值减少了22.84%；而文献[1]中旅客行走总时间为53 765min，比初始解对应的目标函数值减少了12.50%。

结果表明，在算法参数相同的前提下，应用本文DTS算法对给定初始解序列进行搜索，得到的全局最优解优于文献[1]的最优解。

②对比二:确认本文算法最优参数。

在停机位资源受限情况下，通过对比禁忌长度为定长和变长两种情况下的迭代次数，验证可变禁忌长度能够更快地得到全局最优解。对比数据如图 4~5所示。

观察图 4可知:禁忌长度为3、6或7时的曲线处于最底端，表明总体迭代次数较少，运行结果较优。

观察图 5可知:参数组为3-3-4时的曲线处于最底端，表明总体迭代次数较少，运行结果最优。将其原始数据求平均值可求得算法寻优的平均次数为15。

结果表明:对于给定的航班信息，本文DTS算法最合适的参数为:初始禁忌长度为3，最大禁忌频率为3，禁忌长度变化量为4，最大迭代步数为15。

③对比三:初始解采用本文算法来获得。

假设停机位初始状态为空闲状态。按照本文约束条件及求解策略，得到在停机位资源受限情况下的初始解序列，如表 5所示。

初始解对应的目标函数值为51 260，与表 3的对比结果表明:在航班和停机位信息相同的情况下，使用本文的求解策略得到的初始解对应的目标函数值更加接近于全局最优解。

3 结语

本文所提动态禁忌搜索(DTS)算法利用禁忌表、邻域、禁忌频率等元素，使得算法可以在全局范围内寻找到同时满足“停机位利用率最大”和“旅客行走路程最短”的最优解。同时，由于初始解的产生并不是随机的，而是考虑了某些约束条件后得到的，因此能够更好地得到最优解。

本文主要特点包括:

1) 初始解并不是随机产生，而是优先为航班分配与其机型匹配的停机位，然后求解旅客行走总路程最短的停机位分配序列，从而提高旅客的满意度；

2) 本文增加了禁忌频率，用来记录禁忌对象在禁忌表中出现的次数，从而调整该对象的禁忌长度，达到动态控制算法的目的。

改进后的DTS算法虽然更有优越性，但是在实际应用中仍然存在不足之处:实际情况下的停机位分配受到多种约束，尤其是一些不可控的人为因素，这些因素在本文中并未很好地体现。因此本文只能达到理论上的最优，而无法找到实际情况下的最优解，下一步工作则会增加更多的约束条件，使得算法更加适合实际情况下的寻优。