CVRP物流配送路径优化及应用研究

2016-12-22袁文涛孙红

软件导刊 2016年11期

袁文涛　孙红

摘要：车辆行驶路径优化问题是智能安全交通网络的重要组成部分。针对传统车辆路径求解搜索时间过长、得不到最优解、求解质量不高的现况，在研究一般物流配送路径问题处理方法和数学模型的基础上，提出了一种改进的蚁群算法求解问题以提高构建路径的速度和质量，在限量车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）中用改进的蚁群算法来优化求解车物流的配送路径。通过MATLAB仿真结果表明，蚁群算法搜索速度相对较快，具有良好的全局求优能力，收敛结果表明可以准确求出最优路径，相比传统方案，优化后解的质量得到了提高，速度提高了80%左右，是一种可行性较高的求解物流配送路径优化问题的有效算法。

关键词：蚁群算法；物流配送；路径优化；数学模型

DOIDOI：10.11907/rjdk.161974

中图分类号：TP319

文献标识码：A 文章编号文章编号：16727800（2016）011014004

基金项目基金项目：

作者简介作者简介：袁文涛（1993-）男，安徽马鞍山人，上海理工大学光电信息与计算机工程学院硕士研究生，研究方向为模式识别与智能系统；孙红（1964-）女，上海人，上海理工大学光电信息与计算机工程学院副教授、硕士生导师，研究方向为模式识别与智能系统、控制理论与控制工程、企业信息化系统与工程。

0 引言

解决组合优化问题的最优化求解算法有多种现代人工智能算法方案，优化算法用来处理问题最优解的求解，该问题通常由多个变量共同决定。当前，求解最短路径问题是图论研究中的一个典型求解组合优化算法问题，旨在寻找图表（由节点和路径构成）中两节点或多节点之间的最短路径。常用的最优化路径求解方法有Bellman-Ford算法、Dijkstra算法、A*算法和蚁群算法。这些算法都有自身的优点和不足。在对不同算法作出比较后，可以得出蚁群算法在解决网络路由和城市交通系统的问题中是相对有利的。

就目前研究来看，随着实际组合问题的变化，基本的智能算法已经不能满足解决这类组合优化问题，同时其优势也在减弱[1]。本文采取改进后的组合优化蚁群算法以弥补传统蚁群算法易陷入局部最优解的不足，加快了求全局最优解的构造速率。

蚁群算法（Ant Colony Optimization， ACO），是一种模拟蚂蚁群体智能行为的进化仿生类优化算法，在求解性能上具有强鲁棒性、优良的分布式计算能力、便于与其它算法相结合等优点[2-3]。通常作为一种用来在多变量组合优化问题的多候选解中寻找最优化路径的机率型算法。它由Marco Dorigo于1992年在其博士论文《Ant system： optimization by a colony of cooperating agents》中首先提出，其灵感来源于通过对蚁群社会的长期跟踪观察后发现，虽然单个蚂蚁没有视力、智慧程度低、工作方式简单，但它们却有强大的执行能力和协同工作能力，依靠复杂群体的自组织协同能力发挥出超出单个个体累加的智能，是一种超个体（superorganism，又称超有机体）存在现象。蚁群是在这样的超个体案例中最有名的例子。虽然蚁群算法的严格理论基础和实际应用尚未成熟，国内外相关研究暂处于实验阶段，但这并不妨碍人们对蚁群算法的研究已经由当初单一的解决商旅问题（TSP）发展到解决调度问题、网络通信等多个方向的最优化求解应用。

目前，蚁群优化算法已广泛应用于多种求组合最优化问题，在面临路例如作业安排调度问题和路由车辆的二次分派问题上表现出了良好的性能，也经常被用来求旅行推销员问题的拟最优解。它在图表动态变化情况问题的求解上相比萤火虫算法和遗传算法具有绝对优势：蚁群算法的最大优点在于可以连续运行并适应实时变化；缺陷是在处理较大规模和复杂数据问题时，容易存在运算耗时长、收敛速度慢、得不到全局最优解等问题。

