基于改进正余双弦算法的电商物流配送路径规划

王芸博

(太原城市职业技术学院 信息工程系，山西 太原 030027)

0 引言

随着计算机和网络的迅速发展,我国实体销售逐渐向网络销售进行转型,越来越多的人更习惯于网络购物。对于电商企业而言,由于网络销售具有购买群体分散、交易延时且一次性发货量较大的特点,因此对于企业下的物流配送要求较为严格,如何降低物流配送成本,成为电商企业提高效益的重要指标之一[1]。物流配送过程中,运输费用约占配送成本的70%.合理规划配送路径,减少配送车辆,降低运输费用是节约配送成本的有效途径[2]。针对上述配送路径规划问题,主要的方法是通过智能算法对配送路径进行求解。

Mohammed等提出一种基于改进遗传算法的物流配送路径规划策略,有效缩短了配送距离,节约了配送成本,但算法优化时间较长,且在优化过程中易早熟收敛,降低了搜索精度[3]。尚猛等提出一种改进鲨鱼算法的配送优化策略,通过正弦机制和高斯变异对算法进行改进,提高了算法的收敛精度,降低了配送成本,缩短了配送时间[4]。刘晓珍等通过定向变异策略对布谷鸟算法进行改进,通过城市间的距离寻找相邻城市,缩短配送路径,但算法搜索时间较长,不易找到最优解[5]。吴征等建立了模糊配送模型,通过改进的混合算法对模型进行求解,缩短了配送里程,降低了配送成本[6]。马艳芳等提出一种基于改进惯性权重的粒子群算法对配送模型进行求解,通过自适应调整惯性权重平衡算法的全局搜索能力和局部搜索能力,提高了算法的收敛精度,节约了配送时间,提高了配送效率[7]。

上述优化策略均在一定程度上降低了配送成本,但均存在算法早熟收敛、收敛精度不高的问题,这是由于算法没有针对全局搜索能力和局部搜索能力进行平衡导致。因此本文提出一种改进的正余双弦优化算法[8],对配送路径进行优化。通过精英搜索策略和自适应区域搜索算子策略,提高算法的收敛精度,平衡算法的全局搜索能力和局部搜索能力。

1 物流配送路径规划模型

设某电商配送中心个数为M,待配送点个数(即购买货品用户个数)为P。如何合理地将M个配送中心的货物发送到P个待配送点,使得配送距离最小、车辆花费最少、配送时间最短是电商物流配送路径优化的主要问题。因此在建立电商物流配送路径规划模型时,应建立以下几方面的约束:

1)设配送路径上全部车辆的最大承载量均为Cn,同时要求在每一个配送路径上,待配送客户的需求量总和不能超过该配送路径上配送车辆的最大承载量,此约束条件的数学模型如下:

(1)

式中,N为配送车辆个数,qi为第i个客户的购货量,ai,n为判定参数。若ai,n为1,则认为第i个客户的货物由第n辆车进行配送,否则为0.

2)设任意一条配送路径上的全部待配送客户中,其中任意一个客户所购买的全部物品均只能由一辆配送车进行配送,不允许多个配送车对一个客户的物品进行分批配送。此约束条件的数学模型如下:

(2)

3)设任意一条配送路径上,配送车辆只能对同一个客户进行一次配送,即不能多次对同一个客户进行配送。此约束条件的数学模型如下:

(3)

式中,bijn为车辆路径重复行驶控制参数。若bijn为1,则表示第n辆车从第i个客户配送完成后向第j个客户开始配送，否则为0.

根据约束(1)、约束(2)和约束(3),构建电商物流配送路径规划的目标函数为:

(4)

式中,sij为配送车辆从第i个客户到第j个客户所需的配送成本。

2 改进的正余双弦优化算法

2.1 基本正余双弦优化算法

正余双弦优化算法(sine cosine algorithm, SCA)是一类基于数学特征的元启发智能优化算法,算法简单易于实现。设SCA算法的种群规模为NP,维数为D,最大迭代次数为Tmax。因此算法中个体位置更新公式如下所示:

(5)

从式(5)中可知,区域搜索算子R1用于控制正弦全局搜索区域和余弦局部搜索区域的范围,其数学表达式如式(6)所示。R1在迭代前期较大,算法可以大范围进行全局搜索,使得算法在迭代前期尽可能将全局最优解包含在搜索范围内。R1在迭代过程中线性减小,使得算法在迭代后期的搜索范围较小,有利于算法在当前极值点附近进行精确搜索。α为常数，取值为2。

(6)

R2作为移动控制因子,控制个体远离或靠近目标。R3为最优位置权重系数,当R3≥1时,加大最优解对当前个体的吸引力,当R3<1时,则减小最优解对当前个体的吸引力。R4控制正弦全局搜索和余弦局部搜索的概率。

2.2 精英搜索

(7)

式中,N(μ,δ2)为正态分布概率密度函数,其计算方式如下所示:

(8)

2.3 自适应区域搜索算子

由式(5)中区域搜索算子R1可知,种群中每个个体均依照区域搜索算子R1线性改变搜索步长和搜索范围,虽然在一定程度上,对算法的全局搜索能力和局部开发能力进行了平衡处理,但线性递减的规律并不符合优化的过程。在优化过程中,种群中每个个体在进行全局搜索和局部搜索转换的时间并不应该是完全相同的。适应度值较优的个体应尽快减小搜索范围,使得较优个体可以小范围进行精确搜索,提高收敛精度,加快搜索时间。适应度值较差的个体,应继续进行大范围的搜索,使得较差个体可以向全局最优解不断靠拢,提高算法的全局搜索能力,同时也防止算法早熟收敛陷入局部最优。针对上述问题,本文引入一种以适应度值为基准的自适应惯性权重,对算法的区域搜索算子R1进行改进。改进后的区域搜索算子R1-new如下所示:

