DBSCAN聚類處理的改進(jìn)蟻群算法在車輛路徑問題中的應(yīng)用

徐書揚(yáng) 俞鴻烽 潘華錚 張宇來

摘要：傳統(tǒng)的蟻群算法在求解車輛路徑問題時(shí)迭代速度較慢，且求解精度較低，易陷入局部最優(yōu)。針對(duì)這些問題，利用DB-SCAN聚類算法對(duì)車輛路徑問題中的各個(gè)物料配送點(diǎn)進(jìn)行聚類劃分，并根據(jù)聚類劃分的情況對(duì)蟻群算法中的信息素矩陣合理初始化，實(shí)現(xiàn)對(duì)蟻群算法的改進(jìn)，使得改進(jìn)后的蟻群算法能有更高的求解精度和更快的收斂速度。通過MAT-LAB2019A對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行仿真測(cè)試，并與其他算法橫向?qū)Ρ龋傻酶倪M(jìn)后的蟻群算法在求解輛路徑問題時(shí)有著更高的求解精度和更快的收斂速度，特別是在配送點(diǎn)分布相對(duì)密集和各配送點(diǎn)需求量較小時(shí)有著明顯的效果。

關(guān)鍵詞：蟻群算法;DBSCAN聚類算法;車輛路徑問題

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2020）19-0182-05

開放科學(xué)（資源服務(wù)）標(biāo)識(shí)碼cOSID）：

1 概述

隨著互聯(lián)網(wǎng)科技的不斷完善，人們?cè)絹碓蕉嗟倪x擇通過網(wǎng)上購(gòu)物來滿足自己的購(gòu)買需求。因此合理的物流方案設(shè)計(jì)，也成為物流配送中的難點(diǎn)與焦點(diǎn)。早在1959年，Dantzig和Rems-er提出了車輛路徑問題（Vehicle Routine Problem）[1]，將復(fù)雜的物流問題抽象成了圖論問題供學(xué)者研究，該問題的優(yōu)化目標(biāo)為貨車在載重有限的情況下如何規(guī)劃路徑使得完成貨物配送所經(jīng)過的路程長(zhǎng)度最短。VRP問題屬于NP問題，隨著所要配送的點(diǎn)數(shù)增多，用精確算法求解會(huì)導(dǎo)致計(jì)算量過大，因此精確算法求解VRP問題并不適用。1986年，Solomon首次提出用啟發(fā)式算法來求解VRP問題[2]，研究發(fā)現(xiàn)，啟發(fā)式算法能在保證一定的求解精度的情況下有著較小的算法復(fù)雜度，因此更適用于VRP問題的求解。1999年，Dorigo和Gamberdella首次提出利用啟發(fā)式算法中的一種：蟻群算法來求解VRP問題[3-4]，由于蟻群算法本身具有良好的魯棒性和較高的求解精度，國(guó)內(nèi)外學(xué)者開始嘗試?yán)酶倪M(jìn)的蟻群算法或是相關(guān)的混合算法來求解VRP問題，例如，趙群在文獻(xiàn)[5]中提出利用蟻群算法和遺傳算法的混合算法求解VRP問題;劉春英在文獻(xiàn)[6]中提出利用粒子群算法和蟻群算法的混合算法求解VRP問題;石華踽在文獻(xiàn)[7]中將車輛轉(zhuǎn)移規(guī)則應(yīng)用到算法中使算法具有更強(qiáng)的應(yīng)用;鄭文艷在文獻(xiàn)[8]中更改了信息素更新方式和可行解構(gòu)造以提高算法的求解精度。

此外Dhawan C.Kumar Nassa V在文獻(xiàn)[9]中總結(jié)了前人的研究，在蟻群算法解決VRP問題上做了總結(jié)，比對(duì)了各代改進(jìn)算法的優(yōu)缺點(diǎn)，為今后的研究做了導(dǎo)向。M artin等人對(duì)DB-SCAN算法進(jìn)行了簡(jiǎn)單的闡述[10]，該算法能在具有噪聲的空間數(shù)據(jù)庫(kù)中發(fā)現(xiàn)任意形狀的簇，可將密度足夠大的相鄰區(qū)域連接，能有效處理異常數(shù)據(jù)，主要用于對(duì)空間數(shù)據(jù)的聚類。作為一種知名的聚類算法，BDSCAN算法廣泛地應(yīng)用于各個(gè)領(lǐng)域，例如無線電技術(shù)[11]，復(fù)雜環(huán)境監(jiān)測(cè)[12]屏常數(shù)據(jù)處理[13]等.在物流管理問題中也有著應(yīng)用，張洪奉在文獻(xiàn)[14]中提出了利用BDSCAN算法的改進(jìn)算法來設(shè)計(jì)物流信息管理系統(tǒng)。前人對(duì)于蟻群算法求解VRP問題的改進(jìn)有著明顯的效果，但是都未考慮到信息素矩陣的合理初始化對(duì)于算法收斂的導(dǎo)向作用。本文對(duì)傳統(tǒng)的蟻群算法進(jìn)行改進(jìn)，通過BDSCAN算法將VRP問題中的各個(gè)物料配送點(diǎn)進(jìn)行劃分聚類，并以此作為信息素矩陣初始化的依據(jù)，使得初始信息素矩陣對(duì)算法的收斂有導(dǎo)向作用，讓算法有著更高的求解精度和更快的收斂速度。

