改进的蚁群算法在车辆配送路线优化中的应用研究

计算机伎术应用・ｔｈｅ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｔｅｃｈｎｏｌｏｇｙ　改进的蚁群算法在车辆配送路线优化中的应用研究　

由于传统的蚁群算法在寻找　最优解时的处理过程较慢，并且　还会时常出现停滞的现象，因此，　本文提出了改进蚁群算法的措施。　丈中主要是通过建立候选城市数　据表，并且在蚁群算法的状态转　移规则中增加了节约量的启发信　息。通过实际案例加以验证，结　果表明改进后的蚁群算法能够全　面提高企业车辆配送效率。　【关键词】蚁群算法车辆配送路线优化状态　转移规则　蚁群算法（－Ａｎｔ　Ｃｏｌｏｎｙ　ＯｒＩｔｉｍｉｚａｔｉｏｎ），　通常是用来在图中查找最佳路径的机率型算　法。文中通过改进后的蚁群算法对车辆配送路　线进行全面的优化。　１蚁群算法在车辆路径选择中的策略优　化　在蚁群算法处理过程中，蚂蚁所走的各　个位置都需要进行事前的计算，首先需要定位　各条线路的概率值Ｐ，然后再对各个线路进行　择优处理。因此，在原有的算法中选择出最佳　线路是很耗时间的。为了能够节约路径的选择　时间，因此，对其策略进行改进。　（１）候选城市节点信息的优化。　从传统的ＶＲＰ中我们可以发现，当车辆　进入ｉ城市之后需要确定下一个最优城市ｉ时，　那么ｊ就是属于离ｉ最近的城市了。但是在传　统的蚁群算法中，当蚂蚁到达ｉ城市之后，就　从其未走过的城市节点中一一对比来发现ｉ城　市节点，那么这样一一对比的方式就会消耗很　多的计算时间，工作效率较低。从这里我们可　以看出ｍ只蚂蚁选择下一个城市配送点时需　要对比的循环次数是ｍ＊ｎ＊（ｎ＋１）／２，完成一次　操作的复杂度是Ｏ（ｍ・　）。　从上面传统蚁群算法中我们可以发现，蚂　蚁所要经过的城市是属于离当前城市距离最近　的，假如我们选用了Ｃ个节点列为本次的候选　城市节点时。此时，ｍ只蚂蚁选择下一个城市　配送节点时需要对比的节点循环次数是ｍ＊ｃ（ｎ—　ｃ）＋ｍ＊ｃ（ｃ＋１）／２，一般情况下ｃ的取范围是城市　节点总数目的八分之一或者六分之一，那些，　我们可以计算出现在的复杂度是Ｏ（ｍ・　）。从新　算法的复杂度中我们能够发现，蚂蚁ｍ值与　城市１１值的数量在不断地扩大时，可以很明显　文／吴海花　地发现新的蚁群算法具有更快的处理速度和更　短的计算时间。　（２）对状态转移规则的优化。　（ａ）增加节省量启发信息。　假如当城市配送中心节点Ｐ需要向节点ｉ　和＿ｉ这两个城市配送东西，那么就需要分别向　这两个节点城市各派出一辆货车，路程总长为　２・（　＋　），作为第一种配方案。如果可以装　完当前这批货，那么车辆行走路线是这样的：　

