韦修喜,魏 超,黄华娟,∗

(1.广西民族大学 人工智能学院,广西 南宁 530006;2.广西民族大学 电子信息学院,广西 南宁 530006)

0 引言

随着我国社会生产力不断发展,城市化水平显著提高,城市规模和数量逐渐扩大,为物流系统快速发展提供了坚实的基础。物流配送中心[1]选址是当前物流系统的核心问题。合理地选择配送中心地址,能够有效地降低配送成本、促使物流系统达到供需平衡、提高物资配送效率和经济收益。因此,对物流配送中心选址问题进行研究具有重要的实际价值。

目前,国内外学者针对采用启发式算法求解物流配送中心的地址问题提出了许多方案。徐小平等人[2]针对物流配送系统的运输效率低、运输成本过高等问题,提出一种改进的蜘蛛猴优化算法,随着问题复杂度逐渐增加算法的稳定性相对降低;孟军等人[3]针对复杂多约束的物流中心选址模型,提出一种改进的飞蛾优化算法,节约了配送中选址所需时间,配送效率提高了30%,但实验数据规模较小,并不能体现算法的有效性;王宁等人[4]针对城市冷链物流运输效率不高、顾客满意度低等问题,提出一种改进的遗传算法,但实验对比算法较少,不能体现算法的竞争力;郝芃斐等人[5]为有效降低物流系统的运输成本,提出了一种改进的灰狼优化算法来优化铁路物流配送中心选址模型,函数优化效果一般;师喜婷等人[6]提出了一种引入扰动因子的狼群优化算法,求解物流中心选址问题的效果较好,随着问题规模地增加算法的稳定性相对减弱;方文婷等人[7]为了求解节能减排的冷链物流配送路径优化问题模型,提出了混合蚁群算法,只是针对小规模配送问题进行了研究;Chi 等人[8]提出一种混合布谷鸟搜索和差分进化的优化算法,实验表明采用该算法求解物流配送中心选址问题的优化效果较好;Hu 等人[9]为提高传统方法解决物流配送中心选址模型的优化效果,提出一种引入混沌映射的改进萤火虫算法;周鲜成等人[10]简要介绍了使用启发式算法求解考虑环境效益和油耗等因素的绿色车辆路径模型;杨转等人[11]针对蜘蛛猴优化算法求解物流配送中心选址模型的优化效果不理想问题,提出了两种改进的蜘蛛猴优化算法,为求解物流配送中心选址问题提供了新的方法。以上研究表明,将启发式算法用于求解物流配送中心选址问题具有重要的研究价值。但是也存在一些需要进一步改进的地方,针对上述存在的不足,本文提出一种改进的鸽群优化算法。

鸽群优化算法(Pigeon-inspired optimization,PIO)是段海滨等人[12]根据鸽群归巢行为提出的一种群体智能优化算法。近年来,该算法在机器人路径规划、无线传感网络、无人机控制、图像增强等领域。PIO 简单易懂,有较强的搜索能力,但PIO 在迭代寻优过程中存在局部寻优能力不足、收敛精度不高等问题。针对鸽群算法的上述缺点引入灰狼算法的捕食特性,提出了一种改进鸽群算法(Wolf pigeon-inspired optimization,WPIO),增强鸽群算法的局部搜索能力、提高算法的寻优精度。最后,通过函数测试实验和物流配送中心选址实验来验证WPIO 的寻优性能。

1 物流配送中心选址问题模型

物流配送中心选址问题表示为:在目标区域内的城市中,选取一些城市作为物流配送中心,为其他需求点(城市)提供物资,使得各配送中心城市到由它负责的需求点的距离与需求量的乘积和最小。为了问题模型的合理性,本文作出如下假设:

1)不考虑物流运输过程中的环境因数;

2)目标区域内,所有的需求点都应该被覆盖在配送范围内;

3)不考虑其他经济费用;

4)每一个需求点的物资只能由配送中心一对一配送资源,且不考虑运输量;

由此可建立目标函数表达式如下所示:

