改进蚁群优化算法的最优物流配送路径设计

2020-06-19张滨丽卞兴超

现代电子技术 2020年9期

张滨丽卞兴超

摘要：针对传统蚁群优化算法难以找到全局最优的物流配送路径，物流配送的时效性差等缺陷，为获得理想的物流配送路径，提出基于改进蚁群优化算法的最优物流配送路径设计方法。首先，对物流配送路径优化设计问题进行分析，建立物流配送路径优化模型;然后，将蚁群置于物流配送的起始点，通过搜索下一节点、信息激素更新等模拟自然界蚁群寻食机制，找到从起始点到配送目标点的最优物流配送路径，并对传统蚁群优化算法的不足进行相应的改进;最后，通过具体实例分析改进蚁群优化算法应用于最优物流配送路径设计中的有效性。改进蚁群优化算法可以在短时间内成功找到最优物流配送路径，物流配送时间要少于其他物流配送路径设计方法，能够为提高物流企业的经济效益提供有价值的参考信息。

关键词：物流配送; 物流路径设计; 蚁群优化算法改进; 路径优化模型; 算法有效性分析; 企业效益提升

中图分类号： TN02?34; TP183 文献标识码： A 文章编号： 1004?373X（2020）09?0105?04

An optimal logistics distribution path design based on improved ant colony optimization

ZHANG Binli， BIAN Xingchao

（Suihua University， Suihua 152061， China）

Abstract： Since there are shortcomings in the traditional ant colony optimization， like difficulty in getting the global optimal logistics distribution path and poor time efficiency of logistics distribution， an optimal logistics distribution path design method based on the improved ant colony optimization is proposed to obtain an ideal logistics distribution path. The optimization design of logistics distribution path is analyzed. The optimization model of logistics distribution path is established. The ant colony is placed at the start point of logistics distribution. And then， by searching for the next node and information hormone updating， the ant colony feeding mechanism in the nature is simulated， and the optimal logistics distribution path from the start point to the distribution target point is found. In addition， the shortcomings of the traditional ant colony optimization are improved. In the end， the effectiveness of the improved ant colony optimization applied to the optimal logistics distribution path design is analyzed by means of some specific examples. The improved ant colony optimization can find the optimal logistics distribution path successfully in a short time， and its duration of logistics distribution is shorter than that of other logistics distribution path design methods. Therefore， it can provide valuable reference information for improving the economic benefits of logistics enterprises.

Keywords： logistics distribution; logistics path design; ant colony optimization improvement; path optimization model; algorithm effectiveness analysis; enterprise benefit improvement

0 引言

随着经济全球化进程的不断加快，企业的物流活动日益频繁，电子商务快速发展，物流成为企业的一个重要环节[1]。运输费用占用物流费用的比重相当高，运输费用与物流配送路径选取直接相关。物流配送的目的就是為顾客提供最优的服务，同时，尽可能地降低物流配送成本，因此，设计最优的物流配送路径具有重要的研究意义[2?3]。

由于国内物流起步比较晚，因此，物流配送路径设计研究时间相对较短，最初主要通过司机凭借自己的经验规划最优物流配送路径，由于缺乏科学指导，得到的物流配送路径并非最优，物流配送效率低，物流配送的成本高[4?6]。随后有学者提出了基于贪婪法的物流配送路径设计方法，但是贪婪法求解最优路径的时间长，故有学者提出了动态规划算法的物流配送路径设计方法、基于整数规划算法的物流配送路径设计方法、基于分支定界法的物流配送路径设计方法，这些方法属于精确算法[7?9]，虽然可以获得比贪婪法更优的物流配送路径，但是由于本质上和贪婪法均属于穷举搜索算法，物流配送路径求解问题属于NP?Hard 问题，因此，同样存在物流配送路径求解时间长、效率低等局限性[10]。

随着非线性优化理论、人工智能技术、群智能优化理论的不断发展和融合，近些年学者们提出了一些基于启发式搜索算法的物流配送路径设计方法，如基于遗传算法的物流配送路径设计方法、基于模拟退火算法的物流配送路径设计方法、基于禁忌搜索算法的物流配送路径设计方法、基于蚁群算法的物流配送路径设计方法，它们具有全局优化和通用性等特点，通过模拟自然界生物进化、群体搜索等行为，可以较快地找到物流配送路径[11?13]。在实际应用中，物流配送路径设计过程中，不确定性因素多，因素之间存在交叉影响，它们大多数集中于单一因素的物流配送路径设计问题，同时，这些启发式搜索算法存在一些不足，如发生早熟概率相当高，易找到局部最优的物流配送路径[14?15]。

