基于蚁群算法的物流配送中车辆路径优化问题研究

张 伟

（兰州交通大学 机电技术研究所，甘肃 兰州 730070）

ZHANG Wei

(Electromechanical Technology Research Institute of Lanzhou Jiaotong University,Lanzhou 730070,China)

0 引言

在经济全球化的大趋势下，物流行业也发生了一定的变化，已经从传统的运输服务行业逐渐向着综合性物流系统型行业的模式发展。现阶段，很多国家及地区都形成了较为完善的物流理念，拥有着成熟的物流技术，我国物流行业发展虽然缓慢，但是由于我国资源丰富，铁路、公路等物流基础设施建设比较完善，为物流行业发展提供了良好的环境，使得我国的物流行业齐头并进，逐渐具备了与国外先进物流技术相媲美的实力。

现代化物流配送是市场经济发展的要求，对促进大众消费、优化资源配置等方面都具有较大的影响。物流配送方案的好坏，在很大程度上决定了物流配送的效率与成本，同时也影响着实现物流服务行业的附加价值。而物流配送车辆路径优化问题，早在1959年就由Dantzig 及Ramser 提出，后来这一说法引起了物流科学、组合数学、应用数学、运筹学等学者、专家们的重视，成为组合优化领域的热门话题。关于物流配送车辆路径优化问题，定义为：对物流货物装卸点进行有效的组织，安排恰当的行车路径，保证物流配送车辆能够有序的通过这些装卸点，并能够在一定的交货时间、货物需求量、时间限制等约束条件下，尽可能实现用最少车辆、最少时间、最短行程完成物流配送任务。

在近几十年的研究中，有关配送车辆路径优化算法出现很多，包括精确算法、智能优化算法以及启发算法等，其中精确算法在路径优化中的应用计算复杂程度较高，具有一定的局限性；启发式算法中包括SWeep 算法以及C-W 算法等，这些算法虽然具有速度快的优势，但是如果客户数量过多时，就会增加算法搜索的难度，不容易找到最优路径；人工智能算法的出现，在一定程度上提高了路径优化的效率，其中神经网络算法、遗传算法等都属于人工智能算法中的一种。然而物流配送车辆路径优化工作是一项复杂的大规模工作，有些算法在网络结构、参数确定等方面还存在缺陷，不能同时满足时间、成本、车辆等因素条件。

蚁群算法也属于智能优化算法的一种，主要是利用正反馈并行机制，并根据蚂蚁之间的相互协作在最短时间找到食物与巢穴的最短路径现象确定的一种算法。蚁群算法具有求解速度快、并行性能力强等优势，近年来在水运、铁路、公路等领域都得到了广泛的应用。本文也将蚁群算法应用到物流配送车辆路径优化问题中，通过此原理建立数学模型，并通过模型找出路径优化的最优解。

1 建立数学模型

在物流配送工作过程中，其实就是讨论以什么样的路径进行运输，也就是在已知客户需求量以及车辆载重量的基础上，探讨怎样以最短的时间、最少的成本，缩短配送路程。在寻找最短路径过程中，还需要满足以下几个条件：第一，所有的物流配送车辆必须将配送中心作为起点和终点，完成一个配送的循环；第二，每辆配送车仅能为一条路线服务，并且每辆配送车仅能访问一个客户；第三，在配送路线上，客户需求量不能超过车辆配送的载重量总和；第四，车辆的路线不能重复。

根据上述的几个约束条件，在物流配送车辆路径优化问题上，就是寻找最优路径。我们可以将物流配送中心用v0表示，将配送地点用vi表示，用k 表示配送中心车辆数目的上限，用Q 表示配送车辆的载重。这样就能将配送路径优化数学模型表示为：

2 关于蚁群算法的相关理论

本文中所讲的蚁群算法，属于仿生优化算法中的一种，是一种新兴的算法工具，主要是通过模仿蚂蚁蚁群的行为，得出最优解。其实，蚁群算法主要是模仿蚂蚁觅食的过程，将蚂蚁觅食的路径当做是物流配送车辆运输的路径，将蚂蚁行动的录像集合作为移动线路，并利用分布式协作以及正反馈机制，获取最优解。这种算法鲁棒性强，并且具有很快的求解速度，广泛应用于二次分配、作业调度、旅行等领域，并具有良好的应用效果。

