基于改进猴群优化算法的物流配送中心选址研究

李茂林

(运城职业技术学院 电子信息工程系,山西 运城 044000)

0 引言

随着物联网的迅速兴起,物流配送产业也得到了迅猛的发展。物流配送系统主要分为物流配送中心选址和物流配送路径规划两个部分,其中起决策作用的是配送中心选址的优化问题[1]。物流配送中心选址模型优化主要指从若干个供应点和若干个需求点中,选择出几个最优点作为配送中心,使得配送路径最合理,配送成本更低。因此,物流配送中心选址模型具有非线性和多约束性,是典型的NP-Hard问题[2]。针对物流配送中心选址模型优化问题,许多国内外的学者对该问题进行了深入研究。

袁群等人提出一种改进遗传算法的冷链物流配送中心选址优化策略[3],通过贪婪算子对算法进行改进,提高了物流配送效率。尚猛等人提出一种改进鲸鱼优化算法的选址优化策略[4],通过随机正弦控制因子策略提高了算法的全局收敛能力,很大程度降低了配送时间和配送成本。范荣华提出一种基于直觉模糊数的物流配送中心选址策略[5],建立了新的评价标准,降低了配送成本和配送风险。谷淑娟等人提出一种多尺度网格配送方法,通过区域离散的方式选择配送中心[6]。此外,还有重心法[7]、改进蚁群算法[8]、改进粒子群算法[9]以及改进烟花算法[10]。以上物流配送中心选址优化策略均在一定程度上降低了配送成本,节约配送时间,但单一机制的优化算法难以针对具有多个配送点和需求点的配送中心选址模型进行优化,因此本文提出一种改进猴群优化算法的优化策略。

猴群优化算法是一种新的群智能优化算法[11],算法具有调整参数少,结构简单易实现的优点,但算法全局收敛精度较低,在迭代后期易早熟收敛陷入局部最优。本文针对上述问题通过引入lateral变异和非线性调节因子对算法进行改进,并将改进后的算法用于物流配送中心选址模型优化。

1 物流配送中心选址模型

物流配送中心选址优化问题是指在多个供应点中选取M个供应点作为配送中心,使得从配送中心出发的配送车辆可以很快地送到配送中心附近的配送点,从而节约配送时间,降低配送成本。因此,在建立物流配送中心选址模型时,应考虑以下几方面的假设。

1)假设任意一个配送点的需求量应小于或等于其匹配的配送中心的货物总量,此假设可用以下数学式表示:

(1)

式中,M为所选出的全部配送中心地址;ψi,j为第i个配送点的需求量。

2)假设所有配送点所需配送货物均应从距其最近的配送中心发货。此假设可用以下数学式表示:

(2)

式中,Zi,j为0或1,当Zi,j=1时,表示配送点i的货物由配送中心供应。

3)假设无配送中心的点没有客户:

Zi,j≤hjj=1,2,…,N

(3)

式中,hj为0或1,当hj=1时,则将第j个供应点选为配送中心,Fj为第j个配送中心的建设费用。

4)假设有P个物流配送中心:

(4)

5)假设,任意一个配送点都应在与其匹配的配送中心可送范围之内:

di,j≤t

(5)

式中,di,j为第i个配送点和与其距离最短的第j个配送中心之间的距离。

因此基于上述假设,定义带多约束条件的物流配送中心选址模型的目标函数为:

(6)

2 猴群优化算法的改进策略

2.1 基本猴群优化算法 (Monkey Optimization Algorithm, MOA)

针对具有数据量大,复杂度高以及多约束条件特性的数学模型,猴群优化算法有着很好的优化效果,其求解过程包含爬、望、跳三个阶段。首先设猴群优化算法的种群规模为NP,解空间维度为D,因此猴群优化算法的种群初始化过程为:

Xi=(xi,1,xi,2,…,xi,D)

(7)

式中,i=1,2,…,NP,xi表示每个粒子在解空间的初始位置。

其次,猴群优化算法在求解过程中,种群中所有粒子会逐渐向全局极值靠拢,并在迭代过程中不断更新自己的位置,直到找到目标函数最小解为止,这种位置更新过程被描述为爬过程,其数学表达式如下所示:

(8)

(9)

再次,猴群优化算法在迭代过程中,当粒子取得局部最优解的同时,粒子会搜索局部极值附近是否存在比当前更好的解,如果存在,则向更好的解靠拢,否则粒子停留在局部极值点的位置。这种行为被描述为望过程,其过程如下所示:

1)在当前局部极值点附近(xi,j-β,xi,j+β),随机选取相邻点,并计算相邻点的位置yi′。

2)计算局部极值点的适应度值和相邻点的适应度值,并进行比较。若局部极值点的适应度值优于相邻点的适应度值,则粒子停留在局部极值点位置不变,否则粒子向相邻点靠拢。

