混合自适应布谷鸟算法的物流配送路径优化

字号：T|T

文章出处：作者：人气：-发表时间：2024-06-24 09:13:00

1 引言

在城市物流中，通常有多个仓库和多个配送点共同配送货物，以满足不同用户的实际需求。从空间角度而言，物流配送优化问题由区域划分和路径优化两个子问题组成。在实际应用过程中，由于现有方法没有考虑到交通限制和各个仓库之间的相互协作问题，导致最终得到的物流配送方案和真实情况存在偏差，因此还需要进一步优化。

针对上述问题，相关专家针对物流配送路径优化问题[1,2]展开了大量研究，例如蒋俊等人[3]利用强化学习的基本思想选择2A算法解决物流配送路径优化问题，获取最佳物流配送方案。葛显龙等人[4]以总成本最低为目标函数组建数学模型，通过改进遗传算法对模型求解，实现配送路径优化处理。谭晓伟等人[5]以最低配送总成本以及最优客户满意度为目标函数，组建物流配送模型，同时通过自适应大邻域搜索算法对模型求解，确定最佳物流配送方案。在以上几种算法的基础上，提出一种多仓库多配送点物流配送路径优化算法。仿真实验结果表明，所提算法可以有效缩短物流配送距离，降低配送时长，提升整体配送效果。

2 路径优化算法设计

2.1 路径优化模型构建

货物从生产到客户的流动过程是货物配送的核心环节，通过图1给出货物流通的示意图：

图1 货物流通示意图下载原图

供应商或者工厂是物流货物配送的开端，通常由大型运输工具将全部货物配送至区域配送中心，对货物展开收货以及分拣等相关操作，然后通过细分配送需求将货物配送至小区域配送中心存储。根据对配送的范围以及需求来看，多仓库多配送点物流属于“一阶段配，二阶段送”的模式。

多仓库多配送点物流配送路径优化问题包含路径规划和时间调度[6,7]两个方面，因此将最少调用车辆数量和最短配送总距离作为目标函数，下面给出相关约束条件：

1)每个客户必须且只能由一辆汽车展开配送，对应表达式如下：

$Ζ_{a 1} \cap Ζ_{a 2} = ϕ, a_{1} \neq a_{2} (1)$

上式中，Za1和Za2分别代表车辆1和车辆2需要配送的客户集合。

2)各条配送路径的长度不可高于车辆可行驶最大距离，即：

$\sum_{a = 1}^{u_{a}} h_{u_{a}}^{s_{a}} \leq Ι_{a}, u_{a} \neq 0 (2)$

上式中，ua代表车辆a配送的客户总数；sa代表配送车辆a在配送线路中所在的位置；h代表不同客户之间的距离；Ia代表物流配送车辆可行驶最大距离。

3)各条配送路径上的客户需求总量不可高于配送车辆的最大装载量Pc,即：

$\sum_{c = 1}^{u_{a}} z \leq Ρ_{c}, u_{a} \neq 0 (3)$

上式中，z代表客户的货物需求量。

4)最终确定的物流配送路径必须遍历全部的客户，即：

$\underset{a = 1}{\cup} Ζ_{a} = {1, 2, \dots, n} (4)$

上式中，n代表常数。

在确定多仓库多配送点物流配送路径优化[8,9]问题的目标及其约束条件后，构建多仓库多配送点物流配送路径优化模型B,如公式(5)所示：

$B = \sum_{a = 1}^{u_{a}} ϕ Ι_{a} Ρ_{c} Ζ_{a} + m i n f_{c} + m i n l_{i j} (5)$

上式中，fc代表调用车辆数量；lij代表配送车辆行驶总距离。

2.2 路径优化模型求解

针对2.1节构建的路径优化模型，采用混合自适应布谷鸟算法对其进行求解。标准的布谷鸟算法[10,11]10-11]全局搜索能力较强，但是算法的收敛速度较慢且收敛精度相对较低；而粒子群算法的收敛速度较快，但是容易陷入局部最优。为此，可以结合上述两种优化算法的优势，提出一种混合自适应布谷鸟算法，用于路径优化模型求解。

在布谷鸟算法中，搜索目标是通过一个新解或者一个潜在解来替换鸟巢中的劣解。由于算法中发现概率pa以及步长因子αstep两者取值均为常数，不利于算法后期的收敛。所以，需要对上述两个参数展开调整，经过改进后的参数表示为：

${\begin{cases} p_{a} (t) = p_{a m a x} - \frac{B (p_{a m a x} - p_{a m i n})}{Τ} \cdot t \\ α_{s t e p} (t) = α_{\max} - \frac{B (α_{\max} - α_{\min})}{Τ} \cdot t \end{cases} (6)$

上式中，pamax和pamin代表发现概率的最大和最小值；αmax和αmin代表步长因子的最大和最小值；T和t分别代表最大和当前迭代次数。

布谷鸟算法[12,13]12-13]是利用个体的Levy飞行和随机游走展开位置更新，全部群体之间没有任何信息交流，因此，个体优质性还需要进一步提升。个体优质性可以通过适应度展开衡量，所以引入布谷鸟算法适应度权值的概念，通过公式(7)给出第i个布谷鸟个体的适应度权值ωi:

$ω_{i} = | \frac{f_{b e s t} - f_{i}}{f_{w o r s t} - f_{b e s t}} | \times p_{a} (t) α_{\max} (7)$

