王玉富

(郑州测绘学校,河南 郑州 450015)



基于聚类蚁群算法的多车辆路径优化系统的实现

王玉富

(郑州测绘学校,河南 郑州 450015)

摘要：针对模型的可行性和有效性进行大量的仿真实验，首先对算法进行实现，然后通过仿真实验对不同规模的配送进行仿真配送，模型针对单车辆、多车辆、路径最优、时间最优4个方面进行仿真，其能够在较短的时间内得到优化结果，将大大提高搜索效率.

关键词：物流配送;k均值聚类算法;蚁群算法;路径优化

物流配送系统[1-3]在学术界为称为车辆路径问题(vehicle routing problem,VRP),该问题是Danizig与Ramser在1959年提出来，此后迅速在运筹学、组合数学、图论、网络分析、计算机科学等学科的专家所重视，随着互联网的发展，这一学科已经成为现在的热点问题，在生活中各个方面都体现的尤为重要.

随着互联网的快速发展，物联网也在我们生活中扮演着一个不可替代的位置，O2C就是其中一个典型的例子，在O2C系统中，物流配送是其中一个重要的环节.单配送中心的物流路径选择研究本来就是一个NP难问题，从单配送物流中心路径选择到多配送物流中心路径选择的问题难道越来越复杂.

单配送中心路径选择是配送车辆从仓库出发，对各个需要配送点进行配送，每个配送点只能配送一次.因此，在配送过程中就需要对运输要有一个合理的配送路线，也就是对配送车辆和配送对象运输先后顺序的适当选取，以此来降低物流配送过程中的时间和和其余成本.

多配送中心路径选择和单配送中心原理类似，但是其多配送中心的复杂程度成指数增加，随着配送点的增加其复杂程度还在增加，这就使得本来已经复杂的问题更加复杂化.因此，对多配送中心路径选择问题进行研究，建立一个合理的车辆调度系统，不仅可以减少各种资源的消耗(时间、路程、费用)，还可以提高运送质量以及资源利用率，而且还可以提高企业在同行业中的竞争力，竟而促进我国物流产业的发展.

近些年来，大数据概念的相关算法不断的被科学家们提出来[4-9]，对于其中的聚类算法也在物流配送中逐渐应用，聚类算法在物流配送中的选址问题、多车辆配送问题、多配送中心划分问题等都有着应用.

1　系统设计

程序采用面向对象语言C++，C++融合了3种不同的编程传统-C语言代表的过程性语言传统、C++在C语言基础上面添加的类代表的面向对象的传统以及C++模板支持的通用性编程传统，使用C++的原因之一就是为了利用其面向对象的特性，面向对象结构化编程提高了程序的清晰度、可靠性，并且易于维护.

软件主要分为四大模块：控制模块、分类模块、路径模块和动画模块.控制模块根据用户点击设定相关信息，将软件执行的顺序安排好.分类模块用数据挖掘里面的分类算法将客户根据距离的关系，将客户分成用户设定的几类.路径模块用启发式算法里面的最大最小蚂蚁算法将每一类客户的路径选择出来.动画模块采用GDI+双缓冲技术将小车配送过程动态显示在模拟软件上面.控制模块功能是控制各个模块执行流程，首先是对客户分类，然后将得到的分类动态创建路径模块线程，并行计算分类的最优路径.

图1　k-means算法流程图Fig.1　k-means algorithm flow chart

2　K均值聚类算法模型

K均值聚类算法在1967年被每个科学家J.B.MacQueen提出，此算法在工业界计算机科学界引起了巨大反响，目前最多的就是在大数据和数据挖掘学术界应用的最为广泛.其算法基本思想:随机选取k个配送点坐标当做初始聚类的质心，然后根据相似性将每个配送点和质心进行对比，将自己加入到和自己最相似的那个聚类中心所在的类，一次迭代完成更新质心，当质心不再改变的时候，分类基本完成.聚类算法对大规模点分类有显著的效果，大大减少了由纯粹蚁群算法得到的多车辆路径的时间，提高了搜索效率.

2.1　流程描述

K均值聚类算法的具体描述如下：

1)输入一个指定的K值，然后随机选取K个元素，作为K个类的质心;

2)计算出各个元素分别到K个质心的距离，然后加入到离其最近的质心当中;

3)重新计算K个类的质心;

4)若质心在变化，继续第2步骤，否则停止，输出聚类结果;

算法流程图1所示.

2.2　性能分析