其中:minF表示目标区域内的物流配送中心b到由它负责的需求点位置l的距离与需求量之间乘积和的最小值;L={1,2,…,j}为目标区域内所有需求点的位置集合;hl表示需求点l的物资需求数量;dlb为物流配送中心b到由它负责的需求点的位置l的距离;plb的取值为0 或1,若需求点位置l由物流配送中心b供应需求物资,plb的值为1,否则,plb的值为0;Ml表示由该物流配送中心负责配送物资的需求点集合。物流配送中心选址模型仿真图1所示。

图1 物流配送中心选址图Fig.1 Location map of logistics distribution center

图1 中的b1和b2对应物流配送中心,圆圈表示城市需求点,旁边数字与h代表城市编号和物资需求量,b1到城市l的距离为dlb。

目标函数约束条件如下:

上述约束条件表达式中,cb的取值也为0 或1,当cb取值为1 时,表示位置b被选为物流配送中心;q为该目标区域中的配送中心位置的数量;s为配送中心位置b到由它负责配送的所有需求点l距离的最大值。表达式(2)表示需求点的物流配送中心唯一;表达式(6)表示目标区域内的所有需求点都在物流配送中心点的配送范围内。

2 鸽群优化算法及其改进

2.1 鸽群优化算法

鸽群优化算法在迭代寻优过程的不同阶段,使用的种群位置更新工具不同。当鸽群位置距离目标较远时,鸽群位置更新受到磁场和太阳高度的影响。距离目标较近时,地标算子成为当前鸽群的位置更新工具。鸽群优化算法是跟据鸽群归巢行为习惯提出的,详细内容请参见文献[12],算法设计如下:

设鸽群数量为N,维度为D,鸽群的初始化速度V和位置X如下所示:

X =[x1,x2,…,xN],

V =[v1,v2,…,vN]。

当鸽群使用地图和指南针算子导航时,随着迭代次数的增加,鸽子位置和速度也会随之改变,位置和速度更新公式为

其中:R的取值范围是0 到1 之间,表示地图和指南针算子;t表示当前迭代次数;rand表示取值区间为[0,1]的随机数;xbest为最优适应度值的解,表示鸽群中距离目标最近鸽子的位置。

当迭代次数t大于地图和指南针算子阶段的最大迭代次数T1时,鸽群改用地标算子导航。在此阶段,迭代次数每增加一次,种群数量便缩小为原来的1/2,保留种群中位置好的鸽子。计算出当前鸽群的中心位置作为位置更新的方向,表达式如下所示:

式中,xc表示当前鸽群群的中心位置;f表示求解适应度值的函数,其中f求解最大值和最小值的表达式不一致,当求解最大值问题时,函数表达式为f=f(xt-1);求解最小值问题时,函数表达式为

其中,ε为无穷小值,当迭代次数t超过最大迭代次数T时,鸽群算法寻优结束。

2.2 灰狼优化算法

灰狼优化算法(Grey wolf optimization,GWO)是通过模拟灰狼的群体行为提出的一种群智能优化算法。灰狼作为生物链上的顶级生物,大多喜欢群居生活,这也导致灰狼种群内部的等级制度非常严格[13]。根据灰狼的捕食机制和种群特点,设在维度为D的搜索空间内,种群数量为N;种群最优适应度值的解为狼α,狼β和狼δ分别表示种群适应度值为第二和第三的解,狼ω代表解集合中其他解。

灰狼种群狩猎过程由狼α、狼β和狼δ领导其他灰狼搜寻目标,更新狼群位置。式(13)代表猎物位置与种群个体之间的距离,式(16)为位置更新公式。具体公式如下:

其中,t表示当前迭代次数,Xp(t)表示猎物位置,X(t)表示当前灰狼位置,C表示摇摆因子,A表示移动步长,r1和r2都是[0,1]之间的随机数,a表示移动步长,其值随着迭代次数的增加线性减少。

当狼α、狼β和狼δ能够判断出猎物的潜在位置时,每次更新种群位置之后都保留此次迭代的最优的前三个解,并赋值给狼α、狼β和狼δ,种群位置不断更新至捕获猎物[14]。该捕食过程的数学公式如下:

通过式(17)计算出ω个体与α、β和δ之间的距离,由式(18)获取更新后的种群位置,最后通过式(19)将灰狼向猎物位置方向移动。

2.3 鸽群算法的改进

2.3.1 算法思想

