彭熙舜，陸安江，賈明俊，盧學(xué)敏

（貴州大學(xué) 大數(shù)據(jù)與信息工程學(xué)院，貴陽550025）

0 引 言

在當(dāng)今時(shí)代，網(wǎng)購已經(jīng)成為了一種新的潮流，每年由電商舉辦的雙十一、六一八更是風(fēng)靡盛行。隨著快遞數(shù)目的劇烈增長，物流的配送工作越來越重要。人們購買的物件也是花樣繁多，生鮮快遞必須滿足時(shí)效性，裝飾類物品需要避免發(fā)生碰撞。物流配送過程中常規(guī)應(yīng)用GPS導(dǎo)航，而高效的物流管理取決于兩個(gè)關(guān)鍵因素，車輛問題（VRP）與資源配置問題，因此路徑規(guī)劃開始被廣泛應(yīng)用于物流管理中。本文提出了利用Kmeans聚類將客戶購買物品按照特性進(jìn)行分類，再利用蟻群算法進(jìn)行路徑規(guī)劃。

1 研究背景與意義

路徑規(guī)劃是近代興起的新型技術(shù)，被廣泛應(yīng)用于機(jī)器人避障，無人機(jī)避障，防空導(dǎo)彈系統(tǒng)中。人們的日常生活也開始利用這種技術(shù)，比如城市交通規(guī)劃，GPS智能導(dǎo)航，物流配送管理系統(tǒng)。通常情況下，按照周圍環(huán)境信息的布局規(guī)劃，可以將其分為全局和局部兩種路徑規(guī)劃［1］。前者需要在實(shí)踐之前掌握所有的環(huán)境數(shù)據(jù)，提前作出路徑規(guī)劃判斷；后者主要是采取傳感器實(shí)時(shí)得來的局部環(huán)境信息，及時(shí)的給出路徑規(guī)劃。本文主要研究解決車輛路徑問題（VPR），以物流中心為起點(diǎn)，派出車輛向不同位置的客戶進(jìn)行物資配送，配送任務(wù)結(jié)束后返回起點(diǎn)，而其中的關(guān)鍵在于將配送效率最大化，車輛使用率最大化。

路徑規(guī)劃一般是由環(huán)境建模，路徑搜索，路徑平滑這3步所組成［2］。環(huán)境建模是起始環(huán)節(jié)，搭建一個(gè)方便計(jì)算機(jī)規(guī)劃具體路徑的模型，實(shí)質(zhì)上是將物理信息轉(zhuǎn)為數(shù)字信息，在空間上相互映射；路徑搜索是指在搭建的環(huán)境中尋求到達(dá)目標(biāo)的路徑信息；路徑平滑是在所有的路徑信息中選取最優(yōu)路徑。

2 智能算法

2.1 Kmeans算法簡介

網(wǎng)絡(luò)用戶的大幅度增長也帶動(dòng)了數(shù)據(jù)的產(chǎn)生，面對愈來愈多的用戶數(shù)據(jù)，根據(jù)其之間的相似性，進(jìn)行聚類分析（cluster analysis）。所謂聚類并不是通常意義上的按規(guī)格分類，空間中點(diǎn)的匯聚稱為一個(gè)類簇，不同類簇中任意的兩點(diǎn)距離應(yīng)該大于同一類簇中的任意兩點(diǎn)距離［3］。具體過程可以描述為，第一步設(shè)置一個(gè)衡量標(biāo)準(zhǔn)，將系統(tǒng)中的個(gè)體數(shù)據(jù)特性計(jì)算區(qū)別；第二步使用算法將個(gè)體匯編并定義為一個(gè)新的集群。如今存在著多種不同的聚類分析方法，如何根據(jù)自身要求選擇一種合適的算法來進(jìn)行數(shù)據(jù)分析成了當(dāng)務(wù)之急。

Kmeans又稱為K均值，是一種劃分聚類的算法，具有高效簡潔的特點(diǎn)普及率高。其算法步驟清晰易懂，首先根據(jù)客戶需求設(shè)置值為k的n個(gè)初始質(zhì)心；其次，將質(zhì)心散開，將系統(tǒng)中的數(shù)據(jù)點(diǎn)根據(jù)自身特性匹配到與其距離最近的質(zhì)心，同一個(gè)質(zhì)心中的數(shù)據(jù)點(diǎn)構(gòu)成了簇。分析簇中的數(shù)據(jù)點(diǎn)，更新質(zhì)心的值。按照以上步驟重復(fù)進(jìn)行，直到質(zhì)心的值不再變化或者達(dá)到了設(shè)定的終止條件為止。

為了將數(shù)據(jù)點(diǎn)匹配到與之最近的質(zhì)心，需要設(shè)定方法來測算距離。給定一個(gè)樣本空間x i＝將i，j設(shè)置為樣本數(shù)，n表示數(shù)據(jù)特征。首先計(jì)算有序距離度量，根據(jù)閔可夫斯基距離公式（1）：

