改进乌鸦搜索算法在邮件集散中心航空运力调度中的应用①

卢卓桓, 仰燕兰, 叶 桦

1(东南大学 自动化学院, 南京 210096)

2(复杂工程系统测量与控制教育部重点实验室, 南京 210096)

邮件集散中心 (简称集散中心) 作为全国邮政网络的重要枢纽, 主要负责对邮寄实物进行转发和运输. 数据预测, 2021至2035年全社会货运量年均增速约为2%. 稳中有升的货物运输需求之下, 高价值、小批量、时效强的货物运输需求快速攀升. 在此背景下, 航空快件运输凭借其时效优势成为集散中心的重要业务之一[1].当前, 集散中心的航空运力主要为全货机 (固定运力)和客机腹舱 (备选运力). 由于两种运力方式在时间、成本、载运量等方面各异, 不同运力调度方案的运输效率、综合成本差异较大. 因此, 合理调度航空运力成为提升集散中心航空快件保障能力、处理效率, 实现降本增效的重要举措.

目前, 国内外关于航空运力调度问题 (air capacity scheduling problem, ACSP) 的研究主要集中在民航公司的飞机排班问题上, 包括机型指派, 机队分配, 航班时刻优化等. Hane等研究了一般形式下的机队分配问题, 并建立整数规划模型成功求解了某大型航空公司的机型分配问题[2]. Rexing等提出了带时间窗的机队分配模型, 并开发了速度优先的直接算法和内存优先的迭代算法进行求解[3]. Khanmirza等针对航空公司的时刻表设计和机队分配提出了一种并行主从遗传算法进行求解, 该算法能够在短时间内解决大规模的调度问题[4]. 孙宏等在分析了国内航空公司的航线结构和飞机排班要求后引入了“航班节”的概念, 提出了用于描述单枢纽航线结构下飞机排班问题的排序模型, 并设计一种分阶段指派算法用于求解[5].

相比于目前的研究方向, 集散中心的航空运力调度问题 (air capacity scheduling problem of mail distribution center, ACSP-MDC) 具有一定的差异性. 一方面,集散中心航空运力调度的重点不再是客机的排班, 而是综合调度两种运力, 使既定目标最优. 另一方面, 飞机排班问题是根据航班计划和现有资源的情况为每个航班指定一架具体的飞机. 而ACSP-MDC不仅需要为航线选择合适的飞机, 还需要为选中飞机分配载运量,使集散中心当天所有的邮寄实物能顺利运输到各个目的地.

ACSP-MDC作为ACSP的扩展问题, 其基本目标是在一定航空运力资源的约束下得到合理的调度方案,使空运成本最低. 近年来, 元启发式算法因其具有较好的适用性和鲁棒性, 已经成为解决此类问题的主流方法. 李耀华等将飞机排班计划一体化优化模型问题归结为多目标车辆路径问题, 并提出一种自适应单亲遗传算法进行求解[6]. 李红启等构建了航空快递的地面集货运力和航空运力协同调度问题的混合整数规划模型,并设计一种两阶段启发式算法进行求解[7]. 本文在对比了各种元启发式算法之后, 考虑到乌鸦搜索算法 (crow search algorithm, CSA) 具有结构简单, 控制参数少, 寻优能力较强等优点[8], 且算法的有效性和实用性已在作业车间调度、工件设计、图像分割等不同工程领域中得到证明[9-11], 选择其作为本文的基础算法. 本文针对ACSP-MDC的特点, 引入惩罚函数法以消除部分约束,并在CSA的基础上, 对初始化种群、乌鸦位置更新等环节进行改进, 同时引入交叉变异机制, 提出混合交叉策略和自适应变异策略以丰富种群的多样性.

1 ACSP-MDC 问题模型

1.1 问题描述