在求最优解的历次迭代中，单个蚂蚁会根据给定的规则和限定条件选择从一个城市（节点）转移到另一个城市（节点）：它必须对所有城市访问一次，而相对距离越远的城市被选中为下一个访问点的机会越少（能见度低）；相反，在两个城市（节点）边际的一边形成的信息素越浓烈，则该边际作为路径被选择的概率越大；在较短路程情况下，短时间内更多蚂蚁会在所有走过的路径上留下更多信息素，在每次迭代更新后，信息素轨迹浓度会按百分比挥发从而反馈给下一只途经的蚂蚁并影响它作出路径选择。

1 车辆路径问题

传统的车辆路径问题也叫VRP（Vehicle Routing Problem）问题，是关系到现代物联网发展过程中物流配送系统的一个关键问题，属于NP难题。一直以来，该问题也是管理科学和物流运输方面的重要课题[4]，受到国内外学者的广泛关注。

VRP问题描述如下：在一些由于经济或者地理限定的条件约束下，组织一个车队，从一个或者多个初始点出发，规定达到多个不同的地点，设计一个成本最小、路程最短的路线集，使得：① 每个城市只能被一辆车访问，只访问一次；②所有送货车辆必须从起始点出发再回到起始点；③某些特定的约束条件需要被满足。

VRP的数学模型表示如下：一共有k个客户，第i个客户的货物需求为gi，配送中心派出车辆承担运输任务，其载重为q。设gi

如果前提有约束条件用于车辆本身，即容量限制和总长限制，则称为有能力约束的车辆路径问题（Capacitated Vehicle Routing Problem）。此模型是车辆路径问题的基本模型，这类VRP问题叫作CVRP问题[5]。

设每个客户点只允许被访问一次，车辆所访问的客户点的需求总和不能超过车辆的负载能力，且总行驶的路程也不得超过其最大的行驶距离，达到用最少的车辆最短的路径完成既定任务。

。

2 可约束蚁群算法实现

2.1 算法实现方式

当前蚁群算法领域存在MPDACO局部更新和MPDACO全局更新两种方式。前者指当单个蚂蚁从一个节点到达下一个节点完成转移后就立刻更新蚂蚁通过路径时所留下的的信息素，后者是当蚂蚁遍历完所有给定节点后再更新整条路径上的信息素，不再是对所有的蚂蚁，而是仅对全局最优的蚂蚁得到的路径使用。从两种更新方式得到的结果作对比可以得出，全局信息素更新方法虽然可以加快收敛速率，但是存在着一定的缺陷和不足，易使路径更快地集中于单一解，易陷入局部最优，这些缺点限制了它的广泛传播及应用。

本文综合上述两种更新方法的优点和不足，列出了一种新的组合叠加更新方法：在路径搜索的前十次循环中，采用局部最优解更新，十次固定循环结束后，再采用全局最优解进行更新，这种更新方式可以有效避免蚁群搜索得到的路径沉入局部最优解中，有利于发现更多较优解。

2.2 算法实现步骤

根据改进的蚁群算法，将优化后的蚁群算法应用于CVRP问题的实现步骤如下：

（1）参数初始化。设迭代次数 Nc=0；每条路径上的信息素浓度Δτij（0）=c（c为常数），并且Δτij=0；随机将m个蚂蚁放置到初始点上。

（2）更新迭代（循环）次数，即Nc=Nc+1。

（3）初始化禁忌表，蚂蚁禁忌表的索引号k=1。

（4）更新蚂蚁数目k=k+1。

（5）判断路径是否在搜索热区内。按照式（a）～（f）计算出每只蚂蚁应当转移至下一个城市（节点）的概率并完成移动。

（6）当蚂蚁从i城市（节点）出发到达j城市（节点）时，对其所经过的路径上的信息素进行更新，并修改禁忌表，将禁忌表指针按照当前状况进行修改，即将新城市（节点）j置于禁忌表tabuk中。

（7）执行步骤（b）～（f），直到所有蚂蚁都找到了一条包含所有城市（节点）的可行路径解。

（8）在新生成的所有可行解中找到一条最短路径作为本次迭代中的最优路径解。

（9）判断循环次数是否小于十次，若小于十次，则对蚂蚁找到的最优路径按照本次迭代最优值进行信息素更新；若循环次数超过十次，则按照全局信息素进行更新。