针对PIO 在利用地图指南针算子寻优过程中存在全局搜索能力和局部搜索能力不匹配、容易陷入局部最优值问题,引入GWO 中捕食策略思想[15],提出一种改进鸽群优化算法,能有效地平衡算法的全局搜索能力和局部搜索能力,增强算法的稳定性。

基础鸽群优化算法使用地图和指南针算子更新位置时,算法迭代初期,鸽群位置更新过程中飞行速度对其影响较大,由于其飞行的速度与方向的不确定性,经常导致鸽群寻优陷入局部最优。引入灰狼算法的捕食策略,大致判断出最优值的位置,加强算法的全局搜索能力,弥补由于鸽群飞行的不确定导致的问题,提高算法的收敛速度。

图2 表示鸽群优化算法对当前鸽子速度和位置使用式(7)和式(8)更新之后,进入捕食阶段,以Xv和上次迭代种群中前三个最优鸽子位置Xα、Xβ和Xδ指导其他鸽子进行位置更新,Dα、Dβ和Dδ分别表示其他鸽子靠拢前三个最优位置的移动方向。具体位置移动公式如下:

图2 狼性鸽群位置更新图Fig.2 The updated map of the location of wolf pigeons

2.3.2 算法步骤与流程图

根据上述思想实现狼性鸽群算法的步骤如下所示:

Step 1:初始化种群参数,种群规模为N,最大迭代次数为T等;

Step 2:初始化种群位置,计算种群个体的适应度值并存入矩阵E中,选出前面三个最优个体记为Xα、Xβ和Xδ,得到最优值fbest和最优位置Xbest;

Step 3:根据式(7)和式(8)更新种群的位置和速度,按式(17)和(20)计算种群个体与Xα、Xβ、Xδ和Xv的距离,并依据式(18)、(21)和式(22)更新个体位置;

Step 4:更新种群的适应度值矩阵E、个体位置Xα、Xβ、Xδ和最优值fbest;

Step 5:判断当前迭代次数是否达到临界值。如果迭代次数t大于T1,进入地标算子导航阶段Step 6;否则转至Step 3;

Step 6:根据适应度值对种群位置进行排序,使用式(9)～(12)更新种群位置,优化算法的最优解和最优解的位置;

Step 7:判断当前迭代次数是否大于T,若大于则算法结束,否则跳转至Step 6。

综合上述7 个步骤画出流程图,如图3所示。

图3 WPIO 算法流程Fig.3 WPIO algorithm flow

2.3.3 时间复杂度分析

时间复杂度是评价算法性能的重要指标[16],群体智能优化算法的时间复杂度一般只考虑算法的计算时间复杂度。

设种群规模为N,问题维度为D,地图和指南针算子迭代次数为T1,地标算子迭代次数为T2。PIO 的时间复杂度由种群初始化、地图和指南针算子迭代寻优和地标算子迭代寻优三部分构成。根据PIO 算法特性可知,种群初始化时间复杂度为O(ND),地图和指南针算子迭代时间复杂度为O(T1ND),地标算子迭代的时间复杂度为O(3T2N)。PIO 时间复杂度如下:

O(PIO)=O(ND)+O(T1ND)+O(3T2N),

即WPIO 的时间复杂度为

O(WPIO)=O(ND)+O(2T1ND)+O(3T2N)。

根据上述表达式可得,本文WPIO 的时间复杂度与PIO 的时间复杂度的数量级一致,并未增加其时间复杂度。

3 实验仿真与分析

3.1 实验环境

为了验证WPIO 的先进性和有效性,本文做了两组测试实验。第一组实验:通过比较WPIO、PIO、带有佳点集和差值剔除策略的改进灰狼优化算法(Improved grey wolf optimization,IGWO)[5]、果蝇优化算法(Fruit fly optimization algorithm,FOA)[17]、粒子群算法(Particle swarm optimization,PSO)[18]、GWO、蝴蝶优化算法( Butterfly optimization algorithm,BOA)[19]求解10 个基准函数得到的实验结果,验证WPIO 的性能。为了测试WPIO 算法解决实际工程优化问题的能力,第二组实验:使用WPIO 求解物流配送中心选址问题,对实验结果进行分析。

