基于改进马群算法的进场航班调度优化

张宇宁,乐美龙

(南京航空航天大学 民航学院,南京 210000)

随着航空运输的不断发展,交通流量不断增加,交通流需求与现有空中交通管理空域容量不匹配,不能通过增加交通基础设施来解决这一问题[1].据预测,在未来20年内,常规航空运输量将增加50%,而累计延误的风险将达到目前的15倍[2].高效的空中交通管理策略是增加机场容量的重要方法之一,进场航班排序问题或航空器着陆问题(Aircraft Landing Problem, ALP)是终端区空域管理优化部分的重要问题,同时也是一个NP-hard问题.

由于随问题规模增加计算规模指数化增长,大规模问题多采用启发式算法, Beasley J·E 等[3]建立了ALP 的混合0-1整数规划模型,使一些通用近似算法框架可以在该问题中使用,现有文献中使用的启发式算法按迭代中解的规模分为单解算法和群解算法两类:单解算法包括禁忌搜索、邻域搜索类的启发式算法;群解算法主要是遗传算法、粒子群算法和一系列群智能算法,文献中提出的算法绝大部分使用OR-Library数据集测试.在单解算法方面,Salehipour等人[4]提出变邻域模拟退火算法(SA+VND)混合算法,提出两种交换策略构成邻域空间,应用于VND框架中,并且与模拟退火算法结合,解决多跑道问题.Salehipour等人[5]还提出一种启发式和CPLEX求解器结合的算法,算法框架简单且在数据集上效果较好,在此基础上,Salehipour等人对该算法进一步改进[6],采用了目标着陆时间优先的初始化分派规则,用于解决单跑道和多跑道问题.张军峰等人[7]提出一种新的元启发式方法,采用机器调度中的复合分派规则优化航班排序,结合求解器求解固定排序下的最佳降落时间,解决单跑道问题.

在群解算法方面,Beasley 等人提出散点搜索和生物算法,通过直接启发时间来解决多跑道问题.Hu等人[9]引入滚动时域控制策略,与遗传算法结合,考虑时间窗和最小间隔约束,目标函数为累积延误,解决动态情况下的航班排序问题,在30架次航班的新的实例上进行测试.Ji等人[10]基于分布估计算法设计DSSE算法,解决动态进场航班排序问题,并采用北京首都机场数据进行验证.Girish等人[11]在粒子群算法思想基础上,与滚动时域控制策略相结合,提出一种混合启发式算法解决单跑道和多跑道问题,采用新的交叉策略和局部搜索策略替换粒子群算法中的认知项和社会项,该算法目前在OR-Library数据集上的结果最优.Zhou等[12]提出了一种基于跑道平衡的花朵授粉算法,该算法在基础花粉受精算法的框架中引入情境认知学习以进行全局搜索,加入行走策略以进行局部搜索,引入交换算子和插入算子作为扰动策略以跳出局部最优,加入跑道平衡策略以平衡跑道间的负荷.张军峰等[13]提出基于多目标帝国竞争算法的进场排序与调度方法,利用机器调度理论精简目标,采用OR-Library数据集和长沙黄花机场实际运行数据进行验证.

本文的研究针对静态进场航班调度问题,考虑尾流间隔和时间窗约束情况下,以最小化加权延误成本为目标,首先建混合0-1整数规划模型;然后根据新型群智能算法框架——马群算法[14],在马群算法框架的基础上,提出并行2-opt模拟退火搜索策略和新型概率融合个体生成策略,替换马群算法中原有策略;最后利用OR-Library中的实例验证所提出算法的效果.

1 问题描述

ALP的目标是优化航班进场调度,最小化成本函数,问题中给定每架航班的目标着陆时间,偏离着陆到达时间降落会产生一定成本,每一架航班的成本函数是一个分段的随偏离时间变化的线性函数.降落时间需要在限定的时间窗内,且前后两架飞机的降落时间之间需要满足尾流间隔(Wake Vortex separation)规定,保证降落或起飞时飞机不会受到前面飞机机翼尾部产生的涡流影响.

1.1 符号定义

