基于聚類蟻群算法的多車輛路徑優(yōu)化系統(tǒng)的實(shí)現(xiàn)

王玉富

(鄭州測(cè)繪學(xué)校,河南 鄭州 450015)

?

基于聚類蟻群算法的多車輛路徑優(yōu)化系統(tǒng)的實(shí)現(xiàn)

王玉富

(鄭州測(cè)繪學(xué)校,河南 鄭州 450015)

摘要：針對(duì)模型的可行性和有效性進(jìn)行大量的仿真實(shí)驗(yàn)，首先對(duì)算法進(jìn)行實(shí)現(xiàn)，然后通過仿真實(shí)驗(yàn)對(duì)不同規(guī)模的配送進(jìn)行仿真配送，模型針對(duì)單車輛、多車輛、路徑最優(yōu)、時(shí)間最優(yōu)4個(gè)方面進(jìn)行仿真，其能夠在較短的時(shí)間內(nèi)得到優(yōu)化結(jié)果，將大大提高搜索效率.

關(guān)鍵詞：物流配送;k均值聚類算法;蟻群算法;路徑優(yōu)化

物流配送系統(tǒng)[1-3]在學(xué)術(shù)界為稱為車輛路徑問題(vehicle routing problem,VRP),該問題是Danizig與Ramser在1959年提出來，此后迅速在運(yùn)籌學(xué)、組合數(shù)學(xué)、圖論、網(wǎng)絡(luò)分析、計(jì)算機(jī)科學(xué)等學(xué)科的專家所重視，隨著互聯(lián)網(wǎng)的發(fā)展，這一學(xué)科已經(jīng)成為現(xiàn)在的熱點(diǎn)問題，在生活中各個(gè)方面都體現(xiàn)的尤為重要.

隨著互聯(lián)網(wǎng)的快速發(fā)展，物聯(lián)網(wǎng)也在我們生活中扮演著一個(gè)不可替代的位置，O2C就是其中一個(gè)典型的例子，在O2C系統(tǒng)中，物流配送是其中一個(gè)重要的環(huán)節(jié).單配送中心的物流路徑選擇研究本來就是一個(gè)NP難問題，從單配送物流中心路徑選擇到多配送物流中心路徑選擇的問題難道越來越復(fù)雜.

單配送中心路徑選擇是配送車輛從倉(cāng)庫(kù)出發(fā)，對(duì)各個(gè)需要配送點(diǎn)進(jìn)行配送，每個(gè)配送點(diǎn)只能配送一次.因此，在配送過程中就需要對(duì)運(yùn)輸要有一個(gè)合理的配送路線，也就是對(duì)配送車輛和配送對(duì)象運(yùn)輸先后順序的適當(dāng)選取，以此來降低物流配送過程中的時(shí)間和和其余成本.

多配送中心路徑選擇和單配送中心原理類似，但是其多配送中心的復(fù)雜程度成指數(shù)增加，隨著配送點(diǎn)的增加其復(fù)雜程度還在增加，這就使得本來已經(jīng)復(fù)雜的問題更加復(fù)雜化.因此，對(duì)多配送中心路徑選擇問題進(jìn)行研究，建立一個(gè)合理的車輛調(diào)度系統(tǒng)，不僅可以減少各種資源的消耗(時(shí)間、路程、費(fèi)用)，還可以提高運(yùn)送質(zhì)量以及資源利用率，而且還可以提高企業(yè)在同行業(yè)中的競(jìng)爭(zhēng)力，竟而促進(jìn)我國(guó)物流產(chǎn)業(yè)的發(fā)展.

近些年來，大數(shù)據(jù)概念的相關(guān)算法不斷的被科學(xué)家們提出來[4-9]，對(duì)于其中的聚類算法也在物流配送中逐漸應(yīng)用，聚類算法在物流配送中的選址問題、多車輛配送問題、多配送中心劃分問題等都有著應(yīng)用.

1　系統(tǒng)設(shè)計(jì)