针对当前物流配送路径设计方法存在求解效率低、求解错误率大的问题，为提高物流配送路径求解的成功率，提出了基于蚁群优化算法的最优物流配送路径设计方法。通过具体实例分析蚁群优化算法应用于最优物流配送路径设计中的有效性。

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

1.1 物流配送路径优化问题描述

物流配送路径优化问题就是為了达到一定的目标，如配送时间最短、配送路径最短或者配送成本最低，并且满足一些约束条件，如车辆最大载物量、配送结束时间等。对于不同配送点的客户，找到最科学、合理的物流配送路径，其包括许多关键因素，如下：

1）配送中心，通常是物流配送过程中的车辆行驶路线的起点或终点，承担全部车辆调度，通常情况下，其位置是固定的。

2）车辆，主要包括车辆数量、车辆的最大行驶距离、规定最大载重等。

3）客户，即服务的对象，主要包括服务时间期限、优先级、货物需求量。

1.2 物流配送路径优化模型

物流配送路径优化问题可以使用有向图[G=（V，A）]进行描述，[V={v0，v1，v2，…，vn}]表示客户、配送点，[A={（vi，vj）vi，vj，i≠j}]表示客户之间、配送点之间以及客户与配送之间的有向弧，物流配送路径优化问题采用图1表示。

最优物流配送路径优化问题的数学模型可以表示为：

[f=max F（S）=mink=1mi=0nj=1n（λij，xijk）] （1）

式中：[k]表示车辆的编号;[m]表示车辆的数量;[n]表示客户的数量。

物流配送路径优化问题的约束条件如下：

1）车辆访问客户[i]有且只有一次，即：

[yki=1] （2）

2）客户点[i]的货物需求量为[qi]，客户需求的总量不能超过配送中心的所有车辆最大容量，即：