P为航班数量;Ei为航班i最早着陆时间;Li为航班i最迟着陆时间;Ti为航班i目标着陆时间;qi为航班i于Ti前着陆的单位时间成本;li为航班i于Ti后着陆的单位时间成本;Sij为航班i在j之前着陆需要的最小尾流间隔时间;xi为航班i的着陆时间;δij为航班i在航班j之后降落取值为1,否则为0;αi为max(0,Ti-xi);βi为max(0,xi-Ti)

1.2 模型建立

(1)

δij+δji=1,i,j=1,2,…,P,i≠j

(2)

xj≥xi+Sijδij-(Li-Ei)δij,i,j=1,2,…,P,i≠j

(3)

Ei≤xi≤Li,i=1,2,…,P

(4)

0≤αi≤Ti-Ei,αi≥Ti-xi,i=1,2,…,P

(5)

xi=Ti-αi+βi,i=1,2,…,P

(6)

0≤βi≤Li-Ti,βi≥xi-Ti,
xi≥0,i=1,2,…,P

(7)

δij∈{0,1},i,j=1,2,…,P,i≠j

(8)

其中:式(1)表示最小化成本的目标函数;式(2)、(8)中表示δij=1或0且δij和δji中只有一个为1;式(3)表示每一航班对(i,j)降落时间的安全间隔约束;式(4)表示时间窗约束;式(5)～(9)将xi与αi,βi联系起来,便于目标函数的计算.

2 改进马群算法

马群优化算法(Horse herd optimization algorithm)是基于马在其生活环境中的行为模式设计的算法[18].马的行为模式一般包括放牧(Grazing)、等级制度(Hierarchy)、社交(Sociability)、模仿(Imitation)、防御机制(Defense)和漫游(Roam),马群算法基于不同年龄段的马的不同行为设计,在数值优化方面对高维优化效果显著.在每次迭代中马匹的位置更新公式为:

1) 个体编码和解码方式;

2) 初始解生成策略;

3) 行为向量表示方式.

2.1 个体编码和解码方式

由于航班排序问题的特殊性,并且基于排列编码的搜索策略更容易设计,因此采用排列编码的方式表示个体.见图1.

图1 排列编码示意图Figure 1 Diagram of permutation coding

进场航班排序问题可分解为确定航班着陆的先后顺序和确定航班的调度着陆时间(Scheduling Landing Time, SLT)两个子问题,将其对应于个体的编码和解码过程.根据文献中的调度时间生成算法[11],在给定序列下可得到最优航班着陆时间,从而确定目标函数值.

2.2 初始解生成策略

为了使种群在多样化和优越性之间保持平衡,在马群算法中采用三种不同的初始解生成策略:1)最早着陆时间优先策略,即航班的最早着陆时间排序序列作为初始解;2)目标着陆时间优先策略,即航班的目标着陆时间排序序列作为初始解;3)随机生成策略,即随机排列航班生成航班排序序列.为得到有较好的初始搜索位置,同时避免陷入局部最优,保持种群多样性,对应策略个体在种群中的比例为10%,10%,80%.

2.3 行为向量表示方式

将马匹行为按照搜索方式分类,可分为深度搜索行为和广度搜索行为,其中放牧和漫游行为属于广度搜索行为,可使算法跳出局部最优解,搜索全局最优解,等级制度、社交、模仿和防御行为属于深度搜索行为.由于排序问题是组合优化问题,解空间离散,若按标准马群算法进行描述,其速度向量难以表达,故根据马群算法的基本思想,分别针对此问题设计两种搜索策略.

2.3.1 并行2-opt模拟退火搜索

参考旅行商问题常用的局部搜索方法2-opt[15],在此算法基础上加上交换算子,并采用并行框架,单次计算多个结果,选取并行池内最优变异个体,最后利用模拟退火机制判断是否接受新解.算子计算过程示意图见图2,设定邻域范围为一定值假设为2,随机选定一个邻域中心点如图中的3,以邻域中心点2的范围内与邻域中心进行交换或翻转(图示为交换).2-opt算法每次仅生成一个新解,且仅采用翻转方式,邻域搜索速度较慢,该算子可以一次生成一批新解,并采用并行的方式计算目标函数值,大大提升邻域搜索速度.

并行2-opt模拟退火搜索的流程图如图3所示.

图3 并行2-opt模拟退火策略流程图Figure 3 Flow chart of parallel 2-opt annealing simulation strategy

2.3.2 广度搜索算子