2 背景知識(shí)和算法描述

2.1 VRP問題

Dantzig和Remser提出了車輛路徑問題（Vehicle RoutineProblem，簡(jiǎn)稱VRP），它是運(yùn)籌學(xué)重要的研究問題之一。VRP問題關(guān)注一個(gè)供貨商與k個(gè)銷售點(diǎn)的路徑規(guī)劃的情況。該問題可以簡(jiǎn)述為：給定配送中心、一個(gè)車輛集合和一個(gè)顧客集合，車輛運(yùn)載能力和顧客需求量已知，每輛車都從配送中心出發(fā)，完成運(yùn)送任務(wù)后重新返回配送中心，目標(biāo)是在特定的約束條件下滿足客戶需求并且使得成本最小化，配送訂單最大化，滿載率最大化。圖形表示如下：

2.2 蟻群算法

蟻群算法（Ant Colony Algorithm，AC）由Dorigo和Gam-berdella首次提出，該算法能夠模擬自然界中螞蟻的覓食行為。昆蟲學(xué)家們發(fā)現(xiàn)螞蟻在行走過程中能夠釋放用來標(biāo)識(shí)自己行走路徑的稱為“信息素”的物質(zhì)，路徑長(zhǎng)遠(yuǎn)可以通過信息素濃度大小表示，信息素濃度越高，對(duì)應(yīng)的路徑越短。該算法的其基本思路為：將螞蟻的行走路徑作為待優(yōu)化問題的可行解，整個(gè)螞蟻群體的所有路徑構(gòu)成待優(yōu)化問題的解空間。路徑較短的螞蟻所釋放的信息素量較多，隨著時(shí)間的推進(jìn)，較短的路徑上累積的信息素濃度逐漸提高，選擇該路徑的螞蟻也隨之越來越多。最終，整個(gè)螞蟻群體通過信息素交換路徑信息在正反饋的作用下集中到最佳路徑上，該路徑對(duì)應(yīng)的就是待優(yōu)化問題的最優(yōu)解。

蟻群算法流程如下：

（1）初始化參數(shù)

對(duì)相關(guān)參數(shù)進(jìn)行初始化，如螞蟻數(shù)量m、信息素重要程度因子a、啟發(fā)函數(shù)重要程度因子6、信息素?fù)]發(fā)因子a、路徑信息素常量Q、最大迭代次數(shù)iter max、迭代次數(shù)初值iter=1。

（2）構(gòu)建解空間

將各個(gè)螞蟻放于不同出發(fā)點(diǎn)，對(duì)每個(gè)螞蟻根據(jù)概率公式計(jì)算其下一個(gè)訪問城市，直到遍歷完所有城市。

（3）更新信息素

計(jì)算各個(gè)螞蟻經(jīng)過的路徑長(zhǎng)度，記錄當(dāng)前迭代次數(shù)中的最優(yōu)解（最短路徑），同時(shí)進(jìn)行信息素濃度的更新。

（4）判斷是否終止

如果iter< iter max，則令iter= iter+1，清空螞蟻經(jīng)過路徑的記錄表，返回步驟二;否則，終止計(jì)算，輸出最優(yōu)解。

2.3 DBSCAN密度聚類算法