程序采用面向?qū)ο笳Z言C++，C++融合了3種不同的編程傳統(tǒng)-C語言代表的過程性語言傳統(tǒng)、C++在C語言基礎(chǔ)上面添加的類代表的面向?qū)ο蟮膫鹘y(tǒng)以及C++模板支持的通用性編程傳統(tǒng)，使用C++的原因之一就是為了利用其面向?qū)ο蟮奶匦?，面向?qū)ο蠼Y(jié)構(gòu)化編程提高了程序的清晰度、可靠性，并且易于維護(hù).

軟件主要分為四大模塊：控制模塊、分類模塊、路徑模塊和動(dòng)畫模塊.控制模塊根據(jù)用戶點(diǎn)擊設(shè)定相關(guān)信息，將軟件執(zhí)行的順序安排好.分類模塊用數(shù)據(jù)挖掘里面的分類算法將客戶根據(jù)距離的關(guān)系，將客戶分成用戶設(shè)定的幾類.路徑模塊用啟發(fā)式算法里面的最大最小螞蟻算法將每一類客戶的路徑選擇出來.動(dòng)畫模塊采用GDI+雙緩沖技術(shù)將小車配送過程動(dòng)態(tài)顯示在模擬軟件上面.控制模塊功能是控制各個(gè)模塊執(zhí)行流程，首先是對(duì)客戶分類，然后將得到的分類動(dòng)態(tài)創(chuàng)建路徑模塊線程，并行計(jì)算分類的最優(yōu)路徑.

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

2　K均值聚類算法模型

K均值聚類算法在1967年被每個(gè)科學(xué)家J.B.MacQueen提出，此算法在工業(yè)界計(jì)算機(jī)科學(xué)界引起了巨大反響，目前最多的就是在大數(shù)據(jù)和數(shù)據(jù)挖掘?qū)W術(shù)界應(yīng)用的最為廣泛.其算法基本思想:隨機(jī)選取k個(gè)配送點(diǎn)坐標(biāo)當(dāng)做初始聚類的質(zhì)心，然后根據(jù)相似性將每個(gè)配送點(diǎn)和質(zhì)心進(jìn)行對(duì)比，將自己加入到和自己最相似的那個(gè)聚類中心所在的類，一次迭代完成更新質(zhì)心，當(dāng)質(zhì)心不再改變的時(shí)候，分類基本完成.聚類算法對(duì)大規(guī)模點(diǎn)分類有顯著的效果，大大減少了由純粹蟻群算法得到的多車輛路徑的時(shí)間，提高了搜索效率.

2.1　流程描述

K均值聚類算法的具體描述如下：

1)輸入一個(gè)指定的K值，然后隨機(jī)選取K個(gè)元素，作為K個(gè)類的質(zhì)心;

2)計(jì)算出各個(gè)元素分別到K個(gè)質(zhì)心的距離，然后加入到離其最近的質(zhì)心當(dāng)中;

3)重新計(jì)算K個(gè)類的質(zhì)心;

4)若質(zhì)心在變化，繼續(xù)第2步驟，否則停止，輸出聚類結(jié)果;

算法流程圖1所示.

2.2　性能分析

K均值聚類算法根據(jù)歐幾里得距離得到的誤差的平方函數(shù)值最小的k個(gè)劃分，對(duì)于集合中的元素能夠很好的分類，特別對(duì)于大數(shù)據(jù)有很好的支持，具有較高的效率，算法復(fù)雜度為O(nkt)，其中感謝t表示循環(huán)次數(shù)；k表示K個(gè)聚類；n表示集合中的元素?cái)?shù)目.

基于K均值聚類算法有很多變種，一類是改變相似度的公式進(jìn)行的改變，還有一類是針對(duì)自動(dòng)聚類得到k值得改進(jìn)，兩種算法在不同領(lǐng)域應(yīng)用的極為廣泛.

3　蟻群算法的模型

3.1　螞蟻系統(tǒng)模型

螞蟻系統(tǒng)是最基本的螞蟻算法，其搜索過程如下：設(shè)螞蟻的大小為m，配送點(diǎn)個(gè)數(shù)為n，開始時(shí)刻m只螞蟻被放在配送中心，τij表示配送點(diǎn)i到配送點(diǎn)j路徑上信息素的大小，在開始時(shí)刻被設(shè)置為固定常量，當(dāng)客戶從配送點(diǎn)i選擇配送點(diǎn)j其概率為：