将马群算法中广度搜索行为看作交叉操作,使当前解与对应个体进行交叉,交叉个体根据年龄和随机数生成选择.如年龄阶段为γ的个体,其速度向量包括所有6种行为,其交叉个体选择如下:

crossIndividual=

由于排列编码个体交叉后容易产生重复染色体,采用概率融合个体生成方式,见图4.

图4 概率融合个体生成示意图Figure 4 Diagram of probability fusion individual generation

以个体适应度倒数作为轮盘赌选择标准,从每个个体的初始位置开始,每回合选取对应个体的序号,如果该序号已经在新个体中,则移向下一个,直到新个体成为完整个体.选择每个个体的概率计算公式为:

(11)

其中:N表示选择进行子代生成操作的个体数目.交叉过程如图4所示,图4中显示了新个体前4条染色体的生成过程,表1为三个个体在轮盘赌过程中的被选择的概率和累积概率,表2为前4步的选择结果.

表1 个体轮盘赌概率Table 1 Probability of roulette strategy for individuals

表2 前4步选择流程Table 2 First 4 steps for choosing chromosome

改进马群算法的算法流程如图5所示.

图5 改进马群算法框架流程图Figure 5 Flow chart of improved HOA

3 算例验证

本文利用进场排序调度研究的公共数据集案例(OR-Library,http://people.brunel.ac.uk/～mastjjb/jeb/orlib/airlandinfo.html),验证启发式马群算法的效果,并与SA+VND,SS,MPDS_MHA对比.

数据集中包括13个实例问题,其中案例1～8是小规模问题,航班架数范围为10～50架次,案例9～13属于大规模问题,航班架次为100,150,200,250,500,具体信息如表3所示.

表3 OR-Library数据集案例信息Table 3 OR-Library data set information

用最优值和当前算法求得的解的差值的百分比来衡量算法的效果是常用的方法,该指标的计算如下:

(12)

其中:Obja为当前算法求得的最优解,ObjBKV是目前所有方法中能够求得的最好解.为直观呈现算法求解优度和速度,将Gurobi求解器3 600 s的运行结果和ObjBKV与算法运行结果对比,启发式算法在大规模数据集上的求解时间(大于等于100架次)均没有超过Gurobi求解器.

实验中,IHOA的参数为:衰减系数ωα,ωh,ωs,ωi=0.95,模拟退火初始温度gα,gβ,gγ,gδ=100,分级系数hβ=0.9,hγ=0.5,社交行为系数sβ=0.2,sγ=0.1,模仿行为系数iγ=0.3,最大迭代次数为30次,种群规模为10.

为判断算法稳定性,根据3σ准则判断10次结果中是否有异常值,以Airland9为例,结果如图6 ,10次运行结果中均没有超过3σ限制,算法稳定性较好.

图6 Airland9案例3σ判别Figure 6 Airland9 Case 3σ discrimination

图7给出对于Airland9的5次运行结果,用不同线型表示,可以看出基本在10代之内收敛,在大规模算例中也能够有较快的收敛速度,且5次运行结果均能够得到此案例的最优值,算法寻优能力较强.

图7 Airland9算法收敛图(运行5次)Figure 7 Convergence of case Airland9(5 times)

不同算法之间在同一数据集的对比能够体现算法的寻优能力,选取算法包括邻域搜索类、群智能算法类,求解结果如表4所示.

表4 算例求解结果对比Table 4 Comparison of computational results

在不同算法对比中,IHOA在小规模问题中GAP均为0,表示可以得到最优解,在小规模问题中比MPDS_HA、SS效果更好.IHOA在小规模算例中基本在10次迭代之内即可达到最优解,收敛速度极快,继承了标准马群算法收敛速度的特点.

利用IHOA对大规模算例进行求解,IHOA在算例9,11,13中可以得到优于Gurobi求解器的结果,与最优解的最大GAP仅为1.15%.

4 结 语

本文针对进场航班调度问题,建立混合整数规划模型,由于求解器求解大规模问题用时较长,使用新型群智能算法马群算法框架,基于排列编码方式提出并行2-opt模拟退火搜索策略和融合个体生成策略,为算法加入邻域搜索和进化策略.通过OR-library数据集案例与现有算法和求解器对比,验证算法有效性,可为未来进港排序辅助决策系统提供参考.