首先从配送中心出发，先是到达到ｉ城市，再　达到Ｊ城市，然后再返回配送中心。路程总长　为ｄ　＋　＋　是作为第二种配送方案。通过对　第一种与第二种配送路线方案的比较后可以得　出，节约量　＝ｄｐ　＋　一　。　（ｂ）状态转移规则。　尽量避免启发信息出现过大，避免蚂蚁　重复选择其它节点的线路。因此在转移规则运　行之前就需要增加一定的随机量，让蚂蚁根据　一定随机值来确定一个目标城市节点。具体改　进措施如下：　Ｊ　ａｒｇｍａｘ剧¨嘲（ｆ】（【　。Ｊ（ｆ）］　［，７ｆ．　）　］）如果ｑ≤ｑ０，　Ｉ，其它　（１）　（ｆ）＝　ｓ￣ａｌｌｏｗｅｄｋ（ｉ）　０　若ｓｅａｌｌｏｗｅｄｋ（ｆ）否则（２）　ｆ）　南　ｓ　（ｆ））　南　∥　３）　当蚂蚁在进行下一个状态选择时，首先　会产生一个随机数ｑ，如果当ｑ的值小于ｑＯ时，　那么蚂蚁就会通过选择［　（ｆ）］　［　．　）】　启发信　息作为最大的路径；否则就会通过式２来计算　出相应的概率，然后再通过赌轮法来确定下一　个侯选城市的节点。　２改进蚁群算法流程　第一步：先进行初始化参数。取得配送　中心这个节点位置与客户所在城市的节点位置　信息，求这两个城市节点的距离，并且将各个　城市节点建立起各自的候选城市节点信息表。　然后将蚂蚁数量ｍ与城市节点数相等即可，　出现的循环最大次数为　。　第二步：将蚂蚁安排到配送中心，同时　将蚂蚁的载货重量初始化为０。　第三步：各个节点的路径信息素开始运　动。根据公式３来搜索路径并进行信息素挥发　处理。　ｆ．，（ｆ＋１）＝（１一ｐ）ｒｏ（ｆ）　第四步：配送路径的选择。首先将各只蚂　１９２・电子技术与软件工程Ｅｌｅｃｔｒｏｎｉｃ　Ｔｅｃｈｎｏｌｏｇｙ＆Ｓｏｆｔｗａｒｅ　Ｅｎｇｉｎｅｅｒｉｎｇ　蚁设为ｋ，假设每只蚂蚁所达到的目标节点都　是ｉ，那么就会从ｉ的候选城市表中选择出符　合蚂蚁载重要求的城市节点，根据公式１、２　来计算出下个将要达到的城市节点Ｊ，然后将　城市节点ｉ移入蚂蚁ｋ的已搜节点表中去，同　时还需要增加蚂蚁路由的路径长度。假设候选　城市中无法达到现有蚂蚁载重量需求的城市，　那么就会返回到第三步。　，，Ｊ　ａｒｇｍａｘｊｅａＵｏｗｅｄ，（ｉ）　，Ｊ（ｆ）１　，（ｆ　｝如果ｑ≤ｑｏ，　１Ｊ其它　ｌ　，（ｆ）］　［　，　（明　咖）＝｛　ｌ０　若ｓ∈ａｌｌｏｗｅｄ　（ｆ）否则　第五步：释放局部信息素。在各次循环　中，每只蚂蚁需要进行更新各自的信息素，当　在某个ｔ时刻蚂蚁ｋ经过（ｉ，ｉ）边时，那么该　只蚂蚁需要更新（ｉ　）边的规则并释放相关的信　息素。　（ｔ＋１）＝（１一ｐ）ｒｇ（ｔ）＋Ｐ・ｆｏ　第六步：检查蚂蚁的已搜索节点表长度　是否小于客户节点的数目，假如是小于就会跳　转到第三步；否则就会跳转至第七步；　第七步：在本次循环搜索节点过程中，　经过Ｎ次的２－ｏｐｔ变换操作后才能够确定最　优的路径，那么当变换一次后就能够满足装　载量的约束，同时与厶　，（ｒ）进行比较，如果　厶　，（ｆ）＞Ｌ２～　（　），那么就上　（ｆ）＝Ｌ２一　，（　），　并且将最优路径表也进行同步的更新处理。　第八步：释放全局信息素。当全部蚂蚁　走完所有的节点之后，需要确定一只走过路径　最长的蚂蚁和另一只走过最短路径的蚂蚁，同　时还要释放信息素。　ｒｕ（ｔ＋１）＝（１一　）　（ｆ）＋　・￣ｒｏ（ｔ）　

Ｉ＿　矿（ｆ，　）∈Ｌｂ　Ｏ）　：｛　。…　ｌ