K均值聚类算法根据欧几里得距离得到的误差的平方函数值最小的k个划分，对于集合中的元素能够很好的分类，特别对于大数据有很好的支持，具有较高的效率，算法复杂度为O(nkt)，其中感谢t表示循环次数；k表示K个聚类；n表示集合中的元素数目.

基于K均值聚类算法有很多变种，一类是改变相似度的公式进行的改变，还有一类是针对自动聚类得到k值得改进，两种算法在不同领域应用的极为广泛.

3　蚁群算法的模型

3.1　蚂蚁系统模型

蚂蚁系统是最基本的蚂蚁算法，其搜索过程如下：设蚂蚁的大小为m，配送点个数为n，开始时刻m只蚂蚁被放在配送中心，τij表示配送点i到配送点j路径上信息素的大小，在开始时刻被设置为固定常量，当客户从配送点i选择配送点j其概率为：

(1)

其中:τij表示循环中配送点i、j所在路径上的信息素强度;ηij表示从配送点i到配送点j的可见度，本文中取ηij=1/dij,dij为配送点i到配送点j的距离;α、β表示权重系数，分别表示蚂蚁在运动过程中所积累的信息素及期望信息在蚂蚁选择路径中所起的不同作用; Γ表示禁忌表，记录了当前蚂蚁已经走过配送点的集合.

配送点i到配送点j上面的信息素结果由新增加的信息素加上残留的信息素，其更新的公式为：

(2)

其中ρ为信息素挥发程度系数，范围0<ρ<1.

3.2　算法流程描述

最大最小蚁群算法的具体实现步骤如下：

1)参数初始化.事件t=0,循环次数N=0,最大循环次数NM，将当前分配的数量为m的蚁群放置在当前配送中心，然后初始化信息素τij=C，Δτij=0;

图2　最大最小蚁群算法流程图Fig.2　The largest minimal ant colony algorithm flow chart

图3　30车辆路径最优运行图Fig.3　The optimal running 30 vehicle routing

配送点个数2辆车耗时/s3辆车耗时/s4辆车耗时/s100.0619620.0573390.058893500.5075790.4926050.5127141003.9651551.8134061.18203115010.5333546.1665344.31460419018.2359027.9633715.153526

2)计算每个蚂蚁选择下一配送点的概率.根据式(1)计算得到每个蚂蚁当前配送点到下一未经过的各个配送点的概率;

3)人工蚂蚁自动选择下一配送点.根据第2步计算得到的概率，通过轮盘赌算法计算出每只蚂蚁下一步经过的配送点;

4)更新当前各个蚂蚁各自的禁忌列表.将刚经过的配送点加入到各自的禁忌列表里面，防止重复经过配送点;

5)如果没送点没有遍历完成转到第4步，否则计算出各个蚂蚁的所路径的长度;

6)使用式(2)更新全局信息素;

7)循环一次，N=N+1;

8)若循环没有结束转到第2步，否则输出最优路径.

算法流程图下图2所示.

4　实例计算与参数分析

从表1可以看出，在配送规模很小的情况下，三种情况耗时基本上差不多，但是随着配送规模的变大，车辆越多耗时越小，反之相反.现实生活中当配送规模很大的情况，此模型能够很好的融入现实生活解决现实问题.

4.1　多车辆路径最优

4.1.1多车辆运行.以30车辆数据为例：仓库位置：(264，357).

配送点位置：

(174，219)(136，319)(156，458)(252，501)(364，488)

(422，391)(375，305)(221，308)(212，380)(298，426)

(319，382)(302，252)(384，250)(455，334)(429，527)

(398，554)(350，557)(279，472)(226，448)(195，525)

(128，531)(101，448)(126，398)(171，286)(116，260)

(85，329)(238，245)(289，319)(340，223)(302，187)

(210，204)

车辆1配送长度：1252,车辆1配送路径：

0->11->2->22->23->24->12->3->10->9->8->7->19->20->21->1

车辆2配送长度：1400,车辆2配送路径：

0->13->14->25->27->28->26->15->29->30->16->17->18->6->5->4

配送路线图像如图3所示.

从图3可以看出，通过聚类算法获取得到的两个类在位置区域上面有个明显的位置差别，2辆车同时从仓库出发，按照各自的路线运行，红色的代表车辆1运行路线，黄色的路线代表车辆2运行路线.2辆车按照各自的运行路线返回到仓库.

4.1.2多车辆堵塞运行.仓库位置：(244，338).

配送点位置：

(233，211)(162，241)(124，322)(125，375)(158，418)