(1)

其中:τij表示循環(huán)中配送點(diǎn)i、j所在路徑上的信息素強(qiáng)度;ηij表示從配送點(diǎn)i到配送點(diǎn)j的可見度，本文中取ηij=1/dij,dij為配送點(diǎn)i到配送點(diǎn)j的距離;α、β表示權(quán)重系數(shù)，分別表示螞蟻在運(yùn)動(dòng)過程中所積累的信息素及期望信息在螞蟻選擇路徑中所起的不同作用; Γ表示禁忌表，記錄了當(dāng)前螞蟻已經(jīng)走過配送點(diǎn)的集合.

配送點(diǎn)i到配送點(diǎn)j上面的信息素結(jié)果由新增加的信息素加上殘留的信息素，其更新的公式為：

(2)

其中ρ為信息素?fù)]發(fā)程度系數(shù)，范圍0<ρ<1.

3.2　算法流程描述

最大最小蟻群算法的具體實(shí)現(xiàn)步驟如下：

1)參數(shù)初始化.事件t=0,循環(huán)次數(shù)N=0,最大循環(huán)次數(shù)NM，將當(dāng)前分配的數(shù)量為m的蟻群放置在當(dāng)前配送中心，然后初始化信息素τij=C，Δτij=0;

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

圖3　30車輛路徑最優(yōu)運(yùn)行圖Fig.3　The optimal running 30 vehicle routing

配送點(diǎn)個(gè)數(shù)2輛車耗時(shí)/s3輛車耗時(shí)/s4輛車耗時(shí)/s100.0619620.0573390.058893500.5075790.4926050.5127141003.9651551.8134061.18203115010.5333546.1665344.31460419018.2359027.9633715.153526

2)計(jì)算每個(gè)螞蟻選擇下一配送點(diǎn)的概率.根據(jù)式(1)計(jì)算得到每個(gè)螞蟻當(dāng)前配送點(diǎn)到下一未經(jīng)過的各個(gè)配送點(diǎn)的概率;

3)人工螞蟻?zhàn)詣?dòng)選擇下一配送點(diǎn).根據(jù)第2步計(jì)算得到的概率，通過輪盤賭算法計(jì)算出每只螞蟻下一步經(jīng)過的配送點(diǎn);

4)更新當(dāng)前各個(gè)螞蟻各自的禁忌列表.將剛經(jīng)過的配送點(diǎn)加入到各自的禁忌列表里面，防止重復(fù)經(jīng)過配送點(diǎn);

5)如果沒送點(diǎn)沒有遍歷完成轉(zhuǎn)到第4步，否則計(jì)算出各個(gè)螞蟻的所路徑的長(zhǎng)度;

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

7)循環(huán)一次，N=N+1;

8)若循環(huán)沒有結(jié)束轉(zhuǎn)到第2步，否則輸出最優(yōu)路徑.

算法流程圖下圖2所示.

4　實(shí)例計(jì)算與參數(shù)分析

從表1可以看出，在配送規(guī)模很小的情況下，三種情況耗時(shí)基本上差不多，但是隨著配送規(guī)模的變大，車輛越多耗時(shí)越小，反之相反.現(xiàn)實(shí)生活中當(dāng)配送規(guī)模很大的情況，此模型能夠很好的融入現(xiàn)實(shí)生活解決現(xiàn)實(shí)問題.

4.1　多車輛路徑最優(yōu)

4.1.1多車輛運(yùn)行.以30車輛數(shù)據(jù)為例：倉(cāng)庫(kù)位置：(264，357).

配送點(diǎn)位置：