聚類分析屬于無監(jiān)督學(xué)習(xí)，DBSCAN（ Density-Based Spa-tial Clustering of Applications with Noise）是一種典型的基于密度的聚類算法，這類聚類算法一般假定類別可以通過樣本分布的精密程度決定，同一類別的樣本，在該類別任意樣本周圍不遠(yuǎn)處一定有同類別樣本存在。將這些緊密相連的樣本劃分為一類，就可以得到一個(gè)聚類類別。通過將所有各組緊密相連的樣本劃為各個(gè)不同的類別，就可以得到最終的所有聚類類別結(jié)果。DBSCAN算法可以將數(shù)據(jù)點(diǎn)分為三類：1、核心點(diǎn)：在半徑Eps內(nèi)含有超過MinPts數(shù)目的點(diǎn)。2、邊界點(diǎn)：在半徑Eps內(nèi)點(diǎn)的數(shù)量小于MinPts，但是落在核心點(diǎn)的鄰域內(nèi)的點(diǎn)。3、噪音點(diǎn)：既不是核心點(diǎn)也不是邊界點(diǎn)的點(diǎn)。

03-opt算法的具體流程如下：

Stepl：按圖（2）所示從路徑中刪除3條邊，從別的部分加入三條邊使得路徑保持完整。判斷路徑的交換是否能讓路徑總長(zhǎng)度變短，若能，則交換;若不能，則不交換。

Step2：重復(fù)執(zhí)行Stepl，直到遍歷完成所有的可能情況后輸出結(jié)果。

相較于其他opt算法，圖（2）中除了交換的各個(gè)邊之外，所有的曲線段的方向在交換后都未發(fā)生變化，這樣極大地減少了檢查可行路徑的工作量，使得該算法在嵌入到蟻群算法中后整體的算法時(shí)間復(fù)雜度并未發(fā)生明顯變化[15]。

3 改進(jìn)算法的設(shè)計(jì)

3.1改進(jìn)DBSCAN算法鄰域半徑計(jì)算

標(biāo)準(zhǔn)DBSCAN算法中，鄰域半徑為常數(shù)，且點(diǎn)與點(diǎn)之間的邊權(quán)重為點(diǎn)與點(diǎn)之間的距離。而在車輛路徑問題中，每個(gè)物料配送點(diǎn)具有各不相同的物料配送需求量，在鄰域半徑的計(jì)算中合理考慮每個(gè)物料配送點(diǎn)的需求量可以使得聚類劃分的結(jié)果更合理。當(dāng)物料配送需求量較大時(shí)，在單次配送中消耗了車輛更多的物料，根據(jù)貪心法則，優(yōu)先考慮將物料配送至物料配送需求量大的物料配送點(diǎn)可以提高單次配送中卡車的物料裝載空間利用率，因此，對(duì)于物料配送需求量大的配送點(diǎn)，需要適當(dāng)增加其鄰域半徑，使其更易被劃分為核心點(diǎn)，具體數(shù)學(xué)表達(dá)式如下：

3.2 改進(jìn)蟻群算法信息素初始化方案

傳統(tǒng)蟻群算法中，各條路徑上初始信息素濃度相等，這意味著初始信息素分布對(duì)算法的收斂不具備導(dǎo)向作用，這也是傳統(tǒng)蟻群算法收斂速度慢，易陷入局部最優(yōu)的一個(gè)重要原因[16]。為了使得初始信息素分布能夠?qū)λ惴ň哂泻侠淼膶?dǎo)向性，可以通過聚類的劃分區(qū)分各個(gè)配送點(diǎn)的相對(duì)位置[17]，并據(jù)此生成聚類，在同一聚類中的各點(diǎn)通過Kruskal算法生成最小生成樹，在所生成的最小生成樹中的各條路徑中初始化信息素，具體表達(dá)式如下：

3.3 基于03-opt算法的局部?jī)?yōu)化方案

在VRP問題的討論中，通常將會(huì)存在諸多從配送中心出發(fā)完成配送任務(wù)后回到起點(diǎn)的子路徑，例如在本文圖（1）所示范例中就存在3條子路徑：1-3-2-4，5-6-7-8，9-10-11-12。為使得算法能有更高的求解精度，在每一次蟻群算法迭代完成后對(duì)每一條子路徑進(jìn)行03-opt局部?jī)?yōu)化，從而更好地探尋更優(yōu)解。

3.4 改進(jìn)算法流程圖

4 實(shí)驗(yàn)內(nèi)容及結(jié)果分析

4.1 算例及初始數(shù)據(jù)

為驗(yàn)證算法的有效性，選取一個(gè)物流配送的實(shí)例情況對(duì)問題進(jìn)行討論。該實(shí)例選?。?0，40）作為供貨點(diǎn)，各個(gè)配送點(diǎn)的相關(guān)信息如表1所示，各個(gè)基本參數(shù)的設(shè)置值如表2所示：