(271，455)(323，458)(406，423)(419，353)(387，278)

(217，288)(195，320)(196，360)(215，395)(269，406)

(318，394)(334，373)(358，315)(329，257)(303，253)

(276，294)(285，337)(377，197)(408，220)(430，275)

(442，315)(474，385)(464，420)(422，501)(370，460)

(372，386)(435，404)(438，475)(488，513)(449，561)

(385，558)(339，488)(289，511)(337，546)(270，568)

(232，518)(220，463)(193，446)(174，489)(193，560)

(161，545)(118，530)(111，494)(125，444)(118，405)

(75，379) (79，307) (94，274) (114，224)(138，191)

(127，265)(155，311)(151，358)(209，254)(185，194)

(251，163)(274，169)(278，221)(327，180)(332，148)

(410，151)(445，183)(463，263)(479，319)(499，395)

未堵塞情况：

车辆1配送长度：1700,车辆1配送路径：

0->22->18->10->25->68->24->67->66->23->64->65->62->61->60->55->54->2->56->53->52->57->3->51->50->4->58->13->12->11->59->1->63->20->19->21

车辆2配送长度：1800,车辆2配送路径：

0->16->17->31->9->26->69->27->70->28->32->8->30->29->33->34->35->36->39->37->7->38->40->41->45->46->47->48->49->5->43->44->42->6->15->14

随机堵塞几条路径情况：

30到29堵塞、54到2堵塞、23到64堵塞、43到44堵塞17

车辆1配送长度：1766,车辆1配送路径：

0->22->18->10->25->68->24->67->66->23->65->64->62->61->1->63->20->19->21->11->59->2->60->55->54->56->53->52->51->50->4->58->3->57->12->13

车辆2配送长度：1846,车辆2配送路径：

图4　60车辆路径最优运行堵塞图Fig.4　The optimal running 60 vehicle routing block diagram

0->16->17->31->8->32->9->26->69->27->70->28->33->29->34->35->36->39->30->7->37->38->40->41->44->45->46->47->48->49->5->43->42->6->15->14

配送效果图如5.6所示.

从图4可以看出，车辆1开始按照红色路线运行，当堵塞之后，得到系统更新的路线就按照蓝色的路线配送未走过的路线.车辆2和车辆1一样，先按照黄色的路线运行，堵塞的时候停止运行，更新路线之后从当前位置按照绿色的路径运行.对于时间最优情况和本情况类似，不做介绍.

4.2　多车辆时间最优

4.2.1多车辆运行.以30车辆为例：仓库位置：(285，356).

配送点位置：

(230，253)(173，302)(160，395)(190，471)(256，512)

(332，510)(414，454)(422，376)(380，302)(297，295)

(235，332)(227，382)(256，426)(293，434)(325，408)

(332，381)(348，287)(370，246)(401，245)(480，323)

(495，460)(480，528)(381，582)(260，584)(204，556)

(162，517)(130，459)(109，365)(118，282)(190，191)

(261，180)(290，232)(351，181)(300，136)(193，139)

(143，179)(155，256)(97，220) (74，275) ( 65，379)

(88，459)

车辆1运行时间：1119,车辆1运行路线：

0->10->32->1->2->37->29->39->38->36->30->35->31->34->33->18->19->9->17

车辆2运行时间：1636,车辆2运行路线：

0->11->12->3->28->40->41->27->4->26->25->24->5->6->23->22->21->7->20->8->16->15->14->13

图5　60车辆时间最优运行图Fig.5　The optimal running 60 vehicles

运行效果如图5所示.

4.2.2多车辆堵塞运行.仓库位置：(255，340).

配送点位置：

(192，220)(147，282)(137，360)(163，412)(250，462)

(385，447)(413，395)(372，322)(296，292)(220，299)

(205，345)(243，403)(286，412)(318，403)(335，289)

(389，248)(431，269)(475，358)(477，453)(443，519)

(401，550)(330，551)(206，532)(167，504)(101，434)

(80，355) (100，258)(125，194)(208，161)(268，192)

(250，239)(352，185)(328，132)(291，124)(331，216)

(439，155)(469，171)(502，219)(502，285)(436，334)

(370，360)(317，340)(355，451)(309，480)(273，529)

(176，461)(132，527)(207，582)(430，591)(481，566)

(508，417)(472，411)(423，459)(368，499)(354，560)

(341，599)(282，593)(103，313)(62，312)(55，370)

(78，453) (91，523) (107，498)

堵塞前情况：

车辆1运行时间：470.车辆1运行路线如下：

