基于蚁群算法的物流配送路径优化方法研究

何宇翔

（长沙理工大学水利与环境工程学院，湖南长沙 410114）

近年来，物流配送网络智能规划得到了广泛的研究与应用。但由于配送车的数量有限，且其最大行驶距离为固定值。因此，在每辆配送车均不超过最大行驶距离的条件下优化配送路线，使其可在访问所有目标仓库的同时确保行驶路径最短，可以直接节省时间与能耗成本[1-4]。

优化配送路径，不仅能缩短配送时间、减少成本并提升用户满意度，还可缓解交通压力、降低运输污染并保护环境，因此具有重要的研究价值。物流配送路径优化(Logistics Distribution Path，LDP)是一个经典的组合优化问题[5-8]，该问题的计算量大、复杂程度也较高。目前，国内外用于求解此类问题的方法主要有精确优化方法(Precise Optimization Method)、启发式算法(Heuristic Algorithm)、亚启发式方法(Metaheuristics Algorithm)与智能优化方法等。

蚁群优化(Ant Colony Optimization，ACO)算法是一种仿生学智能算法，其通过使用信息素来选择路径，并朝着最优解的方向不断改进，故具有较强的自组织性。然而该算法存在易进入早熟状态及过早陷入局部最优解的问题，由此便会造成最终解并非全局最优解。所以将该算法加以改进，克服其所存在的不足后，即可作为最优配送路径的求解方法。

1 物流配送路径优化问题建模

1.1 模型设计

在港口物流配送的场景中，来自海外的货物首先需要被分拨至目的仓库中进行一级分配，或需将来自各地区的货物转移到同一艘货轮上。算法应合理规划每辆车的运输路线[9-11]，进而令车辆间的运输任务不会相互冲突，并使整个物流配送任务的运输效率达到最高。

假设物流配送任务有一个中心仓库及若干个目标节点，每辆车均从中心仓库出发，且运输不超过核定载重。按照指定路线到达目标节点，卸载该节点所需的货物，然后再返回中心仓库的路线模型，如图1所示。

图1 物流配送模型

根据配送问题中的实际情况，可总结出以下几个约束条件：

1）每个目标节点仅会被访问一次。

2）每条配送路径的长度均不能超过车辆满油时的最大行驶距离。

3）一条配送路径上所有目标节点的货物总和不能超过一辆汽车的核定载货量。

4）所有目标节点必须包含在配送路线中。

1.2 问题公式化

假设一共有M个目标节点需要到达，目标节点i处的货物量为qi，i∈[1,2,…,M]，而中心仓库的编号为0，节点i与j之间的最短路径长度则为dij。可调配的汽车共有K辆，车辆k的核定载货量为Qk，满油时的最大行驶距离为Dk，k∈[1,2,…,K]，nk是需要分配的目标节点数。将该目标节点的集合定义为，其中表示该目标点在车辆k的配送路线中所处的位置为i。

若将运输效率最高定义为整个路径优化的总距离最短，则总运输距离表示为：

其中，符号函数sgn(·)可定义为：

将约束条件归纳为数学公式，则有：

因此，在满足式（3）-（6）所有的条件下，物流配送路径优化问题可公式化为：

2 路径优化算法设计

2.1 蚁群算法的改进

在经典蚁群算法中，蚂蚁会直接选择由信息素浓度所决定的、概率值最大的节点来作为下个目标节点[12-14]。故在一定迭代步数后，不同节点对应的路径信息素含量差距越来越大，蚂蚁便越难以探索新的路径，进而使寻路过程陷入早熟的状态。

为使蚂蚁能有充分探索新路径的可能性，文中采用强化学习中的贪心算法(Greedy Algorithm)思想来对ACO 加以改进，并选择蚂蚁下一个要访问的节点[15-16]。具体选择规则如下：

式中，ε为探索概率，k为衰减系数，p为迭代过程中产生的选择概率。

经典蚁群算法中，更新规则如下：

式中，ρ为信息素挥发因子，ρ∈(0,1)；τ为信息素浓度，σ为初始系数；Lk为当前路径长度。当蚂蚁k经过路径i→j时，该路径上的信息素才会更新，并增加

此处蚂蚁默认为可以无限次地访问目标节点，且不存在约束条件。然而，实际路径规划问题中的车辆存在最大行驶距离约束。因此，经典蚁群算法中的信息素浓度更新策略无法筛除不满足约束条件的路径，故需根据具体问题设计不同的信息素浓度更新方法。