本文实验使用的电脑操作系统为Windows 10,硬件配置为Intel Core i5-6300HQ CPU @2.30 GHz 和 8.0GB RAM 的计算机,利用MATLAB 2020a 平台进行仿真实验。

3.2 实验与结果分析

3.2.1 基准测试函数实验与结果分析

本文为了有效验证改进鸽群优化算法的寻优能力,选取如表1所示最优值都为0 的测试函数,其中f1～f5为高维单峰函数,f6～f10为高维多峰函数,表1 为基础测试函数信息表。为了实验的合理性,实验规定所有算法的种群规模为50,测试函数的问题维度为30,算法总迭代次数为300,对比算法的详细参数见表2。

表1 函数表Tab.1 Function table

表2 算法参数设置Tab.2 Algorithm parameter settings

表3 为高维单峰函数测试结果表,表4 为高维多峰函数测试结果表,两表中的数据都是各算法独立运行30 次得到结果,根据实验数据评价算法的寻优能力和稳定性。根据表3 中的实验数据可知,在高维度单模函数求解中,WPIO 迭代30 次寻优得到的最优值、最差值、方差和平均值都优于表3 中对比算法求解函数对应的数值。由此可见,WPIO 求解高维度单模函数的寻优能力和寻优精度都非常优异。当然,WPIO 的寻优时间比PIO的寻优时间更久,但获得的求解精度却是几十倍的提高,寻优率达到了100%。综上所述,WPIO 与对比算法相比,求解高维度单模函数的寻优性能好,稳定性强。

表3 高维单峰函数结果Tab.3 High-dimensional unimodal function results

从表4 中可得,WPIO 针对实验中的大部分高维多模测试函数都能搜索到全局最优值,但测试函数f8除外,WPIO 求解该函数虽未得到全局最优解,但其搜索得到的最优值精度和和其他实验数据均优于其他对比算法。由此可以得出,与其他算法相比,WPIO 求解高维多模函数的寻优精度和速度更优。

表4 高维多峰函数结果Tab.4 Results of high-dimensional multimodal functions

为了更加直观地了解WPIO 与其他对比算法在寻优过程中最优值的变化情况,图4 展示了算法随着迭代次数的增加函数适应度值的变化曲线图和箱线图,分别随机选取了f1、f7、f9的适应度曲线图和f4、f6、f10的箱线图进行分析。从图4(a)～(c)可得,本文改进的WPIO 在寻优早期就已经达到了最优值0,由于对0 取对数无意义,所以适应度值曲线中断。将WPIO 适应度值迭代曲线与PIO、GWO 和IGWO 相比较,可以得出改进后的鸽群优化算法的寻优性能得到了很大的提升;与剩余其他的群智能算法适应度值迭代曲线相比,WPIO 的收敛速度和精度都非常出色,体现了WPIO 改进的有效性。根据图4(d)～(f)可以得出WPIO 与其他对比算法相比,算法寻优结束之后得到的结果更加集中,进一步表现了WPIO 的稳定性强,寻优性能好。

图4 适应度值曲线图与箱线图Fig.4 Fitness value curve and boxplot

3.2.2 物流配送中心选址问题实验与结果分析

为了验证本文提出的WPIO 对求解物流中心选址模型的优化效果,采用PIO、免疫算法(Immune algorithm,IA)[20]、GWO、鲸鱼优化算法(Whale optimization algorithm,WOA)[21]、PSO 作为物流中心选址实验的对比算法。根据文献实验数据的不同,实验可分为4 种不同场景,所以场景中的种群数量都为50,运行次数都为20,实验迭代次数都为300 代,以表明实验的有效性。

场景一:在31 个城市中选取6 个城市作为该区域的物流配送中心,城市位置坐标和物资需求量如表5所示。表6 展示了6 种算法求解31 维物流中心选址问题得到的优化结果;图5 为物流配送中心将物资运输到需求城市的路线图;图6 为算法寻优过程中的曲线变化图。

表5 31 个城市的位置及其需求量Tab.5 Location and demand of 31 cities

表6 31 维物流中心选址结果Tab.6 31-dimensional logistics center site selection results