集散中心经过邮件分拣、邮件过检、封发装箱等前置环节之后, 需要调度航空运力, 将邮寄实物发往不同的城市. 可供集散中心调度的航空运力包括集散中心所拥有的全货机和民航客机的腹舱. 全货机通常在夜间飞行, 其优势是起飞时间灵活、运载量大, 且变动成本(单位: 元/(t·km)) 较低, 但是每启动一架全货机,需要额外支出维修费、起降停场费、地面服务费等固定成本, 因此, 全货机的载运率越高, 启动全货机运输会更加划算. 客机航班的起飞时间由航空公司制定, 变动成本由航空公司或第三方货运代理制定, 每架客机能提供的货运量受到飞机型号和当日旅客的行李量所限制. 因此, 集散中心在选择备选运力时只能在航空公司制定的航班计划中选择合适的航班运载邮寄实物.

综上所述, 邮件集散中心航空运力调度问题 (ACSPMDC) 可定义为: 集散中心从固定运力和备选运力中选择合适的运力资源, 合理安排每种资源的飞行航线和载运量, 在满足一定约束的前提下 (载重约束、航线约束等) 最小化运输成本.

1.2 数学模型

为了便于描述ACSP-MDC的数学模型, 首先引入如下的符号定义:

K: 航线集合, K ={1,2,···,l};

I: 全货机集合, I ={1,2,···,n};

Jk: 航线k 的客机航班集合, Jk={1,2,···,mk};

dk: 航线k的空距;

wk: 航线k的待运货物量;

cargo_mli: 全货机i 的最大载运量;

cargo_fci: 启用全货机i 的固定成本;

cargo_vci: 全货机i 的变动成本;

civil_mlkj: 航线k 航班 j 的最大载运量;

civil_vckj: 航线k 航班 j 的变动成本;

M: 充分大的正数;

xik: 全货机i 飞 航线k 的载运量;

yik: 0-1变量, 是否使用全货机i 飞 航线k;

ukj: 航线k航班 j 的载运量.

ACSP-MDC的数学模型为:

目标函数:

约束条件:

目标函数式(1)由3个部分组成, 分别是全货机的变动成本、全货机的固定成本和客机航班的变动成本,其中, 变动成本的计算方法为: 飞机载运量×航距×飞行的单位成本; 约束(2)是航线载重约束, 表示每条航线全货机和客机航班的载运量之和需要满足该航线邮寄实物的待载运总量; 约束(3)-(4)分别是客机和全货机的载重约束, 表示每种运力资源的载运量大于0且不能超过其最大载重; 约束(5)表示一架全货机最多只能飞一条航线; 约束(6)约束了 xik和yik之间的关系, 表示只有选中全货机 i 飞 航线k , 才会为其分配飞往航线k 的载运量, 否则全货机i 到航线k 的载运量为0.

2 改进乌鸦搜索算法

乌鸦搜索算法是基于乌鸦藏食和窃食的社会性行为进行开发的, 其位置更新公式如式(7)所示:

朴素CSA的算法流程如图1所示.

图1 朴素CSA算法流程图

为了使CSA能够有效地解决ACSP-MDC, 本文根据具体场景的约束, 对CSA在求解过程中的各个步骤进行一定程度的改进.

(1) 使用惩罚函数法消除部分约束, 拓宽乌鸦搜索的可行域, 避免在Step 5检查乌鸦新位置可行性时, 过多乌鸦因为不满足原有约束而被丢弃;

(2) 在Step 2初始化种群时引入基于幂函数载波的Logistic混沌映射, 提高初始种群的多样性;

(3) 针对ACSP-MDC的特殊性, 提出了基于个体最优追随的位置更新策略取代Step 4的随机跟随策略,并嵌入正余弦算子, 提高CSA的搜索能力;

(4) 引入交叉变异机制, 根据ACSP-MDC的特点,提出两种不同的交叉策略和一种自适应变异策略, 维持搜索过程中种群的丰富性, 让算法有更大概率跳出局部最优, 从而找到全局最优解.

2.1 基于惩罚函数法的约束消除

在解决约束优化问题时, 通过适当地引入约束处理技术, 可以平衡目标函数和约束条件的信息, 使优化算法更加高效. 惩罚函数法是其中一种常见且有效的技术, 其基本原理是: 将问题的约束条件转换为一个惩罚函数并加在原目标函数中, 构造出一个增广目标函数. 若当前解不满足约束条件, 增广目标函数就会加大惩罚, 淘汰可行域之外的解[12]. 通过引入惩罚函数, 可以减少ACSP-MDC中的约束条件, 扩大解的可行域,避免部分乌鸦因为不满足约束而被视为无效个体, 同时也可以省去算法中处理特定约束的步骤和时间.