(9)

式中,fitnessmin(t)和fitnessmax(t)为当前迭代中,全部个体中计算所得的最小适应度值和最大适应度值,fitnessi(t)表示第i个个体在第t次迭代时计算所得适应度值。R1-new的取值范围在[0,1]之间。改进后的个体位置更新公式如下所示:

(10)

改进后的正余双弦算法的优化步骤如下所示:

1)种群初始化,其中种群规模为NP,维数为D,最大迭代次数为Tmax;

2)计算种群中的全部个体的适应度函数值,并记录最优值Pbest,适应度最大值fitnessmax和最小值fitnessmin;

3)根据式(9)计算种群中全部个体对所对应的区域搜索算子R1-new,并通过式(10)对个体进行位置更新;

4)计算位置更新后的全部个体的适应度函数值,并记录最优值Pbest;

5)根据精英策略对最优解Pbest进行正态变异,并将所得结果Pnewbest与Pbest进行精英选择;

6)判断是否达到最大迭代次数,若是则输出当前最优解，否则返回第2步。

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

为了验证本文所提改进正余双弦算法(Improved sine cosine algorithm, ISCA)的算法性能,本文选择8个基准测试函数F对ISCA算法进行数值仿真实验,对算法的收敛精度和稳定性进行验证。8个测试函数如表1所示。其中F1—F5为单峰测试函数,用于验证ISCA算法的局部开发能力,F6—F8为多峰测试函数,用于验证ISCA算法的全局搜索能力。为了说明实验结果的有效性,本文将实验结果与自适应动态鸡群算法 (ADLCSO)[9]和改进粒子群算法(IPSO)[10]的实验结果进行对比验证。为保证对比结果的公平性,三种算法的种群规模均为100,迭代次数均为200.三种算法独立运行50次,取得实验结果的最小值、平均值和标准差。实验结果如表2所示。

表1 测试函数Table1 Test function

从表2可知,对于单峰测试函数F1—F5而言,本文所提ISCA算法求解的最小值和平均值最小,说明相较自适应动态鸡群算法和改进粒子群算法而言,ISCA的局部搜索能力较强,这是由于加入精英搜索后,种群中的劣质个体均被最优个体所替代,使得种群中全部个体的质量较高,有利于局部搜索。同时,ISCA算法求解的标准差同样最小,说明ISCA算法的寻优稳定性更强,不易陷入局部最优早熟收敛。

表2 测试函数测试结果Table 2 Results of test functions

对于多峰测试函数而言,ISCA算法求解的最小值和平均值同样最小,说明ISCA算法的全局搜索能力要优于自适应动态鸡群算法和改进粒子群算法。同时也说明改进后的区域搜索算子R1-new可以更加平衡算法的全局搜索能力和局部开发能力,使得适应度值较差的个体可以充分地进行全局搜索,向全局极值点靠近。适应度值较优的个体,也可以在全局极值点附近进行快速的精确搜索,提高开发能力。总体而言,通过精英策略和自适应区域搜索算子改进后的正余双弦算法,全局搜索能力和局部开发能力得到了有效的平衡,同时也提高了算法的收敛精度和整体寻优性能。

3 仿真

某电商以A城市为物流配送中心,对31个城市进行货品配送。其中包含配送中心A城市在内的32个城市的坐标以及31个配送城市的货品需求量如表3所示,配送中心A城市的序号设为0。

表3 32个城市的基本信息Table 3 Basic information of thirty-two cities

本文通过改进的正余双弦算法对电商物流配送路径进行优化,并将实验结果与自适应动态鸡群算法和改进粒子群算法的优化结果进行对比。实验结果如表4—表6以及图1—图3所示。在模型中,设配送车辆个数为5,其中车辆1的最大行驶里程和最大承载量分别为200 km和100 kg。车辆2,3,4,5的最大行驶里程和最大承载量均为2 000 km和100 kg。其中每1 km的物品配送10 kg的价格为1元。

表4 改进正余双弦算法的优化结果Table 4 The optimization results of the improved sine cosine algorithm for sequential quadratic programming

表5 自适应动态鸡群算法的优化结果Table 5 Optimization results of adaptive dynamic chicken colony algorithm

表6 改进粒子群算法的优化结果Table 6 Optimization results of improved particle swarm optimization

图1 改进正余双弦算法的配送路径Fig.1 The distribution path of improved sine cosine algorithm in sequential quadratic programming

图2 自适应动态鸡群算法的配送路径Fig.2 Distribution path of adaptive dynamic chicken colony algorithm

图3 改进粒子群算法的配送路径Fig.3 Distribution path of improved particle swarm optimization

从表4—表6及图1—图3可知,本文所提改进正余双弦算法相较自适应动态鸡群算法和改进粒子群算法而言,配送路程节省了7.18 km和37.16 km，总配送金额节约了294.30元和1 523.56元。很大程度上缩短了配送路径，节约了配送成本，有效提高了电商企业的效益。

4 结论

本文针对电商物流配送路径优化问题,提出一种改进正余双弦优化算法的优化策略。同时针对传统正余双弦算法收敛精度低的问题,通过精英策略和自适应区域搜索算子策略进行改进,有效平衡了算法的全局搜索能力和局部开发能力,提高了算法的收敛精度和整体寻优能力。最后，通过改进后的正余双弦算法对电商物流配送模型进行优化求解。实验结果表明,通过改进正余双弦算法优化后的配送路径,节约了配送成本,缩短了配送路程，提高了配送效率。