根据表6 可知,使用WPIO 求解31 个城市的物流中选选址问题,得到的最优值为5.496 4×105,6 个配送中心的城市编号为5,9,12,17,20,27,对应的城市坐标分别为(3 757,1 187)、(4 312,790)、(2 562,1 756)、(3 918,2 179)、(3 676,2 578)、(2 935,3 240)。具体的配送方案为:城市编号为2、4、6、7、16、23 的需求点由5 号配送中心城市供应物资;城市编号为8 和10 的需求点由9号配送中心城市供应物资;城市编号为1、11、13、14、15、29 的需求点由12 号配送中心城市供应物资;城市编号为3、18、19 的需求点由17 号配送中心城市供应物资;城市编号为21、22、24、25 的需求点由20 号配送中心城市供应物资;城市编号为26、28、30、31 的需求点由27 号配送中心城市供应物资,具体配送路线如图5所示。图6 为各算法求解31 维物流中心选址问题的适应度值迭代曲线图。

图5 31 维物流中心选址图Fig.5 31-dimensional logistics center location map

使用IA、GWO、WOA 求解31 个城市的物流中选选址问题,获得的最优值都为5.496 4×105,优化得到的配送中心为5,9,12,17,20,27。PSO 求解此问题的最优值为5.680 5×105,对应的配送中心为:5,9,14,18,25,27。根据图6 可得,所有算法的适应度值曲线在迭代次数达到300 次之前,都趋向于平缓,证明了启发式算法求解物流中选选址问题的可行性。为了进一步验证这一观点,在场景二中使用50 个城市作为实验城市,求解该目标区域的物流配送中心位置和配送路线。

图6 31 维物流中心选址迭代优化图Fig.6 Iterative optimization diagram of location selection of 31-dimensional logistics center

场景二:从50 个城市中选取10 个城市作为该区域的物流系统的配送中心,城市位置坐标和物资需求量如表7所示。表8 为WPIO 和其他5种群体智能优化算法求解50 维物流中心选址问题的结果数据表。图7 与图8 分别为求解50 维物流中心选址图和适应度值曲线图。

表8 50 维物流中心选址结果Tab.8 50-dimensional logistics center site selection results

由表8 可知:WPIO 求解50 维物流中心选址问题得到的最优值为5.642 3×105。从50 个城市中选择10 个编号为2,9,12,13,17,26,36,38,47,48 作为该物流区域的物流配送中心城市,与之对应的城市坐标分别为(4 177,2 244)、(3 791,1 339)、(3 376,1 306)、(3 237,1 764)、(3 258,911)、( 4 196,1 044)、(4 643,404)、(4 153,426)、(2 716,1 924)、(2 061,1 277)。各物流配送中心为其他城市配送所需物资的运输路径如图7所示。

图7 50 维物流中心选址图Fig.7 50-dimensional logistics center location map

根据表8 中各项数值可得,在求解50 维物流流中心选址问题上,WPIO 的各项性能评价数值都比PIO 好,体现了WPIO 改进的有效性;与其他群体智能优化算法相比,WPIO 的最优值和平均值最好;GWO 独立运行20 次获得的最差值与标准差比WPIO 好,WPIO 的稳定性比GWO 弱,但比其他对比算法强。从图8 可知,PIO、IA、WOA、PSO 的适应度值曲线,在算法迭代前期便停止变化,陷入局部最优值;WPIO 与GWO 相比,WPIO 的适应度值曲线在迭代次数为260 时趋向于平稳,得到最优适应度值,体现了WPIO 寻优速度快,表明WPIO 求解50 维物流中心选址问题的可行性。

图8 50 维物流中心选址迭代优化图Fig.8 Iterative optimization diagram of location selection of 50-dimensional logistics center

场景三:从60 个城市中选取9 个城市作为该区域的物流配送中心,城市位置坐标和物资需求量如表9所示。表10 为群体智能优化算法求解60 维物流中心选址问题的结果。

表9 60 个城市的位置及其需求量Tab.9 location and demand of 60 cities

由表10 可得:WPIO 求解60 维物流中心选址问题得到的最优值为9.408 8×105,优化得到的物流配送中心城市编号为7,12,18,30,36,43,48,59,60;与之对应的城市坐标分别为(3 904,1 289)、(3 376,1 306)、(3 814,261)、(4 252,882)、(4 643,404)、(3 054,1 710)、(2 061,1 277)、(278,890)、(1 064,284),具体配送路径如图9所示。