＿　（ｆ，　）∈Ｌｗｏｒ，，（ｆ）　Ｉ上　（ｆ）一…　一　第九步：需要进行自适应参数的调整，　对ｑｏ，Ｑ，Ｐ　０分别进行相应的调整。　

‘　

Ｑ（ｆ）＝Ｑｏ（１＋ｔ），　≤ｒ　（川）：　（　），若。・　（　）≥　ｍ　Ｉ　第十步：当前循环次数ｔ与最大循环次数　ｔｈｅ　Ａｐｐｌｉｃａｔｉｏｎ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｔｅｃｈｎｏｌｏｇｙ・计算机技术应用　表１：Ａ－ｎ４５一ｋ６的客户分布与需求量　鸦　０　Ｉ　２　３　４　５　６　７　８　９　３ｌ刀　ｌｌ田　９６　８ｌ　位　７ｌ　４８　９１，１７　４９　嗍　Ｏ　ｌ９　２　ｌ２　２ｏ　６　ｌ７　８　ｌ４　２　序‘ｉ｝　ｌ０　ｌｌ　ｌ２　ｌ３．　１４　ｌ５　ｌ６　ｌ７　ｌ８　ｌ９　１１．１６　７　ｌ　ｌ　黼　蚓７　笼　曩ｌ３　８　５　７　兹　ｌ４　ｌ７　筋　ｌ５　２ｌ　２　序Ｉｉ｝　∞　２ｌ　∞　２５　２７　２８　２９　矾　惭ｌ　４０７２　１，４４　印　ｌ　蝴　旎４３　脯　１０　２０　６　２ｌ　ｌＯ　６　ｌ３　２ｌ　：｝４　序‘胃｝　∞　３Ｉ　３ｃ２　３３　３４　３６　３７　３８　剪　１，ｍ　５３ｊＩ６　螂　７　２３５　３ｃ２　嬲　ｌｌ　Ｉ６　８　ｌｌ　ｌｌ　兹　ｌ７　２２　ｌ７　８　序‘ｉ｝　４０　４Ｉ　４２　４３　４４　９．１ｌ　鲢ｌ６　９０．鲳　３嚣３ｌ　矗碧　■剜闷星　５　３　ｌ８　ｌ２　

图１：ＶＲＰ车辆调度行驶路径图　ｆ　进行比较，如果大于就跳出本次循环；否　则将已搜索节点信息表全部清空，并将ｍ只　蚂蚁还原到配送中心的起始位置，同时还要跳　转至第二步，不断重复这样的过程，最终求得　最优的配送路径。　３改进后的蚁群算法在车辆配送路线优　化中的应用　因为Ｇ２平台广泛的应用在车辆调度工作　方面，Ｇ２平台是属于美国Ｇｅｎｓｙｍ公司设计　出来的实时智能管理软件。这里以Ｇ２平台作　为车辆调度应用基础，全面优化企业车辆配送　调度服务，提高工作效率，以最快的速度将货　物送达客户手中。假设客户所在城市的分布与　需求量和Ａ．ｎ４５一ｋ６分布信息是一致的（如表　１）。表中序号为０的节点是属于配送中心，　其它各个节点是属于客户所在城市的节点位　置，假设各个车辆的载重量是１００。　系统应用改进后的蚁群算法计算出来的　车辆行驶路径如图１所示：　通过改进蚁群算法求得的最优解是：　

０．＞１４一＞３５－＞３１．＞３８．＞２一＞２５．＞ｌ５一＞Ｏ．＞１２．＞３９．＞３６一　＞４２一＞４一＞ｌ６－＞２２一＞９一＞０－＞１－＞６．＞２４一＞３７一＞２７一＞２６一　＞０－＞４４－＞３４－＞１９一＞３０一＞４０－＞ｌ　１－＞１７．＞１８．＞０一＞２９．　＞４３－＞ｌ３－＞７－＞２８一＞２３．＞Ｏ．＞３２一＞２０．＞５．＞２１．＞３３．　＞４１．＞８一＞１０一＞３．＞０　

车辆的具体调度路径安排如下：　