其次，介紹無序?qū)傩跃嚯x度量，式（2）：

Kmeans在空間中只需考慮數(shù)據(jù)點(diǎn)與質(zhì)心問題，它的空間復(fù)雜度不高?？臻g的存儲(chǔ)量設(shè)定O（（m+k）n），其中的m是數(shù)據(jù)點(diǎn)數(shù)，n代表了屬性數(shù)。它的時(shí)間復(fù)雜性與數(shù)據(jù)點(diǎn)的數(shù)目有關(guān)，所需要的時(shí)間于m呈線性表示，為O（I×K×m×n），I代表了收斂的迭代次數(shù)。

2.2 蟻群算法

蟻群算法，顧名思義是模仿生物界中螞蟻特性的算法。這種算法模仿的是螞蟻從蟻窩中尋找食物所自動(dòng)生成的最佳路徑的過程。在螞蟻行走的過程里，它們會(huì)釋放一種被稱為信息素的物質(zhì)，以此來標(biāo)識自己的行走路徑，路徑越長的地方，信息素越少，而路徑越短的地方，信息素越多，表示了螞蟻選擇走該路徑的數(shù)量居多。久而久之，信息素少的地方自然也就被淘汰，最后留下來的就是一個(gè)優(yōu)化路線［4］。

蟻群算法在離散空間中是通過離散的點(diǎn)狀散布來選取的信息量的最優(yōu)解。連續(xù)空間中的解空間與離散的不同，是以區(qū)域性的方式進(jìn)行表示，不是用離散的點(diǎn)集合表示。連續(xù)空間與離散空間有著3處不同，首先是觀察蟻群的信息量留存方式；其次蟻群在解空間中尋找最優(yōu)路徑方法；以及最后的群體前進(jìn)策略。

蟻群算法在連續(xù)空間下的尋優(yōu)方法是基于蟻群的初始分布狀態(tài)，螞蟻路途中釋放的信息量分布狀態(tài)，整個(gè)蟻群的行進(jìn)方向策略。因此，可以用數(shù)學(xué)表達(dá)式模擬出基本過程：第一步是將群體的初始分布狀態(tài)表示，根據(jù)問題來設(shè)置蟻群的大小，例如設(shè)置共有N個(gè)小螞蟻；將問題的定義區(qū)間均等分為N個(gè)子空間，每個(gè)子空間匹配一只小螞蟻，編號為i。因?yàn)槲浵仌?huì)變換自己的活動(dòng)區(qū)域，所以所規(guī)定的子空間也是隨著螞蟻同步變化的，一一對應(yīng)。當(dāng)小螞蟻隨機(jī)移動(dòng)時(shí)，可以發(fā)現(xiàn)它所攜帶的子空間會(huì)與其它2個(gè)相鄰的子空間重疊，根據(jù)這個(gè)重疊的程度，可以推算出2個(gè)相鄰子空間內(nèi)的實(shí)際螞蟻?zhàn)兓潭龋?-6］。

按照以上敘述方式，設(shè)置提出問題的定義區(qū)間是［A，Z］，則當(dāng)種群內(nèi)的螞蟻數(shù)目為N時(shí)，可以得到各個(gè)子空間的長度為式（3）：

因?yàn)槲浵佊兄陨磉\(yùn)動(dòng)的移動(dòng)子空間，而這個(gè)移動(dòng)子空間的長度與基本子空間是沒有區(qū)別的，所以有L R＝L，那么蟻群的初始點(diǎn)的坐標(biāo)分布可以定義為式（4）：

螞蟻所處子空間i的左邊界為x iL，右邊界為x i R，可以得到式（5）：

當(dāng)螞蟻隨機(jī)移動(dòng)k時(shí)，移動(dòng)子空間與相鄰子空間的重疊度也為k，那么可以定義兩個(gè)相鄰的子空間內(nèi)對應(yīng)當(dāng)前螞蟻的實(shí)際個(gè)數(shù)N1的變化為式（6）：

所以，當(dāng)小螞蟻向右行進(jìn)時(shí)，右邊子空間內(nèi)實(shí)際的螞蟻數(shù)目多出了Δn，與之相對，左邊的子空間實(shí)際螞蟻數(shù)目就減少了Δn。

接下來根據(jù)螞蟻的分布情況來確定空間中的信息量分布密度。若蟻群在x i處的函數(shù)值為f（x i)，那么可以規(guī)定此時(shí)螞蟻留下的信息量峰值為M i，這樣可以根據(jù)函數(shù)與信息量的大小得出最優(yōu)路徑。假設(shè)在某一區(qū)間內(nèi)去實(shí)現(xiàn)尋找函數(shù)的最小值，那么可以得到相應(yīng)的信息量分布函數(shù)，式（7）：