图1 是蚁群路径搜索过程图：

如图1 所示，用字母A 代表蚁巢，将食物源用字母F 表示，同时设置一个障碍物，用CD 表示。由于存在障碍物，蚂蚁在觅食过程中必须穿过障碍物，穿过障碍物的路径有多种，蚂蚁会通过相互之间的合作机制、信息素更新机制等，选择最短的路径作为觅食路线。

3 基于蚁群算法的物流配送车辆路径优化设计

在物流配送车辆路径优化算法设计过程中，利用蚁群算法，主要包括确定蚁群数目、设定蚁群路径选择规则、信息素更新机制规则等几个方面：

3.1 确定蚁群数目。假设一共有n 个客户数，相应的蚁群中就具有m 个蚂蚁数量，则蚂蚁数量可以用下面的表达式表示：m其中在时间t 点，在客户i 位置上，蚂蚁的数量就表示为bi（t）。

3.2 蚁群路径选择规则。在物流配送车辆路径优化设计过程中，基于蚁群算法，蚂蚁（k）从一个客户到下一个客户中间转移的过程中，需要考虑到下一个客户路径中信息素浓度、路径总长度等问题。我们可以将允许访问的客户点用j 表示，将配送中心用o 表示，这样就能将蚂蚁从上一个客户点到下一个客户点转移路径的概率用相关的计算公式表示出来，具体表示为：

在上式中，权重系数用a、b 表示，而蚂蚁从上一个客户到下一个客户所用的时间用tij表示，将信息启发式因子用α 表示，而期望启发式因子用β 表示。而两个客户之间路径关联启发式信息值用ηij（t）表示，并且可以将ηij（t）定义为：ηij（t）=1/dij，其中，dij是两个客户自检的距离。

3.3 信息素更新机制规则。利用蚁群算法过程中，为了对循环最优解进行充分的利用，并且保证尽快的找到最优解，需要在每次循环后，将每只蚂蚁带来的相关信息进行及时的更新，同时在信息素更新过程中还需要遵循一定的规则。如果将信息素挥发系数用ρ 表示，其中ρ 是0 到1 之间的一个随机数值，将信息素残留因子用1-ρ 表示；一次循环中路径中增加的信息素可以用ΔTij表示，设ΔTij的初始值为0。那么就能够将信息素更新操作的规则用以下两个式子表示出来：

4 物流配送中车辆路径优化实现

在物流配送车辆路径优化问题求解方面，利用蚁群算法，主要是用人代替蚂蚁来寻找物流客户点，如果下一个客户服务点中，车辆总载重量如果被超出，或者是两者之间的距离比车辆一次行驶的最大距离远，这需要配送车辆回到配送中心，同时也表示该配送车辆完成了这次的配送任务，该辆配送车就能够进行下一个服务站点的任务，直到有一个客户获得了一次完整的服务为止，这就说明人工蚂蚁完成了一次循环。在经过一个循环后，根据每一个人工蚂蚁在循环过程中得到的信息，对路径中的信息素增加量进行有效的计算，同时进行信息素更新操作，这样重复的循环后，就会有大部分人工蚂蚁找出相同的路径，同时也会找到最短的路径，这样就完成了最优解的算法设计。本文将这个构成步骤整理为以下几点：

第一步，将参数进行初始化设置，然后对有需求的客户进行相关数据读取，之后产生全局最初解。

第二步，在物流配送中心设置m 个人工蚂蚁，将初始时间以及迭代次数都设置为0，同时进行蚁群禁忌表建立。

第三步，对于每一个人工蚂蚁，需要从列表中查出其没有到达过的节点，同时根据上文中提到的转移概率的公式，通过详细的计算、分析，为人工蚂蚁选择合理的下一个客户服务点。

第四步，对两个客户服务点路径中的货运总量进行计算，如果路径中的货运总量比车辆最大载重量大，那么就直接进行下一个步骤；如果没有超过，就能够将该节点作为可行点，并跳转到第六步中。

第五步，对客户需求点等待的时间进行计算，如果符合时间窗的相关要求，就能在禁忌表中加入该点，同时计算两个点之间的路径费用、长度等，跳转到第三步进行；否则就在可行点集合中加入该点，同时进入下一步。