上式中，fi代表第i个个体的适应度；fbest和fworst代表最优和最差适应度值。

通过上述分析可知，在布谷鸟算法Levy飞行中需要增加群体之间的适应度权值，以此达到加强群体交流的目的，更新公式如下所示：

$ω^{'}_{i} = [r_{1} (\vec{x}_{i}^{t} - \vec{x}_{b e s t}^{t}) + r_{2} (\vec{x}_{i}^{t} - \vec{x}_{j}^{t}) (ω_{i}^{t} - ω_{j}^{t})] - ω_{i} (8)$

上式中，r1和r2代表随机数；ω $_{i}^{t}$ 和ω $_{j}^{t}$ 代表当前迭代下第i个和第j个个体的适应度权值。

粒子群算法[14,15]14-15]的主要优势在于粒子具有扩展搜索空间的能力，解的更新主要是依靠粒子的随机游走。其中，随机游走带有学习因子以及加速系数，可以采用参数调整的方式全面提升收敛速度。

通过上述分析，将粒子群算法和布谷鸟算法有效结合，通过混合机制形成新解 $_{i}^{t + 1}$ 表示为公式(9)的形式：

$\vec{z}_{i}^{t + 1} = d \times \vec{y}_{i}^{t + 1} + (1 - d)^{2} \times ω^{'}_{i} \vec{x}_{i}^{t + 1} (9)$

上式中，d代表取值在[0,1]内的随机数； $_{i}^{t + 1}$ 代表粒子群算法随机游走产生的新解。

通过混合自适应布谷鸟算法[16,17,18]16-18]求解多仓库多配送点物流配送路径优化问题，由于配送中心和客户均为离散点，因此，对算法离散化处理。详细的操作步骤如下所示：

1)在现阶段路径方案中随机选取两条边，分别为c1(x,y)和c2(x,y);

2)假设|j(i+1)|≥2,则将c1(x,y)和c2(x,y)删除；

3)将顶点ej作为b1遍历起点，同时重复步骤1)和2),直至j=n-1;

4)将顶点ei作为b2遍历起点，同时重复步骤1)和步骤3),直至i=n-1;

5)重复上述操作步骤，直至不存在交叉边缘，则终止操作。

结合以上分析，以下给出混合自适应布谷鸟算法求解多仓库多配送点物流配送路径优化模型的详细操作步骤：

1)对多仓库多配送点物流配送路径优化模型中的参数和算法参数展开初始化处理，主要包含车辆、车速以及种群规模等参数。

2)通过公式(10)获取客户数据，主要包含客户坐标位置、客户需求以及时间窗：

$ϖ = \vec{z}_{i}^{t + 1} (g_{x, y}, θ_{i j k}, S_{(i)}) (10)$

上式中，gx,y代表客户所在具体坐标位置；θijk代表客户真实需求；S(i)代表时间窗。

3)计算不同坐标点之间的距离Δτij,如公式(11)所示：

$Δ τ_{i j} = ϖ [g_{x, y} (m) - g_{x, y} (n)] (11)$

上式中，gx,y(m)和gx,y(n)代表客户之间的距离。

4)引入混合自适应布谷鸟算法形成多仓库多配送点物流配送路径优化模型的初始解，同时计算适应度值[19,20]19-20]。

5)判断是否满足迭代终止条件，假设是，则直接输出最优多仓库多配送点物流配送路径；反之，则调整步长因子和发现概率，同时形成新的多仓库多配送点物流配送路径，引入粒子群算法随机游走形成全新的物流配送路径，将两个解合并形成新的物流配送路径，得到新的物流配送路径。

3 仿真实验分析

为了验证多仓库多配送点物流配送路径优化算法的有效性，展开仿真实验研究。

3.1 实验数据和实验环境

通过Simio仿真软件生成A市多仓库多配送点物流配送路径电子地图，测试不同算法的路径优化效果。通过实际需求，共计设立了8个不同规模的物流配送问题，客户规模从2000到8000不等，仓库数量为5个，设定物流配送车辆的容量为2000kg, 可行驶最大距离为450km。实验环境为：64位Windows7操作系统，内存为16GB。A城市的仓库和配送点分布情况如图2所示：

图2 A市仓库和配送点分布示意图下载原图

3.2 实验结果分析

为了验证所提算法的性能，在动态区域不断变化的情况下，通过图3分析不同算法的多仓库多配送点物流配送路径长度变化情况：

图3 物流配送路径长度实验结果比较下载原图

分析图3可知，在不同动态区域下，不同算法获取的多仓库多配送点物流配送路径长度存在差异。其中，采用粒子群算法和布谷鸟算法获取的配送路径长度明显更高一些；而将两者有效结合后，采用所提算法获取的物流配送路径总长度明显更短一些，说明其获取的解质量更好，适用于求解多仓库多配送点物流配送路径优化问题。

通过表1进一步分析上述几种不同算法的计算时间：

表1 不同动态区域下各个算法的计算时间实验结果比较导出到EXCEL

测试动态区域编号	计算时间/s
测试动态区域编号	所提算法	粒子群算法	布谷鸟算法
01	28.4	40.7	56.2
02	32.6	32.5	33.8
03	25.9	63.0	80.5
04	27.5	78.9	56.7