本问题的约束条件为式(2)-式(6), 其中, 约束(3)和约束(4) 在搜索过程中通过边界修复来实现, 如式(8)和式(9)所示:

由于存在约束(5)-式(6), 使得xi=[xi0,xi1,···,xil]中只有一个维度的值大于0, 其余维度值均为0, 故可将式(9)转化为式(10):

约束(2)和约束(5)则通过进入惩罚项来消除, 结果如式(11)所示:

其中, σ1和 σ2为惩罚因子, 在本文中, 将其设置为足够大的正数即可.

引入惩罚项后, 评价乌鸦位置优劣的适应度函数可定义为:

其中, Fc为 目标函数, Fp为惩罚项, 式(12)表明, 适应度值越小, 乌鸦的位置越优.

2.2 初始化种群

初始化种群的好坏直接影响智能群体算法的寻优精度和收敛速度, 朴素CSA采用随机方法生成初始化种群, 这种生成方式有两个弊端. 其一, 容易造成乌鸦的位置分布不均匀, 导致乌鸦种群难以搜索到整个空间, 易陷入早熟, 最终只能得到局部最优解; 其二, 对于约束较为复杂的问题, 随机生成的乌鸦容易逃逸出搜索空间的可行域. 尽管本文通过引入惩罚函数, 边界修复等方式消除了约束, 扩大了乌鸦搜索的可行域, 初始化高质量的种群仍是必要的, 因为初始化乌鸦个体如果能尽量落在满足原约束的可行域内, 它们将更靠近最优解, 搜索效率会更高.

因此, 本文引入了基于幂函数载波技术的Logistic混沌映射[13]来提高乌鸦种群的多样性, 同时借鉴文献[14]对0-1变量的混沌初始化方法, 使初始的乌鸦个体更加靠近最优位置, 为后续的搜索打下基础.

2.2.1 幂函数载波技术

Logistic映射方程为:

其中, zn为生成的[ 0,1]区 间的混沌值, 迭代初始时z0为随机生成的混沌初值, 但不可取0、0.25、0.75、1;µ∈[0,4], 为控制参数, 当 取4时, 系统处于完全混沌状态. 虽然Logistic映射产生的混沌变量具有遍历性, 但由于其轨道点分布不均匀, 导致落在区间两端的点要比区间内部的点更多. 为了纠正这一问题, 充分发挥Logistic混沌变量的遍历性, 文献[14]提出了式(14)所示的幂函数载波技术:

其中, 0 ＜a＜b＜1, 0 ＜p＜1, q ＞1, zn为式(13)产生的混沌变量, zn′为载波后的混沌变量. 通过幂函数载波,靠近区间左边的点会右移, 靠近区间右边的点会左移,从而使得载波后的点分布更加均匀, 遍历性更好, 图2展示了这一点. 本文取a =0.15, b =0.96, p=0.46, q =13.6.

图2 幂函数载波前后Logistic映射的遍历性

2.2.2 基于幂函数载波的初始化方法

本文对变量 xik和ukj进行实数编码, 组成一个乌鸦个体. 对于备选运力ukj, 直接使用式(15)进行初始化.

对于固定运力 xik, 由于其受到了一架全货机只能飞行一条航线的限制, 因此, 可以先对0-1变量 yik进行初始化, 使其满足约束(5), 然后再根据 yik的值对 xik进行赋值, 如式(16)所示:

假设全货机数量为n, 航线数量为l, 则对于每只乌鸦, 初始化yik(i=1,2,···,n,k=1,2,···,l)的步骤如下:

Step 1. 赋给式(13)随机初值, 生成n 维的混沌序列seq.

Step 2. 对混沌序列应用式(14), 将其载波成新的序列 s eq′.

Step 3. 将区间[ 0,1] l +1等分, 生成区间编号为0-l.

Step 4. 判断序列 s eq′[i]所在的区间范围, 并置:

由上面4个步骤实现的yik的初始化可以满足约束(5), 然后应用式(16)初始化 xik的值, 应用式(15)初始化ukj的值, 将 xik和ukj组成一个完整的乌鸦个体, 由此生成的乌鸦比随机生成的乌鸦有更大的概率在原约束下的可行域内或更加靠近可行域, 且分布更加均匀. 重复迭代即可生成整个种群.

2.3 改进的位置更新策略

2.3.1 个体最优追随机制

初始生成的乌鸦已经满足了约束(5), 此时得到的个体是较好的, 如果仍然应用式(7)所示的朴素CSA的随机跟随策略更新乌鸦位置, 会导致大量乌鸦在探索新位置时, 远离原约束下的可行域.

假设如下情况: 集散中心共有2架全货机, 当天有2条航线需要飞行. 在初始化种群后, 进入搜索阶段. 仅考虑全货机的调度, 设某两个乌鸦个体初始化情况如式(18)所示, 乌鸦i 跟随乌鸦 j的可能结果如图3所示.可以看到, 跟随后乌鸦i 已经不满足约束(5), 即同一架全货机飞行两条航线, 此时已偏离最优解, 可认为是一次无效跟随.

i j图3 乌鸦 跟随乌鸦 的个体编码

因此, 为了保证乌鸦每次跟踪都能更加靠近最优解, 本文提出了个体最优追随机制, 即在跟踪阶段, 每只乌鸦不再随机跟踪种群中的另一只乌鸦, 而是追随上一代的个体最优位置, 这种调整能够保证乌鸦不断靠近最优解, 并提高算法的收敛速度. 改进后的位置更新策略如式(19)所示.

2.3.2 正余弦优化策略

考虑到固定的参数设置使得朴素CSA的搜索能力受限, 本文引入正余弦算法(sine cosine algorithm,SCA)作为局部优化算子来提高CSA的全局探索和局部开发的能力[15,16]. 位置更新公式如式(20)所示:

其中, R1为控制参数, 决定位置更新的方向, 其计算方法为.R1的大小控制着乌鸦的搜索范围, 随着迭代次数增加, R1逐渐减小, 乌鸦的搜索范围随之减小, 最终收敛在一个最优位置, a为常数, 本文取a=2; R2, R3, R4是 均匀分布的随机数, R2∈[0,2π], 控制位置更新的步长, R3∈[0,2], 控制个体最优位置的影响程度, R4∈[0,1], 控制算法是使用正弦还是余弦操作.

正余弦算法本身具有参数自适应的机制, 能够很好地弥补CSA参数固定的缺点. 在迭代前期, R1较大, 算法探索全局的能力较强, 在迭代后期, R1较小, 算法的局部开发能力较强; 同时R2的随机性也控制着正余弦函数的振幅, 使得同一个方向上的不同区段范围都有可能被搜索到, 以此更好地平衡搜索过程中的全局探索能力和局部开发能力, 并最终收敛于最优解或较满意的解.

2.4 交叉变异机制

改进后的位置更新策略能够大大加快算法的收敛速度, 但却不利于维持搜索过程中种群的多样性, 导致算法易陷入局部最优解. 为了让算法有更大的机会跳出局部最优, 本文受遗传算法启发, 引入了交叉变异机制来提高算法全局寻优的性能.

2.4.1 混合交叉策略

在ACSP-MDC中, 全货机和客机的约束不同, 故本文提出一种混合交叉策略, 将乌鸦个体按全货机和客机分为两段, 分别记为X段和U段, 各自采用不同的交叉策略.

对于X段, 为了保证交叉后的个体满足约束(5),采用如下交叉策略: 将两个父个体的X段按航线数量进行切分, 切分点即为交叉点, 对于每个交叉点, 随机生成 [ 0,1] 之 间均匀分布的随机数r andom , 若random＜Pc(给定概率), 则进行交叉操作.

对于U段, 如果生成的[ 0,1]区 间的随机数random＜Pc, 则采用式(21)进行实数交叉, 更新个体的U段.

Step 1. 在种群中随机选取另一只乌鸦j ;

Step 2. 按照X段的交叉策略进行交叉, 交叉后可得到乌鸦i的X段和两个子X段;

Step 3. 按照U段的交叉策略生成新的U段;

Step 4. 将Step 2和Step 3生成的X段和U段组合起来, 生成3只乌鸦, 应用适应度函数并保留适应度值最小的乌鸦.