其中，p表示信息素?fù)]發(fā)參數(shù)，N_表示算法運(yùn)行迭代最大限制次數(shù)，表示螞蟻循環(huán)一周釋放的信息素總量，m表示螞蟻數(shù)，τ0表示不同簇上點(diǎn)之間的信息素初始參數(shù)值，τ1表示相同簇上核心點(diǎn)之間的信息素初始參數(shù)值，τ2示相同簇上非核心點(diǎn)之間的信息素初始參數(shù)值，CAP表示火車最大載重量。

4.2 仿真測(cè)試與結(jié)果分析

首先通過DBSCAN算法對(duì)配送點(diǎn)進(jìn)行聚類劃分成各個(gè)不同的簇，接著對(duì)各個(gè)簇利用Kruskal生成最小生成樹，結(jié)果如圖3所示：

DBSCAN算法的應(yīng)用成功將各個(gè)配送點(diǎn)劃分在不同的簇中，并在簇中生成了最小生成樹。根據(jù)本文2.4部分的內(nèi)容對(duì)蟻群算法中的初始信息素矩陣進(jìn)行更新。之后分別用本文改進(jìn)后的算法，傳統(tǒng)蟻群算法，傳統(tǒng)粒子群算法和文獻(xiàn)[14]提出的算法通過MATLAB2019A對(duì)實(shí)例進(jìn)行1000次仿真測(cè)試，并將結(jié)果每種算法的1000次仿真測(cè)試結(jié)果求其均值后觀察每種算法的求解精度與收斂速度。為了更好地衡量算法的收斂速度，這里做如下定義：

當(dāng)算法得到最佳求解結(jié)果時(shí)說需要的最少迭代次數(shù)值為算法的最佳迭代點(diǎn)。

程序運(yùn)行結(jié)果如表3所示：

1）本文算法;

2）傳統(tǒng)蟻群算法;

3）傳統(tǒng)粒子群算法;

4）文獻(xiàn)[8]提出的算法。

由表3可知，本文所提出的算法在求解該實(shí)例時(shí)所規(guī)劃的路徑相較于其他算法更短，并且有著更小的最佳迭代點(diǎn)，由此可以驗(yàn)證無論在求解精度還是收斂速度上相較于其他算法都有著明顯的優(yōu)勢(shì)。由此可以驗(yàn)證，本文所提出的算法有著較高的求解精度，在求解VRP問題時(shí)為貨車制定的路徑相較于其他算法更短，為貨運(yùn)公司節(jié)省更多的時(shí)間和成本;同時(shí)本文算法也有著更快的收斂速度，在解決實(shí)際問題時(shí)能夠以較小的計(jì)算量解決問題，使得方法的應(yīng)用更快捷，占用更少的時(shí)間。

5 結(jié)束語(yǔ)

本文通過DBSCAN聚類算法對(duì)蟻群算法的初始信息素矩陣進(jìn)行更新，使得初始信息素分布對(duì)算法的合理收斂有著良好的導(dǎo)向性從而得到更精確的結(jié)果和更快的收斂速度。然而，本文對(duì)于同一簇中的配送點(diǎn)間的信息素的初始化值設(shè)定為自定義參數(shù)，因此該自定義參數(shù)值的選取會(huì)對(duì)結(jié)果產(chǎn)生較大的影響，如果該值過大，則算法收斂速度過快，容易陷入局部最優(yōu)而影響求解精度;如果該值過小，則算法中初始信息素分布對(duì)算法的收斂缺乏良好的導(dǎo)向性，使得收斂速度較慢，且求解精度相對(duì)不高，相較于傳統(tǒng)蟻群算法沒有明顯的優(yōu)勢(shì)。此外值得一提的是，算法本身的參數(shù)值也會(huì)影響算法的求解效果，例如在配送點(diǎn)分布相對(duì)較為分散時(shí)，DBSCAN算法對(duì)于簇的分類效果較差，導(dǎo)致求解精度相較于傳統(tǒng)蟻群算法的提高并不明顯;在配送點(diǎn)需求量較大時(shí)，同一簇的配送點(diǎn)需要貨車多次運(yùn)輸，則本文算法易在迭代初期陷入局部最優(yōu)。總之，相較于其他算法本文算法對(duì)VRP問題的求解有著明顯的優(yōu)勢(shì)，但是依舊存在可改進(jìn)空間，在之后的研究中，如何確定相關(guān)基本參數(shù)以及如何選擇性地對(duì)同一簇內(nèi)點(diǎn)間的信息素進(jìn)行更新成為重點(diǎn)和難點(diǎn)。

參考文獻(xiàn)：

[1] Toth P， Vigo D. Vehicle routing Problems，