车辆１：０－＞１４一＞３５一＞３１－＞３８￣２・＞２５－＞１５－＞ｏ　行驶长度：１５７　２０９　车辆２：０－＞１２．＞３９．＞３６－＞４２－＞４一＞１６一＞２２．＞９．＞ｏ　行驶长度：Ｉｇｌ　ｇ１９　车辆３：０－＞卜＞６－＞２４－＞３７－＞２７．＞２６．＞０　行驶长度：１　１２．５０３　车辆４：０－＞４４，＞３４一＞１９－＞３０－＞４０－＞１１．＞１７一＞１８－＞０　行驶长度：１７３　６０４　车辆５：Ｏ－＞２９一＞４３．＞ｌ３－＞７－＞２８－＞２３．＞０　行驶长度：１　１４　７７３　车辆６：Ｏ－＞３２．＞２０．＞５－＞２１－＞３３一＞４１．＞８．＞１０．＞３－＞０行驶长度：２０４　９７３　行驶的总长度为：９４４　５８　

从上面的结果中我们能够发现，车辆调　

度系统的精度已经能够满足用户的基本需求，　所以通过车辆调度模似系统能够更好地优化车　辆调度工作，全面降低货运费用，有效地提高　货物运送质量，节约成本，而且还可以为客户　提供更好的服务。　

参考文献　［１］Ｃｏ１　０ｆｎｉ　Ａ，Ｄｏｒｉ　ｇｏ　Ｍ，Ｍａｎｉｅｚｚｏ　Ｖ．Ａｎ　ｉｎｖｅｓｔｉｇａｔｉｏｎ　ｏｆ　ｓｏｍｅ　ｐｒｏｐｅｒｔｉｅｓｏｆ　ａｎ　ａｎｔ　ａ１ｇｏｒｉｔｈｍ［Ｃ】Ｉｎ：Ｐｒｏｃ　ｏｆ　ｔｈｅ　Ｐａｒａ１　ｌｅｌ　Ｐｒｏｂｌｅｍ　Ｓｏ１ｒｉｎｇ　ｆｒｏｍ　Ｎａｔｔｉｒｅ　Ｃｏｎｆｅｒｅｎｃｅ（ＰＰＳＮ　９２），Ｂｒｕｓ　ｓｅｌ　ｓ，Ｂｅｌｇｉｕｍ：　Ｅ１　ｓｅｖｉｅｒ　Ｐｕｂｌｉ　ｓｈｉｎｇ，１９９２：５０９—５２０．　［２】陈嵘，金以慧．Ｇ２智能实时系统平台的开　发和应用【Ｊ】．化工自动化及仪表．１　９９８，　２５（５）：３３－３６．　［３］李士勇．蚁群算法的改进及应用研究进　展［Ｊ］．计算机测量与控制，２００３，１１（１２）：　９１１－９１　７．　［４】孙玉涛，毕殿杰．融合遗传算法和蚁群算　法动态网格任务调度算法研究ｆＪ］．工业　控制计算机，２Ｏ１１（０２）．　［５］林芳．遗传算法在网格任务调度的应用研　究［Ｊ］．计算机仿真，２０１１（１１）．　［６】白继中，师彪，冯民权，周利坤．自适应　人工蚁群算法在水资源优化配置中的应用　［Ｊ】．沈阳农业大学学报，２０ｌ１（０４）．　［７］张新丽，范蓉．改进的蚁群聚类算法在电　信ＣＲＭ客户细分中的应用［Ｊ】．移动通信，　２０ｌ１（２２）．　［８】刘长平，叶春明，唐海波．Ｊｏｂ—Ｓｈｏｐ调度　问题的量子蚁群算法求解［Ｊ］．计算机应　用研究，２０１１（１２）．　［９】张潇，王江晴．混合蚁群算法在车　辆路径问题中的应用［Ｊ】．计算机工　程，２Ｏ１１（２４）．　［１０】郭乘涛，汪志斌．应用混合蚁群算法求　解并行批处理机组批与调度问题…．上　海交通大学学报，２０１　０（０８）．