其中，R是設(shè)定的常數(shù)，規(guī)定R＞f（x i）。 此時(shí)可以發(fā)現(xiàn)，函數(shù)值越小，信息量的分布函數(shù)峰值越大。相對的，如尋找函數(shù)的最大值，當(dāng)f（x i）＞0，可以得到式（8）：

因此，可以得到單個(gè)螞蟻所對應(yīng)的信息量分布函數(shù)為式（9）：

在得到螞蟻群分布的總信息量后，需要確定各子區(qū)間內(nèi)的實(shí)際螞蟻數(shù)目［7］。根據(jù)信息量分布函數(shù)可以得出當(dāng)前蟻群在各個(gè)子空間內(nèi)分布積分和為式（10）：

實(shí)際上的各子空間總信息量為式（11）：

其中，q代表上上次的總信息量遺留部分，p代表信息量的揮發(fā)量。所以可以得出實(shí)際總空間中的總信息量為式（12）：

按照子空間中的實(shí)際總信息量與總空間的信息量可以推算出螞蟻的分布情況，得出螞蟻在某一子空間中的數(shù)目為式（13）：

3 仿真分析

利用Kmeans算法與蟻群算法思想，事先構(gòu)思出聚類規(guī)劃和尋優(yōu)路徑的新型路徑配送方式。將文本數(shù)據(jù)導(dǎo)入程序，設(shè)N為樣本數(shù)量，n是樣本中的屬性數(shù)；將螞蟻群分成4個(gè)小組；螞蟻總數(shù)目設(shè)為R，最大迭代次數(shù)用Tmax表示，表1為不同組參數(shù)設(shè)置表，其中Mi n代表螞蟻到其對應(yīng)的聚類中心的距離最小值。

此外，還需要注意偏離誤差的計(jì)算，即為螞蟻到其對應(yīng)的聚類中心的距離Mi n，Mi n越小，說明螞蟻越集中，聚類水平高。倘若得到每一只螞蟻的Mi n值，那么從中挑選出最小的Mi n，其所對應(yīng)的路徑就是本次迭代的最佳路徑。而迭代的方法就是利用循環(huán)，更新蟻群的信息素，根據(jù)新的參數(shù)進(jìn)行尋優(yōu)計(jì)算，直到滿足要求為止。當(dāng)R＝100，Tmax＝1 000時(shí)，仿真分析如圖1，當(dāng)R＝100，Tmax＝10 000時(shí)，如圖2所示。

表1 程序參數(shù)設(shè)置表Tab.1 Program parameter setting table

圖1 第一次蟻群聚類結(jié)果Fig.1 The first ant colony clustering results

圖2 增大迭代次數(shù)后的聚類效果Fig.2 The clustering effect after increasing the number of iterations

從圖1中可以清晰地看到，共有R＝4種螞蟻組數(shù)，此時(shí)的M i n是30 690，達(dá)到了一定的聚類效果，但還不能滿足要求，接下來繼續(xù)增大迭代次數(shù)。將Tma x增大到10 000可得以下結(jié)果：

由圖2知，此時(shí)的Mi n＝19 726，相比于第一次聚類效果，在達(dá)到良好的聚類分析后，需要找出一條合適的路徑，從初始點(diǎn)到聚類中心，接下來需要對路徑進(jìn)行尋優(yōu)規(guī)劃。此時(shí)用400個(gè)單位方塊模擬環(huán)境地圖，邊長設(shè)置為1，以（0，0）作為初始點(diǎn)，（20，20）作為終點(diǎn)，圖3和圖4中隨機(jī)設(shè)置障礙物，并用矩陣存儲(chǔ)每一代的每一只螞蟻的爬行路線長度。

圖3 螞蟻爬行路線Fig.3 Ant crawling route

圖4 螞蟻無碰撞最優(yōu)路徑Fig.4 The optimal path of ants without collision

由圖3可知，螞蟻從起始點(diǎn)到終點(diǎn)路線數(shù)量復(fù)雜，尤其是起始點(diǎn)附近，因?yàn)槲浵亜倧南佈ǔ鰜?，?shù)量眾多，分泌的信息素也多，因?yàn)槁窂礁拥姆爆?。在接近終點(diǎn)處，由于路程長度，信息素散發(fā)稀釋，所以螞蟻的行進(jìn)路線自然減少。螞蟻此次路程的最佳路徑如圖4所示，在無碰撞的情況下保證路程長度。

4 結(jié)束語

利用Kmeans與蟻群算法能夠很好地解決物流配送問題，尤其是當(dāng)下不同種類的物資需要不同的配送方式。物流中心在接到配送訂單時(shí)，可以利用該組合算法對配送物品進(jìn)行聚類分析，可以按照物件的時(shí)效性，安全性等作為路徑規(guī)劃，這樣就能更好的滿足客戶的需求，同時(shí)也減少了物流配送的時(shí)間成本。Kmeans與蟻群算法對當(dāng)下的快遞行業(yè)有著一定的參考意義。