该设计的更新思路为：当K只蚂蚁完成节点访问后，对产生的K条路径进行评估。标记满足单个车辆最大行驶距离约束的规划路径，使之成为可行解；而对不满足约束条件的规划路径，则朝着满足约束的方向转化。令最终的解空间均为满足约束条件的规划路径，从中选择总路径长度最短的规划方案便一定是满足约束条件下的最优解。

此次设计的局部最优解信息素浓度更新方法如下：

式中，Ebest为当前最优路径上所有蚂蚁路径的总长度。

对于非最优解，所设计的信息素浓度更新方法为：

式中，El为第l条路径的总长度，且El＞Ebest。

2.2 算法描述

基于ACO 的路径优化算法步骤可描述如下：

1）初始化蚂蚁数K、信息素启发因子α、路径启发因子β、信息素挥发因子ρ、探索概率ε、衰减系数k、初始选择概率p0以及最大迭代次数Nc。

2）生成目标节点距离矩阵DN×N，构建每只蚂蚁m的待访问节点集合N(m)，并建立禁忌表。

3）从中心仓库开始，为每只蚂蚁选择下一个目标节点，直至所有节点均被访问。首先对蚂蚁k，根据式（9）计算路径选择概率p；然后根据式（8）选择下个目标节点j，并将其加入禁忌表；最终判断所有蚂蚁是否访问完全部节点，若是，则转至步骤4），否则重新计算选择概率p，并完成后续步骤。

4）计算每只蚂蚁的路径长度。

5）判断每只蚂蚁的路径长度是否满足约束，是则判定为可行解，且选择长度最小的解作为局部最优解。

6）对可行解，根据式（12）更新每条路径的信息素浓度。

7）对不可行解，则依据式（14）更新每条路径的信息素浓度。

8）重复步骤3）～步骤8），直至Nc达到最大迭代次数。

9）输出全局最优解，作为路径优化的最终结果。

3 算法仿真

3.1 仿真数据

为了验证路径优化算法的可行性，该文在无量纲的网格地图中，使用一个中心仓库与随机生成的11 个或34 个目标节点进行路径求解测试，实例描述如下：

假设中心仓库（标号0）位于坐标（70，40）处，共有20 辆车可供调度，且每辆车载重1 t。则目标节点的分布，如图2-图3 所示。

图2 11个目标节点分布图

图3 34个目标节点分布图

3.2 仿真结果

算法采用Matlab 软件平台进行仿真，输入仿真数据并通过路径优化算法进行求解，两种不同目标节点所获得的规划路径结果分别如图4-图5 所示。

图4 11个目标节点规划的配送路径

图5 34个目标节点规划的配送路径

而计算得到的路径总长度，分别如图6-图7所示。

图6 11个目标节点规划路径的总长度

图7 34个目标节点规划路径的总长度

从上述仿真结果图可看出，无论是11 个或是34个目标节点，文中所设计的路径优化算法均能够设计出较为合理的配送路径，并能快速收敛得到最短的路径长度，从而优化配送成本。

3.3 算法对比

为验证所提算法的有效性，将本算法与标准蚁群算法、遗传算法(Genetic Algorithm，GA)进行对比，以此来分析算法的性能。3 种算法的初始仿真参数设置如下：该算法和标准蚁群算法的蚂蚁数量均为50 个，信息素启发因子均为1，路径启发因子均为5。遗传算法的交叉率设置为0.8，变异率为0.3。

实验计算得到3 种算法访问34 个目标节点的最终路径总长度，如表1 所示。

表1 规划路径总长度

由表1 可以看出，根据该文算法所规划出的路径总长度最小，标准蚁群算法则达到了所提算法的两倍以上。这是由于标准蚁群算法陷入了局部最优，故无法找到全局最优解。而遗传算法虽收敛速度快，但最终解的质量较差。

4 结束语

配送环节是现代物流行业中的关键，提高配送效率可大幅缩减物流业的成本。针对普遍存在的配送路径优化问题，文中首先归纳出此问题的一般模型及实际问题的约束条件，并将其总结为数学形式的表达。然后介绍了蚁群算法能寻找最短路径的根本原理及其过程，最终将蚁群算法融入物流配送的路径优化问题中，并分析二者的相似性。同时还将路径优化问题的各个条件对应到蚁群算法的各要素中，进而设计出基于ACO 的路径优化算法，再根据两个实例仿真分析了算法的有效性。结果表明，该算法能够满足路径优化的设计目标。