混合交叉示意图如图4所示.

图4 混合交叉示例

2.4.2 自适应变异策略

常见的变异操作包括两点交换变异和单点特殊变异, 受本文实际场景的约束, 一架全货机只能飞行一条航线, 交换变异有很大概率会造成不可行解, 故本节采用单点特殊变异, 具体操作如式(22)所示:

为了保持种群的优良性, 对较好的个体减少变异的概率, 对较差的个体增加变异的概率, 本文提出了如下的自适应变异策略.

其中, i为乌鸦按适应度值的大小升序排列后的序号,N 为种群大小, pmin为设定的最小变异概率, pmax为设定的最大变异概率, Pm的 取值范围为( pmin,pmin+pmax).式(23)所示的自适应变异概率是线性递减的, 当个体越优时, Pm越小, 变异的机会小, 有利于优良个体的保留; 当个体较差时, Pm变大, 变异的机会随之增大, 有利于较差个体的进化. 采用自适应变异策略可以在保持种群优良性的同时, 丰富种群的多样性.

2.5 算法总流程

改进乌鸦搜索算法的详细步骤如图5所示.

图5 改进CSA算法流程图

3 问题求解

以某物流公司所拥有的全货机数据和该公司某段时间的物流情况为参考, 设计如表1-表4的测试用例,以验证本文算法的有效性.

表1给出了航线的信息, 表2给出了可供调度的全货机信息, 表3给出对应航线的客机航班信息, 表4给出了7组运输量组合, 每组都给出了不同航线需要运输的货物量的情况.

表1 航线信息

表2 全货机信息

表3 客机航班信息

表4 航线运输量(t)

设置种群数为60, 迭代次数为100, 乌鸦跟踪步长fl 为2, 感知概率 A P 为0.1, 正余弦算子的辅助常数α 为2, 交叉概率 Pc为 0.5, 最大变异概率 pmax为0.5, 最小变异概率 pmin为0.

使用本文改进的CSA算法求解结果如表5所示,其中, 平均值和最优值是运行50次所得到的结果, 最优的调度方案记录为: 航线:飞机编号(载重). 从表中可以看到, 每组算例的调度方案都能满足各自航线的载重需求, 同时, 每组结果的平均值和最优值相差很小,最大的一组W7仅相差了318.96, 表明本文改进的CSA算法具有较好的鲁棒性.

表5 改进CSA算法求解结果

图6展示了朴素CSA, SCA-CSA和改进的CSA三种算法在求解W1-W7时的表现. 从图中可以看出改进的CSA相比于朴素CSA和SCA-CSA具有更好的求解精度, 在面对不同问题时改进的CSA也表现出更好的鲁棒性.

图6 不同算法在不同货物量组合下的最小成本对比

针对W7这组测试用例, 图7展示了3种算法的收敛曲线, 可以看出改进CSA算法的求解精度和收敛速度都优于其他两种算法.

图7 W7测试用例下3种算法的收敛曲线

进一步扩展问题的规模, 表6所示的8个问题分别是对航线, 全货机和客机航班进行一定程度的扩充,并为每条航线随机分配该航线的货物量. 对每个问题都进行50次的测试, 测试结果如表7所示. 从表中可以看出, 本文改进的CSA在求解ACSP-MDC问题时的表现优于朴素的CSA和SCA-CSA.

表6 扩充仿真实例

表7 3种算法结果(适应度值)对比

4 结束语

本文针对邮件集散中心航空运力调度问题, 在航空运力资源充足的情况下, 建立了以最小化运输成本为目标的优化模型. 针对ACSP-MDC的特点, 本文在朴素CSA的基础上, 做了一系列的改进, 包括引入惩罚函数消除部分约束, 扩大乌鸦搜索的可行域, 根据问题的实际场景提出新的位置更新策略, 并引入交叉变异机制, 丰富种群的多样性, 提高全局寻优的性能. 改进后的CSA相较于朴素CSA和SCA-CSA的收敛速度更快, 求解结果更优, 鲁棒性更好, 且能有效地解决邮件集散中心的航空运力调度问题, 为集散中心空运业务降本增效提供合理的解决方案.