(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配送長(zhǎng)度：1252,車輛1配送路徑：

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

車輛2配送長(zhǎng)度：1400,車輛2配送路徑：

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

配送路線圖像如圖3所示.

從圖3可以看出，通過聚類算法獲取得到的兩個(gè)類在位置區(qū)域上面有個(gè)明顯的位置差別，2輛車同時(shí)從倉(cāng)庫(kù)出發(fā)，按照各自的路線運(yùn)行，紅色的代表車輛1運(yùn)行路線，黃色的路線代表車輛2運(yùn)行路線.2輛車按照各自的運(yùn)行路線返回到倉(cāng)庫(kù).

4.1.2多車輛堵塞運(yùn)行.倉(cāng)庫(kù)位置：(244，338).

配送點(diǎn)位置：

(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配送長(zhǎng)度：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配送長(zhǎng)度：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

隨機(jī)堵塞幾條路徑情況：

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

車輛1配送長(zhǎng)度：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配送長(zhǎng)度：1846,車輛2配送路徑：

圖4　60車輛路徑最優(yōu)運(yùn)行堵塞圖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開始按照紅色路線運(yùn)行，當(dāng)堵塞之后，得到系統(tǒng)更新的路線就按照藍(lán)色的路線配送未走過的路線.車輛2和車輛1一樣，先按照黃色的路線運(yùn)行，堵塞的時(shí)候停止運(yùn)行，更新路線之后從當(dāng)前位置按照綠色的路徑運(yùn)行.對(duì)于時(shí)間最優(yōu)情況和本情況類似，不做介紹.

4.2　多車輛時(shí)間最優(yōu)

4.2.1多車輛運(yùn)行.以30車輛為例：倉(cāng)庫(kù)位置：(285，356).

配送點(diǎn)位置：

(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運(yùn)行時(shí)間：1119,車輛1運(yùn)行路線：

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

車輛2運(yùn)行時(shí)間：1636,車輛2運(yùn)行路線：

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車輛時(shí)間最優(yōu)運(yùn)行圖Fig.5　The optimal running 60 vehicles

運(yùn)行效果如圖5所示.

4.2.2多車輛堵塞運(yùn)行.倉(cāng)庫(kù)位置：(255，340).

配送點(diǎn)位置：

(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運(yùn)行時(shí)間：470.車輛1運(yùn)行路線如下：

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

車輛2運(yùn)行時(shí)間：663. 車輛2運(yùn)行路線如下：

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

車輛3運(yùn)行時(shí)間：742,車輛3運(yùn)行路線：

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

隨機(jī)堵塞路線：

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

車輛1運(yùn)行時(shí)間：478.車輛1運(yùn)行路線如下：

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

車輛2運(yùn)行時(shí)間：679. 車輛2運(yùn)行路線如下：

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

車輛3運(yùn)行時(shí)間：748.車輛3運(yùn)行路線如下：

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

本文對(duì)大規(guī)模配送點(diǎn)多車輛的問題進(jìn)行研究，但沒有對(duì)蟻群大小、啟發(fā)信息和揮發(fā)因子進(jìn)行研究，只是將前人經(jīng)驗(yàn)借鑒直接使用，對(duì)于這些參數(shù)只有進(jìn)行理論性的探索加上實(shí)際的測(cè)試才能得到比較準(zhǔn)確的結(jié)果.其次本文使用的是最大最小蟻群算法，沒有對(duì)其進(jìn)行改進(jìn)優(yōu)化，還有很多地方有待提高.

參考文獻(xiàn):

[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]葉有時(shí),唐林波,趙保軍.一種基于聚類的深空紅外多目標(biāo)快速檢測(cè)算法[J].電子與信息學(xué)報(bào),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.

責(zé)任編輯：時(shí)凌

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

文章編號(hào)：1008-8423(2015)02-0210-05 1008-8423(2015)02-0205-05

作者簡(jiǎn)介：李如平(1973- )，男，碩士，副教授，主要從事計(jì)算機(jī)應(yīng)用、物聯(lián)網(wǎng)技術(shù)的研究. 余基映(1987- )，女，碩士，主要從事并行計(jì)算研究.

基金項(xiàng)目：安徽省科技攻關(guān)計(jì)劃項(xiàng)目(13011031029、1201a0301008)；安徽省廳級(jí)自然科研項(xiàng)目(KJ2011B069、KJ2013Z105) ；安徽省對(duì)外科技合作計(jì)劃項(xiàng)目(1403062028).

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

中圖分類號(hào)：TN961

文獻(xiàn)標(biāo)志碼：A