最后,为了在算法寻优过程中,将当前区域移动到新的搜索区域当中,选择所有粒子的重心位置作为支点,每个粒子均沿当前位置指向支点的方向进行移动搜索,这个过程被描述为跳过程,其数学表达式如下所示:

yi=xi,j+θ(pi,j-xi,j)

(10)

式中：θ为[0,1]之间的随机数；pj为支点,可表示为:

(11)

2.2 改进的猴群优化算法(Improved Monkey Optimization Algorithm, IMOA)

首先,根据大量的数值实验表明,整体收敛精度较高的算法在迭代前期,应获得较高的惯性权重或控制因子,使得算法具有较强的全局搜索能力和搜索范围,保证全局极值点在搜索范围内。在算法迭代后期,惯性权重或控制因子应迅速减小,保证算法可以获得较强的局部搜索能力,有助于粒子在小范围内的精确寻优。在传统猴群优化算法中,α为搜索步长,同时也是控制因子,负责调整算法全局搜索能力和局部搜索能力的大小,但传统猴群算法中,α的取值随迭代次数的增加线性减小,而算法全局搜索能力和局部搜索能力之间的平衡呈非线性,α线性减小难以平衡算法的全局勘探能力和局部开发能力。因此,本文引入非线性调节因子对爬过程进行改进,非线性调节因子δ的数学表达式如下所示:

(12)

式中,Tmax为最大迭代次数,t为当前迭代次数,λ和ω为调节系数。经大量实验验证,当λ=3.75ω=0.01时,算法收敛精度最高。τ为位移量,当τ=0.64时,算法取得结果最优。sinh(·)为双曲正弦函数,由双曲正弦函数特性可知,δ随迭代次数的增加,非线性减小,在算法迭代初期,减小速率较慢,使得算法具有较强的全局收敛能力。在算法迭代后期,δ值迅速降低,使得算法具有较强的局部开发能力,使得粒子的搜索精度更高,同时保证粒子可以在全局极值附迅速收敛,提高算法的收敛速度。因此可将式(8)改为:

(13)

其次,通过算法寻优过程中的望过程可知,β的值越小,随机生成领域点的范围越小,使得粒子在迭代过程中易陷入局部最优,早熟收敛。β的值越大,随机生成领域点的范围越大,使得算法在迭代后期寻优速度缓慢,甚至停滞,依然会导致算法早熟收敛,陷入局部最优。因此,为了避免由β取值不合理,导致算法出现早熟收敛的现象,本文引入lateral变异对算法进行改进,其中lateral变异的数学表达式如下所示:

xi,j=(1-η)xi,j+ηxk,j

(14)

式中,xi,j为当前最优个体,xk,j为种群中的随机个体且k≠i;η为学习率,在[0,1]之间服从均匀分布。lateral变异主要是通过xk,j个体的信息特征来指导当前xi,j的搜索机制,可更有效地利用种群的环境信息,在算法陷入局部最优时给予适当大小的扰动,帮助粒子跳出局部最优,并提高算法的收敛速度。

改进的猴群优化算法的寻优步骤如下所述。

Step1:初始化猴群的种群规模NP=100,维数D=50,最大迭代次数Tmax=100,λ=3.75,ω=0.01,τ=0.64;

Step2:对种群中所有粒子的位置进行初始化,计算全部个体的适应度值,并将粒子按适应度值大小进行排序。找出适应度值最小的个体作为当前最优解;

Step3:依照式(13)计算当前猴群粒子的位置;

Step4:依照望过程更新当前猴群粒子的位置;

Step5:依照式(14)对当前粒子进行lateral变异操作,对更新后的粒子进行边界处理;

Step6:依照式(10)更新当前猴群粒子的位置;

Step7:判断是否达到最大迭代次数,若达到最大迭代次数,则输出全局最优解,否则返回Step3。

2.3 基于测试函数的性能测试

为了验证本文所提改进猴群算法(IMOA)的收敛精度,选取8个基准测试函数作为目标函数,对IMOA进行数值实验,并将实验结果与改进鲸鱼优化算法(IWOA)、改进粒子群算法(DPSO)以及改进蚁群算法(ICOA)的数值实验结果相对比,记录四种算法求解所得平均值和标准差。为了保证对比实验的公平性,四种算法种群规模均为100,维度均为50,最大迭代次数均为100,其他参数设置详见文献[4]、文献[8]以及文献[9]。测试函数如表1所示。其中f1～f4为单峰测试函数。f5～f8为多峰测试函数。具体实验结果如表2所示,其中最优解用加粗字体表示。

表1 测试函数Table 1 Test function

表2 12个测试函数测试结果Table 2 Test results of 12 test functions