[（qi，yki）

3） [λij]表示[A]上的有向弧权重，[xijk]表示第[k]个车辆经过有向弧[（vi，vj）]时，[xijk=1]，否则，[xijk=0]，即有：

[xijk=1，第k个车辆经过有向弧0，第k个车辆未经过有向弧] （4）

综上可知，物流配送路径优化问题是一个典型的组合优化问题，蚁群优化算法是一种通过正反馈与分布式协作对问题进行求解的启发式搜索算法。由于蚁群在寻找食物时，总是寻找一种从食物源到蚁穴的最短路径，这与物流配送路径优化问题十分相似，因此，引入改进蚁群优化算法对其进行求解。

2 改进蚁群优化算法的最优物流配送路径设计方法

2.1 传统蚁群优化算法

第[t]个时刻，节点[i]上的蚂蚁数量为[Bi（t）]，那么蚂蚁数量为[m=i=1nBi（t）]，[n]表示节点数，即客户的数量，节点[i]和[j]之间的距离为[dij]，最初，全部路径没有蚂蚁爬行过，初始信息素相同，即[τij（0）=C]，那么第[t]个时刻，节点[i]上的蚂蚁[k]向节点[j]转移的概率为：

[pkij（t）=ταij（t）ηβij（t）s∈allowedkταij（t）ηβij（t）， j∈allowedk0， otherwise] （5）

式中：[allowedk]表示蚂蚁[k]可以选择的节点集合;[α]和[β]分别表示启发因子和期望因子;[ταij（t）]和[ηβij（t）]分别表示节点[i]和[j]之间路径的信息素量和能见度。

由于蚁群优化算法具有正反馈机制，路径越短，那么该路径上的信息素量越大，每一只蚂蚁爬行一步后，对路径上的残留信息素进行更新，具体如下：

[τnewij=（1-ρ）τoldij+Δτij] （6）

[Δτij=k=1mτkij] （7）

式中：[ρ]表示信息素的挥发系数;[Δτij]表示节点[i]和[j]之间路径的信息素增量。

2.2 蚁群优化算法的改进

由于传统蚁群优化算法存在一些不足，如搜索时间长、容易过早收敛等，从而影响了物流配送路径的求解，因此本文对其进行改进。信息素的挥发系数[ρ]用于描述信息素量的持久程度，由于采用固定取值方式无法体现蚁群算法的特点，因此，本文采用适应变化取值方式加快了收敛速度，且减少了出现过早收敛的概率，具体如下：

[ρ=0.2， NC∈[0，0.25NC_max]0.3， NC∈[0.25NC_max，0.75NC_max]0.4， NC∈[0.75NC_max，NC_max]] （8）

式中NC和NC_max分别表示当前和最大迭代次数。

2.3 改进蚁群优化算法的最优物流配送路径求解

改进蚁群优化算法的最优物流配送路径求解步骤如下：

1）建立最优物流配送路径优化问题相对应的有向图。

2）初始化蚁群，将所有蚂蚁分别放置于节点之上，所有路径上的初始信息素相同。

3）迭代次数NC=0。

4）计算每一只蚂蚁选择下一个爬行节点的概率，并根据计算结果爬行到下一个节点。

5）对相邻节点之间路径上的信息素进行更新。

6）当所有蚂蚁对整个路径进行爬行后，对整个路径上的信息素进行更新。

7）迭代次数NC=NC+1。

8）如果NC>NC_max，那么输出最优物流配送路径。

3 最优物流配送路径设计方法的测试分析

3.1 测试环境

为了分析改进蚁群优化算法的最优物流配送路径设计方法的性能，采用Matlab软件编程实现仿真测试。物流配送路径参数设置为：有8个客户点，1个配送中心，配送中心的位置为（0，0），车辆数量为3，车辆的最大载重为125，客戶点的位置和货物需求量如表1所示，改进蚁群优化算法的最大迭代次数为200。

3.2 测试结果与分析

采用传统蚁群优化算法的优化物流配送路径设计方法，如基于遗传算法的物流配送路径设计方法作对比测试，进行5次仿真实验，统计每一次实验的最优物流配送路径长度，结果如图2所示。从图2可以看出：改进的蚁群优化算法的最优物流配送路径长度平均值为111.39;传统蚁群优化算法的最优物流配送路径长度平均值为114.65;遗传算法的最优物流配送路径长度平均值为114.64。改进蚁群优化算法获得了更优的物流配送路径，提高了物流配送速度，可以减少物流配送的时间成本，实际应用价值更高。

统计每一次实验找到最优物流配送路径的迭代次数，具体如表2所示。

从表2可以看出，改进蚁群优化算法找到最优物流配送路径的迭代次数要明显少于传统蚁群优化算法和遗传算法，加快了最优物流配送路径的求解效率，可以应用于大规模物流配送路径设计问题的求解，实际应用范围更加广泛。

4 结语

研究最优物流配送路径具有十分重要的实际价值。为了解决当前物流配送路径设计方法存在的一些问题，本文提出了基于蚁群优化算法的最优物流配送路径设计方法，并与传统蚁群优化算法、遗传算法进行了对比测试，结果表明，改进蚁群优化算法可以获得理想的物流配送路径，而且搜索效率高，具有十分广泛的应用前景。

参考文献

[1] 葛显龙，许茂增，王伟鑫.基于联合配送的城市物流配送路径优化[J].控制与决策，2016，31（3）：503?512.

[2] 兰辉，何琴飞，边展，等.考虑道路通行状况的冷链物流配送路径优化[J].大连海事大学学报，2015，41（4）：67?74.

[3] 葛显龙，孔阳.带有时间窗的生鲜物流配送路径优化研究[J].数学的实践与认识，2016，46（12）：78?87.

[4] 戴昕.基于反向学习策略粒子群的物流配送路径优化研究[J].物流技术，2014，33（13）：291?294.

[5] 李周芳，杨桦.基于多蚁群优化的粮食物流配送路径问题研究[J].中国农机化学报，2013，34（4）：283?286.

[6] 姜代红.改进的遗传算法在多目标物流配送路径中的应用[J].科学技术与工程，2013，13（3）：762?765.

[7] 周艳聪，孙晓晨，余伟翔.基于改进遗传算法的物流配送路径优化研究[J].计算机工程与科学，2012，34（10）：118?122.