图9 60 维物流中心选址图Fig.9 60-dimensional logistics center location map

表10 60 维物流中心选址结果Tab.10 60-dimensional logistics center site selection results

WPIO 求解60 维物流中心选址问题得到的最优值、最差值、平均值都比其他5 种对比算法得到的结果更优,各算法迭代300 次的适应度值曲线如图10所示。通过分析标准差可得:WPIO 与IA、GWO、WOA、PSO 求解60 维物流中心选址问题,独立运行20 得到的最优值结果集,WPIO 结果集的离散度相对较高,说明WPIO 的稳定性还需进一步加强。根据文献[11]可得CMASMO 求解该问题,得到的最优值为9.611 3×105,比WPIO优化得到的最优值高了2.025×104,证明WPIO 出色的竞争优势。

图10 60 维物流中心选址迭代优化图Fig.10 Iterative optimization diagram of 60-dimensional logistics center location selection

综合分析上述3 个场景的实验结果可得:随着物流配送中心地址问题维度逐渐增加,WPIO 求解此类问题得到的优化效果也变得更好,由此可以做出推论:WPIO 更适合求解高维复杂问题。为了验证这一猜想,在场景四中将物流配送中心选址问题的维度设置为100,分析WPIO 的实验结果。

场景四:收集100 中国城市的位置坐标,从中选取21 个物流配送中心城市,考虑到篇幅有限,城市位置坐标和需求量参见文献[11]。表11 为WPIO 和其他5 种群体智能优化算法求解100 维物流中心选址问题的结果数据表,图11 与图12分别为求解100 维物流中心选址图和适应度值迭代曲线图。

表11 100 维物流中心选址结果Tab.11 100-dimensional logistics center site selection result

根据表11 可知:当物流配送中心选址问题维度为100 的时候,WPIO 求解该问题得到的最优值为:9.978×105,21 个物流配送中心城市编号为:1,2,3,7,14,16,21,29,33,37,40,47,55,63,74,75,80,86,89,96,98,配送中心城市坐标为:(3 688,1 818)、(4 016,1 715)、(4 181,1 574)、(3 918,2 179)、(4 201,2 397)、(3 766,2 364)、(3 594,2 900)、(3 862,2 839)、(4 186,3 037)、(3 334,2 107)、(3 587,2 417)、(3 394,2 643)、(3 526,3 263)、(3 140,3 557)、(2 801,2 700)、(2 126,2 896)、(1 084,2 313)、(1 478,267)、(278,890)、(2 061,1 277)、(2 751,1 559)。物流配送信息参见图11。

图11 100 维物流中心选址优化图Fig.11 100-dimensional logistics center location map

与其他智能优化算法相比,WPIO 求解100 维物流中心选址问题得到的各项评价指标都是最优,随着问题维度逐渐增加,WPIO 的鲁棒性得到了很大地改善,证明了WPIO 更适合求解高维复杂问题。由图12 可直观地了解WPIO 在求解100维物流中心选址问题收敛速度快、收敛精度高,说明了WPIO 合理地平衡了算法寻优过程中收敛速度和收敛精度。根据文献[11]得,CMASMO 在求解100 维物流中心选址问题中,算法独立运行50次,得到最优值为1.055 8×106,与WPIO 相比最优值精度少了5.8×104,进一步说明了WPIO 的竞争力强。

图12 100 维物流中心选址迭代图Fig.12 100-dimensional logistics center location map

4 结束语

针对鸽群算法求解物流配送中心选址问题时,存在效果不理想的缺陷,本文提出了一种加入捕食策略的鸽群优化算法。该算法在鸽群算法的基础上引入灰狼捕食策略,弥补基础鸽群算法局部搜索能力不足的缺点,提高算法的寻优能性能。基础函数测试实验表明,WPIO 的收敛精度高和稳定性强。使用WPIO 求解四种不同维度的物流配送中心选址问题,通过实验分析得出:物流中心选址问题的维度越高,使用WPIO 求解得到的优化效果越好,说明WPIO 更适合求解高维复杂问题。未来计划将WPIO 应用到移动机器人路径规划、电力调度和图像识别等领域中,进一步验证WPIO算法的适用性。