（10）对所有蚂蚁经过的路径，按式（1）进行一次全局更新。

（11）循环执行（b）～（j），直到连续多次的迭代中得到的解已收敛或循环次数Nc的值已经达到给定的最大迭代次数的情况下选取当前输出值作为本次最优解。

3 实验仿真

设存在一个物流中心有4辆运输车，单辆车最大载重为1 000kg，现需要同时向7个随机分布的客户点派送货物，蚁群算法的初始化参数为：蚂蚁总数为20只，算法的最大迭代数为100次， α和β分别为1，2，信息素的挥发速度为0.75，实验重复运行100次，求得的平均结果为最终结果。同时初始时刻各边上的信息痕迹为1，残留信息的相对重要度为1，设置预见度为5。原始数据进行处理结果分析如图3所示。按本文提出的优化蚁群算法求解CVRP后的处理仿真结果如图4所示。

观测图3、图4的收敛曲线，可以知道蚁群算法优化后的结果相比之前的行车路径有大幅度优化[810]，如图5所示。针对每个收敛的点结合数据可以看出，传统蚁群算法的平均路径在迭代次数为45时可以得到最优解，而改进后的蚁群算法可以在第5次左右得到最优解，相当于收敛速度提高了近80%。

4 结语

在当今应用数学和理论计算机科学的领域中，组合优化（Combinatorial Optimization）是在一个有限的对象集中找出最优对象的一类重要课题，属于运筹学的一个重要分支。在很多组合优化问题中，穷举搜索/枚举法是不可行的。组合优化问题的特征为可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。解决组合优化问题一般采用智能算法，而这些算法都有自身的优点和缺点。组合优化的难处，主要是加进来拓扑分析，在不同的拓扑形态下，算法也需随着不同部分的约束关系作出相应调整。从目前研究来看，随着实际组合问题的变化，基本的智能算法已不能解决这类组合优化问题。

蚁群算法作为一种仿生类进化算法在求路径最优化解方面具有很好的效果。本文首先引出蚁群算法可以用于解决这一类问题，然后介绍了约束车辆路径问题，也即CVRP问题，说明了其约束模型；接着研究了基本的蚁群算法步骤，并对其中信息素更新和改进了启发因子，解析并改良了蚁群算法应用于CVRP问题的实现步骤和处理方法。

本文提出的组合叠加更新方法可有效克服传统蚁群算法收敛质量低、耗时长、易陷入局部最优解等缺陷，使蚁群算法的全局优化能力得到大幅度提高。对比实验前数据可以看出，蚁群算法找到最短路径的收敛速度比传统方法快了80%左右，确实是一种求解最短物流配送路径的有效算法。

参考文献：

[1] 陈昌敏.基于蚁群算法的物流配送路径优化研究与应用[D].成都：西华大学，2012（4）：1154.

[2] 宋留勇，王锐，周永旺，等.动态城市交通网络优化模型研究及算法设计[J].测绘科学，2011，36（1）：134136.

[3] 钟石泉，贺国光.有时间窗约束车辆调度优化的一种禁忌算法[J].系统工程理论方法应用，2005，14（6）：523527.

[4] CHAO YIMING.A tabu search method for the truck and trailer routing problem[J].Computer and Operations Research，2002，29（1）：3351.

[5] 杨中秋，张延华.改进蚁群算法在交通系统最短路径问题的研究[J].科学计算与信息处理，2009，32（8）：7678.

[6] 李松，刘兴，李瑞彩.基于混合禁忌搜索算法的物流配送路径优化问题研究[J].铁道运输与经济， 2007， 29（3）：66 69.

[7] 陶波，朱玉琴.改进的7动态规划法在车辆最短路径问题中的应用[J].重庆工学院学报， 2009，23（1）：2427.

[8] 李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社， 2001：101113.

[9] 张万旭，林健良，杨晓伟.改进的最大最小蚂蚁算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统，2005，11（4）：572576.

[10] 余玥，胡宏智.基于改进遗传算法的物流配送路径求解[J].计算机技术与发展，2009，19（3）：5255.