从表2中可知,首先,对于测试函数f1～f4而言,四种算法均可以找到全局极值点,说明四种算法的整体性能较高。但本文所提IMOA算法相较其他三种算法而言,取得平均值更小,说明IMOA算法具有更高的局部收敛精度,在迭代后期,可以迅速向全局最优解靠拢,收敛速度更快。值得注意的是,对于测试函数f1而言,本文所提IMOA可以求解到理论最优值,说明IMOA算法很大程度地减小了算法陷入局部最优的概率。此外,IMOA算法可以取得更小的标准差,说明IMOA算法相较其他三种算法而言,算法局部搜索的稳定性更高,鲁棒性更强,对于处理复杂度较高的优化问题具有很好的收敛精度。

其次,对于多峰测试函数f5～f8而言,IMOA求解的平均值同样远小于其他三种算法,验证了IMOA算法在寻优初期具有较高的全局搜索范围,算法的全局收敛能力要优于其他三种算法,搜索成功率也大于其他三种算法。同样,对比四种算法的标准差,IMOA求解结果远小于其他三种算法,说明IMOA算法的全局寻优稳定性优于其他三种算法。由此可得,IMOA算法的全局收敛精度远优于其他三种算法的全局收敛精度。

最后,利用Wilcoxon秩和检验分析IMOA、DPSO、ICOA和IWOA四种算法的性能差异性。在(D=50)时,在选定5%的显著性水平下,以IMOA算法为基准,DPSO算法、ICOA算法和IWOA算法所得的pvalue分别为0.02741、0.04873和0.04209。

总体而言,IMOA算法很好地平衡了算法的全局收敛能力和局部搜索能力,对于求解复杂的较高的测试函数时,具有较高的收敛精度和收敛速度,可以用于求解物流配送中心选址模型。

3 仿真实验及分析

为了验证本文所提IMOA算法的优化性能,本文获取30个需要配送货品的城市地理位置信息,选取式(6)为目标函数,建立物流配送中心选址数学模型,并将IMOA算法对模型进行优化。本文实验平台为MATLAB2014a,实验所用硬件配置为Intel Core i5 2.70 GHz 8.00 GB运行内存的处理器。操作系统为Win10操作系统。30个配送城市的地理位置和货物量如表3所示。

表3 30个配送城市地理位置Table 3 Geographical location of 30 distribution cities

为了可以更加直观地表明IMOA算法具有较高的收敛精度,本文将IMOA算法的优化结果与IWOA算法的优化结果和ICOA算法的优化结果相对比,三种算法的设置参数与数值实验中参数设置相同。具体实验结果如图1～图3和表4所示。

图1 基于IMOA算法的物流配送中心选址Fig.1 Location of logistics distribution center based on IMOA algorithm

图2 基于IWOA算法的物流配送中心选址Fig.2 Location of logistics distribution center based on IWOA algorithm

图3 基于ICOA算法的物流配送中心选址Fig.3 Location of logistics distribution center based on ICOA algorithm

表4 三种算法的选址性能比较Table 4 Comparison of location performance of three algorithms

在实验前应对三种算法进行二进制编码处理。将30个城市的编码随机设定成0或1,当其中任意一个城市被选中为配送中心时,该城市编码为1,否则该城市编码为0。假设在10个城市中选择第1个、第4个和第8个城市作为配送中心,则该编码为X=(1,0,0,1,0,0,0,1,0,0)。

图1～图3分别为基于IMOA算法的优化策略、基于IWOA算法的优化策略以及基于ICOA算法的优化策略所求解的平均适应度值和最小适应度值。从图中可知,本文所提基于IMOA算法的优化策略相较其他两种优化算法的优化结果,可以求解到更小的平均值和最小适应度值,说明基于IMOA算法的优化结果更加精确,搜索精度更高。

从表4可得,经IMOA算法优化后的物流配送中心选址模型,较大程度地降低了物流配送费用,同时可以更快地得到最优解。值得注意的是,IMOA算法相较其他两种算法迭代次数明显更小,说明IMOA算法具有较为平衡的全局收敛能力和局部搜索能力,搜索精度更高。总体而言,IMOA算法较其他两种算法,优化速度更快，可以更加精确地选取物流配送中心地址。

4 结论

本文针对物流配送中心选址模型难以优化的问题,提出一种改进的猴群优化算法对模型进行求解。首先针对猴群算法收敛精度低,易早熟收敛陷入局部最优的问题,通过非线性调节因子和lateral变异对算法进行改进,提高了算法的收敛精度和收敛速度,平衡了算法的全局搜索能力和局部开发能力,提高了算法跳出局部最优的概率。其次通过数值对比实验,验证了本文所提IMOA算法整体收敛性能更强,具有较高的收敛精度。最后,将IMOA算法对物流配送中心选址模型进行优化,并将实验结果与IWOA算法的优化结果和ICOA算法的优化结果相对比,结果表明,IMOA算法可以更快求解到最优值,很大程度降低了物流配送花费,提高了配送效率,降低了配送成本。