基于状态空间模型序号编码进化算法的航班优化调度

李恒,李茂军

(1．长沙理工大学,湖南 长沙 410114;2．长沙航空职业技术学院,湖南 长沙 410124)

随着我国航空业的快速发展,原有的先到先服务(First Come First Service, FCFS)航班调度方法[1],已不能满足现有航班调度要求和我国航空业的发展需求。因此,针对航班进离港优化调度问题,国内外许多学者进行了较为深入的研究,他们从航班调度模型、优化目标、求解算法等不同的方向优化解决问题。

Faye[2]采用多项式时间算法与模拟退火法相结合的方法,求解单跑道航班调度数学模型。Landry等[3]开发了基于独立分布式网络的航班调度系统,以解决进离港航班调度问题。徐兆龙[4]等构建了多跑道航班多优化目标的协同调度模型,采用蚁群算法对模型进行求解,能有效缓解终端区的拥堵问题。王璐等[5]采用遗传算法对航班着陆调度模型进行求解,为机场制定航班着陆方案提供依据。黄涛等[6]建立多跑道进离港航班调度模型,采用AATC-SR-SA的启发式算法进行求解,并给出最优的调度方案。潘贺[7]建立单跑道机场进离港航班调度模型,结合航班实际数据,采用改进的基于免疫球蛋白的人工免疫系统算法进行求解,证明了模型和算法的可行性和鲁棒性。虽然上述模型和算法各有所长,但是这些模型多以延误时间和跑道的吞吐量为目标,对多跑道航班调度的总延误损失和航班调度的公平性研究较少。

基于状态空间模型的进化算法(Evolutionary Algorithm Based on State-space Model,SEA)[8]是李茂军教授提出的一种新颖的进化算法。在电力市场竞价[9]、城轨自动运行列车速度优化[10]、轨道交通优化调度[11]等实际应用问题上取得了良好的效果。虽然SEA能有效解决上述问题,但都是采用实数编码,对于采用序号编码解决组合优化问题(如航班优化调度问题[4]、旅行商问题和Flow-shop问题[11]等)研究较少,因此本文提出一种基于状态空间模型序号编码进化算法(Order Coded Evolutionary Algorithm Based on State-space Model,OSEA),并研究其在航班进离港优化调度中的应用。仿真实验表明:这种算法对于解决航班进离港优化调度的航班排序问题是非常有效的。

1 多跑道航班优化调度模型

1.1 目标函数

多跑道航班进离港优化调度是将某一时间窗内进离港航班看作一个整体,在确保飞机起降安全的前提下,以航班总延误损失、跑道容量和飞机最小安全间隔等为约束条件,对进离港航班顺序进行统一优化排序,使得研究时段内机场所有航班总延误损失最少,机场航班吞吐量最大,属于多目标的组合优化问题[13]。其总延误损失目标函数定义如下:

(1)

符号说明如下:

L为机场独立平行跑道集合,L={1,2,…,l};

Ss为时隙集合,S={S1,S2,…,Ss};

flti为1表示跑道l上有航班降落或起飞;为0表示跑道l上没有航班降落或起飞;

ssi为1表示时隙ss分配给航班;为0表示时隙ss不分配给航班;

AATmax为进港航班的最大提前延误时间;

ADTmax为进港航班的最大滞后延误时间;

DATmax为离港航班的最大提前延误时间;

DDTmax为离港航班的最大滞后延误时间;

CM为所有航班的总延误损失;

δij为连续两架进离场航班的最小安全飞行时间间隔;

1.2 约束条件

式(2)为相邻两架航班的最小安全飞行间隔约束。

(2)

式(3)、式(4)为进/离港航班起飞/降落时隙资源约束。每一个进/离港航班,只有分配到一个起飞/降落时隙,才允许进/离港降落。

(3)

(4)

式(5)、式(6)为跑道资源约束,表示一条跑道在同一时间内,最多只能有一架起降航班。

(5)

(6)

式(7)表示任意时刻内,所有跑道上起降航班数量小于或等于跑道数量。

∑flti≤r

(7)

式(8)、式(9)表示进/离港航班不能超过规定的最大延误时间。

AATMAX≤STAi-ETAi≤ADTMAX

(8)

DATMAX≤STDi-ETDi≤DDTMAX

(9)

2 基于状态空间模型序号编码进化算法

2.1 算法简介