0->11->3->4->25->61->60->26->59->58->2->27->28->29->1->10

车辆2运行时间：663. 车辆2运行路线如下：

0->42->15->8->41->7->52->51->18->40->39->38->37->36->17->16->35->32->33->34->30->31->9

车辆3运行时间：742,车辆3运行路线：

0->13->14->44->54->43->6->53->19->20->50->49->21->55->22->56->57->45->48->23->24->47->62->63->46->5->12

随机堵塞路线：

44到 54堵塞、58 到 2堵塞、35 到 32堵塞

车辆1运行时间：478.车辆1运行路线如下：

0->11->3->4->25->61->60->26->59->58->27->28->29->1->2->10

车辆2运行时间：679. 车辆2运行路线如下：

0->42->15->8->41->7->52->51->18->40->39->38->37->36->17->16->32->35->33->34->30->31->9

车辆3运行时间：748.车辆3运行路线如下：

0->13->14->44->43->6->53->19->20->50->49->21->54->22->55->56->57->45->48->23->24->47->62->63->46->5->12

本文对大规模配送点多车辆的问题进行研究，但没有对蚁群大小、启发信息和挥发因子进行研究，只是将前人经验借鉴直接使用，对于这些参数只有进行理论性的探索加上实际的测试才能得到比较准确的结果.其次本文使用的是最大最小蚁群算法，没有对其进行改进优化，还有很多地方有待提高.

参考文献:

[1]Alberto Colony,Marco Dorigo.Vittorio Maniezzo.Distributed Optimization by Ant Colonies[C]//Elsevier:European conference on artificiaI Life,France,1991:134-142.

[2]Marco Dorigo,Gianni Di Caro.Ant Algorithms for Discrete Optimization[J].Artificial Life,1999,5(3):137-172.

[3]MarcoDorigo.Ant colonies for the traveling salesman problem [J].Bio systems,1997,43:73-81.

[4]Zhuang Hua-liang,Low Kay-soon, You Wei-Yun. Multichannel pulse-coupled-neural-network-based color image segmentation for object detection[J].IEEE Transactions on Industrial Electronics,2012,59(8):3299-3308.

[5]Ji Ze-xuan,Xia Yong,Chen Qiang.Fuzzy c-means clustering with weighted image patch for image segmentation[J].Applied Soft Computing,2012,12(6):1659-1667.

[6]Mignotte Max.A de-texturing and spatially constrained K-means approach for image segmentation[J].Pattern Recognition Letters,2011,32(2):359-367.

[7]叶有时,唐林波,赵保军.一种基于聚类的深空红外多目标快速检测算法[J].电子与信息学报,2011,33(1):77-84.

[8]Chen Kang-Lin and Lorenz D A.Image sequence interpolation based on optical flow, segmentation,and optimal control[J].IEEE Transactions on Image Processing,2012,21(3):1020-1030.

[9]Wang Ru,Zhao Chun-jiang,and Guo Xin-yu.Improved cam-shift algorithm based on frame-difference method for video′s auto tracking[J].International Journal of Digital Content Technology and its Applications,2012,19(6):137-144.

责任编辑：时凌

Implementation of Multiple Vehicle Routing Optimization System

Based on Ant Colony Clustering Algorithm

WANG Yufu

(Zhengzhou School for Surveying and Mapping,Zhengzhou 450015,China)

Abstract：A large number of simulations are made for the feasibility and effectiveness of the model. First,the algorithm is achieved,and then distribution on different size distribution is made through the simulations. The model simulates from four aspects, namely,multi-vehicle,single vehicle,the most optimal path,and the most optimal time, which can get the optimization results in a relatively short period of time and will greatly improve the search efficiency.

Key words：logistics and distribution;k-means clustering algorithm;ant colony algorithm;path optimization

DOI:10.13501/j.cnki.42-1569/n.2015.06.024 10.13501/j.cnki.42-1569/n.2015.06.023

文章编号：1008-8423(2015)02-0210-05 1008-8423(2015)02-0205-05

作者简介：李如平(1973- )，男，硕士，副教授，主要从事计算机应用、物联网技术的研究. 余基映(1987- )，女，硕士，主要从事并行计算研究.

基金项目：安徽省科技攻关计划项目(13011031029、1201a0301008)；安徽省厅级自然科研项目(KJ2011B069、KJ2013Z105) ；安徽省对外科技合作计划项目(1403062028).

收稿日期：2015-04-24. 2015-04-16.

中图分类号：TN961

文献标志码：A