第六步，统计车辆的数目，然后判断可行点的集合，如果集合为空集，则直接进入下一个步骤。如果集合不是空集，则需要从集合中获取没有经过搜索的点，同时将时间最短的节点作为起点，跳回到第三步进行。

第七步，更新每一个人工蚂蚁带来的信息素增量。

第八步，搜索人工蚂蚁路径的最短值以及路径的最短距离，同时计算最短路径对应的费用，并及时的更新信息素。在循环开始时，对所有的人工蚂蚁进行迅游，对人工蚂蚁搜索过后的边进行信息素更新，不然就进行本循环中找到的最优路径。

第九步，对本次循环以及所有的路径最优解进行比对，如果本次循环比全局最优解路径更短，就将其作为最优解，同时更新最优解列表。

第十步，找到全局的最优解或者迭代次数达到上限，就表示该程序完成，否则就需要从第二步骤开始进行重复上述过程。

可以将本步骤用图2 表示：

5 仿真实验

假设一个物流配送中心一共有30 辆车，每辆车的载重量相等，都为12吨，同时向30 个服务客户提供物流配送服务，客户的坐标资料是已知的，每一个客户的客户需求量也是已知的。客户资料如表1 所示。

采用专业的仿真计算机平台，平台主要为3.4GMHz 的CPU、4G 内存，Windows2007 操作系统，在VB6.0 语言环境下进行编程实现。用同时设置蚁群算法的相关参数，具体设置如表2 所示。

实验结果如下：

当迭代达到283 次时，求出了路径的最优解，并且最优路径的长度通过计算得到为165。

同时，仿真实验中还将蚁群算法与遗传算法、模拟退火算法等进行了有效的对比，用每一种算法运行10 次，然后通过计算，对比结果的平均值，其中遗传算法找出的最优路径长度为183.2，整个过程花费了50 多秒，成功率为65%；模拟退火算法找出的最优路径的长度为172.4，过程时间为42 秒，成功率为78%；本文中提到的算法，最优路径长度为165，整个过程花费的时间为21 秒，成功率高达98%。这些数据说明了蚁群算法在物流配送车辆路径优化中具有独特的应用优势，能够在短时间找出最短路径，是提高物流配送效率的有效方式。

6 总结

通过上述分析可知，物流配送中车辆路径优化问题关系到物流配送的成本、效率等，关系到客户的满意度，是现阶段物流行业关心的问题之一。本文提出了一种基于蚁群算法的物流配送中车辆路径优化方式，基于蚁群算法的鲁棒性、快速性等特点，短时间找出最短的配送路径。并且通过仿真实验证明了，本文提出的优化算法有效性极高，值得在物流行业中大范围的使用与推广。

表1

表2

[1]章兢，周泉.基于免疫克隆算法的物流配送车辆路径优化研究[J].湖北大学学报，2012,28(2):114-115.

[2]亓霞，陈森发，黄鵾.基于免疫算法的物流配送车辆路径优化问题研究[J].土木工程学报，2013,26(3):99-100.

[3]尚华艳.物流配送中车辆路径问题研究[J].武汉理工大学，2013,14(4):63-64.

[4]荆海霞.物流配送中双向运输车辆路径优化问题研究[J].武汉大学学报，2013,26(6):54-55.

[5]曹二保.物流配送车辆路径问题模型及算法研究[J].湖南大学学报，2013,18(9):247-248.

[6]戴锡.车辆路线问题的二阶段启发式算法及其在现代物流配送中的应用[J].复旦大学学报，2013,28(7):511-512.

[7]元兴.物流配送中心车辆路径优化中的几种算法研究[J].计算机仿真，2011,18(7):41-42.

[8]卫田，范文慧.基于NSGAⅡ的物流配送中车辆路径问题研究[J].计算机集成制造系统，2013,28(3):110-111.

[9]钟石泉.物流配送车辆路径优化方法研究[J].天津大学学报，2011,18(8):45-46.

[10]肖健梅，黄有方，李军军.基于离散微粒群优化的物流配送车辆路径问题[J].系统工程，2011,17(8):78-79.