遗传算法的编码方式有二进制编码、实数编码和序号编码等不同方式。但在求解组合优化问题(如航班优化调度问题、旅行商问题和Flow-shop问题等)时,采用序号编码比其他几种编码方式更直接、更方便。序号编码遗传算法不能采用常规的交叉算子,因此有学者提出了针对序号编码遗传算法的POX、JOX、SPX[14]等特殊交叉算子,但这些交叉算子操作较难实现,因此本文提出一种用于求解组合优化问题的基于状态空间模型序号编码进化算法(Order Coded Evolutionary Algorithm Based on State-space Model,OSEA)。此算法采用序号编码,不使用交叉算子,只使用变异算子,且通过构造状态进化矩阵等操作来实现变异算子的功能,简化了遗传操作,继承了SEA算法[8]和单亲遗传算法[13]的优点。OSEA算法将问题的解答过程表示为离散状态空间模型的动力学过程,突破了遗传算法的计算模式[15]。

2.2 算法原理

OSEA算法采用序号编码方式,不使用交叉算子,通过构造状态进化矩阵来实现基因换位等遗传算子功能,使种群不断的进化,并结合选种池的选择操作实现种群的优胜劣汰。状态空间模型序号编码进化算法表示为离散系统的状态空间模型:

X(k+1)=GX(k)

(10)

其中X(k)表示第k代群体,G为状态进化矩阵,X(k+1)表示第k+1代群体。X(k)是一个N×M的矩阵,此矩阵的各个行向量表示一个个体,即有N个个体,每一个个体包含M个变量。通过构造状态进化矩阵G来改变基因的排序,保持群体X(k)的多样性并不断地进化,它是一个N×N进化矩阵,矩阵的每一行有且只有一个元素为1,其余为零,其构造方式如下:

(11)

2.3 算法的操作步骤

状态空间进化算法的操作步骤如下:

Step1:使用序号编码,随机生成一组满足约束条件的初始群体X(0),置k=0;

Step3:根据式(11)构造状态进化矩阵G;

Step4:按照式(10)进行迭代计算,生成下一代群体X(k+1),并计算下一代群体X(k+1)中个体的适应度值;

Step5:将下一代群体X(k+1)不满足约束条件的个体,其适应度值赋值为零,再把X(k)和满足约束条件的X(k+1)一起投入选种池;

Step6:根据适应度值大小,按从大到小顺序排列,选择前N个适应度值对应的个体构成下一代群体X(k+1),然后置k=k+1;

Step7:对计算结果进行判断是否满足结束条件,若满足结束条件,则输出计算结果;否则,跳转到Step3继续循环。

3 仿真结果与分析

为了验证OSEA算法的有效性,本文选取我国某大型机场节假日高峰时段内的24架航班进行仿真实验,并将实验结果与FCFS算法进行对比。

在求解航班优化调度数学模型的计算中,FCFS算法和OSEA算法种群规模N=200,最大迭代次数300次。为测试模型和算法的性能,在仿真实验中随机选取10次计算结果,如表1、表2所示。

表1 FCFS算法随机计算10次的结果

表2 OSEA算法随机计算10次的结果

从表1、表2可以得出:OSEA算法在65代左右可以得到最优解,计算速度比较快,航班最低延误损失为72774.1元,FCFS算法在170代左右才能得到最优解,计算速度较慢,航班最低延误损失为108427.5元,因此OSEA算法与FCFS算法相比能够大幅度降低航班的延误损失,效果更好,收敛速度更快。

用AC%、BC%、CC%分别表示平均值与最小值的误差、平均值与最大值之间的误差、最大值与最小值之间的误差,求出各项误差结果,如表3所示。

从表3可以看出,OSEA算法AC%的误差BC%值很小,CC%的误差值相对较小,而FCFS算法AC%、BC%、CC%的误差值普遍较大,说明OSEA算法比FCFS算法的稳定性和可靠性更好。因为是求航班总延误损失最小值,由此可以判断72774.1元为OSEA算法的最优解,得出优化后的航班时刻表,并与FCFS优化后的航班序列进行比较,如表4所示。

表3 算法各项误差结果

表4 FCFS和OSEA算法结果对比

从表4可以看出,OSEA算法与FCFS算法对比:OSEA算法使得所有航班总延误损失为72774.1元,而FCFS算法的总延误损失为108427.5元,优化后的航班延误总延误损失降低了32.88%,且操作简单、运算速度更快。

4 结 论

提出了一种OSEA算法,此算法采用序号编码方式,不使用交叉算子,通过构造状态进化矩阵来实现基因换位等遗传算子功能,简化了遗传操作,继承了SEA算法和单亲遗传算法的优点,并将这种算法应用于航班进离港优化调度。通过仿真实验表明,本文所提出的方法在求解航班进离港优化调度方面具有很好的实用性,能够快速找到问题的最优解,减少了算法的运算时间,并且更方便、直接。

本文只给出了一种构造状态进化矩阵的方法,如何通过构造更好的状态进化矩阵提高算法的全局收敛性,有待进一步研究。