基于Spark的自適應(yīng)蟻群算法對(duì)CVRP問題的求解

徐濤/XU Tao，孫鑒/SUN Jian，2，劉陳偉/LIU Chenwei

（ 1.北方民族大學(xué)，中國 銀川 750021；2.圖像圖形智能處理國家民委重點(diǎn)實(shí)驗(yàn)室，中國 銀川 750021 ）

作為車輛路徑問題（VRP）的一個(gè)分支，帶有容量限制的車輛路徑問題（CVRP）和旅行商問題（TSP）相比，約束條件復(fù)雜，問題規(guī)模大，求解難度高。VRP在物流配送中具有至關(guān)重要的作用，是運(yùn)籌學(xué)和組合優(yōu)化領(lǐng)域的研究熱點(diǎn)，受到業(yè)界廣泛關(guān)注。

VRP[1]是一種NP-hard問題，主要的解決方法有精確式算法、元啟發(fā)式算法、機(jī)器學(xué)習(xí)算法等。分支限界法[2-3]及動(dòng)態(tài)規(guī)劃法[4-5]是精確式算法[6]的代表，可以有效求解小規(guī)模的CVRP問題。例如，對(duì)于數(shù)據(jù)集CVRPLIB①http://vrp.atd-lab.inf.puc-rio.br/index.php/en/中A類（set A）的27個(gè)實(shí)例，其節(jié)點(diǎn)規(guī)模在32～80之間[7]。但面對(duì)大規(guī)模問題，如數(shù)據(jù)集CVRPLIB中X類（Uchoa et al）的99個(gè)實(shí)例，節(jié)點(diǎn)規(guī)模在101～1 001之間[8]，計(jì)算復(fù)雜度較高，計(jì)算資源受限。強(qiáng)化學(xué)習(xí)[9-12]和深度學(xué)習(xí)[13-14]是機(jī)器學(xué)習(xí)算法的代表，但面對(duì)大規(guī)模CVRP的求解時(shí)間較長。蟻群算法[15]、模擬退火算法[16]、遺傳算法[17]是元啟發(fā)式算法的代表。此類算法更適用于大規(guī)模客戶點(diǎn)的場(chǎng)景，能夠在一個(gè)可接受的時(shí)間內(nèi)得到一個(gè)相對(duì)可以接受的解。而蟻群算法由于具有螞蟻搜索路徑過程中并行的特點(diǎn)，結(jié)合分布式計(jì)算框架，可以有效提高解的效率。

蟻群算法本質(zhì)上是一種并行算法，其中每只螞蟻搜索路徑的過程彼此獨(dú)立。黃震華等[18]利用圖形處理器（GPU）多線程并發(fā)的優(yōu)勢(shì)，提出中央處理器-圖形處理器（CPUGPU）異構(gòu)環(huán)境。該環(huán)境由CPU負(fù)責(zé)控制，同時(shí)由GPU完成大部分計(jì)算任務(wù)。每只螞蟻被分配到統(tǒng)一計(jì)算設(shè)備架構(gòu)（CUDA）的不同線程上。雖然能實(shí)現(xiàn)螞蟻并行，但是這種異構(gòu)環(huán)境依舊是單GPU多線程的單機(jī)環(huán)境。吳昊等[19]提出基于大數(shù)據(jù)環(huán)境MapReduce框架的蟻群算法。該算法用Map函數(shù)并行每只螞蟻求解過程，用Reduce函數(shù)表達(dá)求得較優(yōu)解和改變信息素過程，同時(shí)應(yīng)用云計(jì)算的管道能力，把Re‐duce函數(shù)的輸出信息作為下一代Map函數(shù)的輸入，以進(jìn)行下一代循環(huán)。這種蟻群算法在求解大規(guī)模的TSP問題上取得較好的結(jié)果。與MapReduce平臺(tái)蟻群優(yōu)化算法相比，王詔遠(yuǎn)等[20]提出的基于Spark平臺(tái)的蟻群優(yōu)化算法在解決TSP問題上的執(zhí)行速度提升了10倍以上。

雖然上述并行算法能較好地解決CVRPLIB中A類及X類的VRP，但這些算法仍存在求解時(shí)間長、精度不高、平臺(tái)架構(gòu)限制大、擴(kuò)展性差等缺陷。為此，本文中我們提出一種基于Spark平臺(tái)的自適應(yīng)蟻群算法（SPAMACO）。

本文中，我們首先針對(duì)蟻群算法信息素導(dǎo)向和啟發(fā)信息權(quán)重進(jìn)行自適應(yīng)變化設(shè)計(jì)，擺脫固定參數(shù)的弊端；分段設(shè)計(jì)信息素強(qiáng)度變化，及時(shí)跳出局部最優(yōu)解；針對(duì)求解精度差的問題，在產(chǎn)生局部解時(shí)利用2-opt算子增強(qiáng)算法局部搜索能力；針對(duì)大規(guī)模數(shù)據(jù)集執(zhí)行時(shí)間過長問題，在Spark平臺(tái)實(shí)現(xiàn)該并行算法，將蟻群封裝成彈性分布式數(shù)據(jù)集（RDD），實(shí)現(xiàn)蟻群在分布式集群環(huán)境下的并行構(gòu)造可行解，在減少算法執(zhí)行時(shí)間的前提下保證了算法的求解精度。

1 技術(shù)介紹

1.1 CVRP問題描述

在 圖G= (V,E)中 ， 頂 點(diǎn)V={v0,v1,…,vn}， 邊E={(vi,vj),i≠j}。其中，v0表示倉庫，vn為第n個(gè)客戶點(diǎn)。每個(gè)客戶的需求為ci，dij表示(vi,vj)的歐幾里得距離，每輛車的最大載重為D。約束條件如下：

（1）每輛車都必須從倉庫出發(fā)，并且返回倉庫；

（2）每個(gè)客戶點(diǎn)有且只有一輛車可以進(jìn)行配送服務(wù)；

（3）一條線路上客戶的總需求不能超過車輛的容量限制。

CVRP的目標(biāo)是在這些節(jié)點(diǎn)當(dāng)中確定一條最短的路徑。集合K={1,2,3,…,k}表示運(yùn)輸車輛，車輛總數(shù)為k。集合P={pi={vi1,vi2,…,vir i}|r∈K}，使P中的k條路徑距離和最小。其中，ri為由車輛i配送的客戶節(jié)點(diǎn)數(shù)，vij為車輛i經(jīng)過的第j+1個(gè)節(jié)點(diǎn)。建立模型的目標(biāo)使車輛路徑總長度最短。

1.2 蟻群算法

蟻群算法是M. DORIGO教授于1992年提出的。該算法源于螞蟻覓食行為。螞蟻在尋找食物時(shí)，會(huì)在經(jīng)過的路徑上釋放一種信息素，并且能夠感知其他螞蟻釋放的信息素。信息素濃度的大小表明路徑的遠(yuǎn)近。信息素濃度越高，對(duì)應(yīng)的路徑距離越短。通常螞蟻會(huì)以較大的概率優(yōu)先選擇信息素濃度高的路徑，并且釋放一定的信息素，使該條路徑上的信息素濃度增高，進(jìn)而使自己能夠找到一條由巢穴到食物源最近的路徑。但是路徑上的信息素濃度會(huì)隨著時(shí)間推移而逐漸衰減。

其中，Qk(i)={1,2,…,n}-τk表示螞蟻k下一步允許選擇的城市；列表τk記錄這此次迭代中螞蟻k的已訪問城市，在接下來的遍歷中不能再次訪問列表τk中的城市；τij(t)表示t時(shí)刻路徑(i,j)上信息素的數(shù)量；ηij表示啟發(fā)因子，一般取路徑(i,j)距離的倒數(shù)；α和β分別表示路徑上的信息素累積量和啟發(fā)信息的權(quán)重比例。

其中，Q為常數(shù)，Lk表示螞蟻k在此次迭代中所走過的路徑長度。

在蟻群算法求解CVRP方面，WANG X.[21]等提出一種新的ACO算法來求解CVRP。該算法允許螞蟻多次進(jìn)出倉庫，直到它們?cè)L問所有客戶。這簡(jiǎn)化了構(gòu)建可行解的過程。LIN N.[22]等針對(duì)CVRP提出一種有效的順序感知混合遺傳算法。該算法的特征為改進(jìn)的初始化策略和特定問題的交叉算子。前者結(jié)合了掃描算法，后者結(jié)合了鄰域搜索啟發(fā)式。S.AKPINAR[23]提出一種新的混合算法。該算法結(jié)合蟻群優(yōu)化的解構(gòu)造機(jī)制，執(zhí)行大鄰域搜索（移除和插入算子）方法來求解CVRP。R. GOEL[24]提出用蟻群和螢火蟲算法（HAFA）的混合算法來求解CVRP，并在CVRP和帶時(shí)間窗車輛路徑問題（VRPTW）上做了驗(yàn)證。

1.3 局部搜索算子2-opt

2-opt算法是一種隨機(jī)性算法，其基本思想是隨機(jī)取兩個(gè)元素進(jìn)行優(yōu)化，在路徑問題求解上得到廣泛應(yīng)用。如圖1所示，路徑AD、BC。如果滿足AD+BC＞AB+DC，則刪除AD、AC并連接AB、DC，生成更短的路徑。

▲圖1 2-opt算法優(yōu)化過程

1.4 Spark計(jì)算框架

Spark是Apache軟件基金會(huì)三大分布式計(jì)算系統(tǒng)開源項(xiàng)目，是基于內(nèi)存的分布式計(jì)算平臺(tái)。與MapReduce相比，Spark可以將計(jì)算中間結(jié)果存儲(chǔ)在內(nèi)存中，不需要反復(fù)讀寫分布式文件系統(tǒng)（HDFS），提高了計(jì)算速度，因此適合需要迭代處理的算法。Spark運(yùn)行架構(gòu)如圖2所示。

▲圖2 Spark運(yùn)行架構(gòu)

Spark運(yùn)行架構(gòu)包括集群資源管理器、執(zhí)行作業(yè)任務(wù)的工作節(jié)點(diǎn)、每個(gè)應(yīng)用的任務(wù)控制節(jié)點(diǎn)和每個(gè)工作節(jié)點(diǎn)的執(zhí)行進(jìn)程。Spark所采用的進(jìn)程有兩個(gè)優(yōu)點(diǎn)：一是用多線程執(zhí)行具體任務(wù)，減少了啟動(dòng)開銷；二是在執(zhí)行進(jìn)程中，會(huì)把內(nèi)存和磁盤共同作為存儲(chǔ)設(shè)備，有效減少了輸入/輸出（I/O）開銷，提高了讀寫性能。

2 基于Spark框架的自適應(yīng)蟻群算法設(shè)計(jì)

2.1 轉(zhuǎn)移概率的改進(jìn)

本文采用自適應(yīng)調(diào)整選擇概率來提高收斂性能。公式（9）中先進(jìn)行的狀態(tài)轉(zhuǎn)換的選擇操作，使得搜索個(gè)體傾向選擇信息素濃度較高且路徑長度較短的城市f。

其中，q是[0,1]區(qū)間的均勻分布的隨機(jī)數(shù)；q0=2-arctan(ni+2)，(ni=1,2,…,iterations)，iterations為最大迭代次數(shù)。

2.2 信息素強(qiáng)度的動(dòng)態(tài)調(diào)整

在前期，算法收斂比較慢；在后期，路徑信息素濃度過大（容易造成局部最優(yōu)）。對(duì)此，本文采用公式（11）中的分段函數(shù)代替常數(shù)Q。

當(dāng)最優(yōu)解在一段時(shí)間內(nèi)不變化時(shí)，搜索過程可能陷入局部最優(yōu)困境。此時(shí)，分段的信息素設(shè)定可以增加或者減少信息素的數(shù)量影響。這使系統(tǒng)可以跳出局部最優(yōu)困境。

2.3 自適應(yīng)蟻群算法的并行化實(shí)現(xiàn)

用Spark平臺(tái)可以完成自適應(yīng)蟻群算法的并行實(shí)現(xiàn)。我們采用RDD進(jìn)行操作，實(shí)現(xiàn)蟻群并行構(gòu)建求解過程。

具體的SPAMACO步驟如下：

1）讀取CVRPLIB數(shù)據(jù)文件，初始化車輛數(shù)量k、車輛容量D，構(gòu)建坐標(biāo)點(diǎn)（x,y）、客戶點(diǎn)需求demand，計(jì)算各點(diǎn)距離，初始化信息素矩陣；

2）初始化參數(shù)；

3）封裝螞蟻為Ant類，利用Spark的.parallelize()操作將螞蟻裝換為分布式的RDD；

4）在每輪迭代中通過Spark的.map()方法實(shí)現(xiàn)并行求解過程；

5）每輪迭代結(jié)束后通過Spark的.collect()方法收集計(jì)算結(jié)果，對(duì)其進(jìn)行2-opt局部?jī)?yōu)化；

6）更新信息素并廣播；

7）判斷迭代是否結(jié)束，結(jié)束輸出全局最優(yōu)解，否則返回步驟4繼續(xù)并行計(jì)算求解。

綜上所述，算法流程如圖3所示。

▲圖3 基于Spark的自適應(yīng)蟻群算法求解CVRP流程圖

3 數(shù)值實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)計(jì)

本文基于Spark分布式集群實(shí)現(xiàn)SPAMACO。實(shí)驗(yàn)環(huán)境由8臺(tái)虛擬機(jī)組成，其中包括1臺(tái)master主節(jié)點(diǎn)（負(fù)責(zé)任務(wù)控制節(jié)點(diǎn)的運(yùn)行和管理），7臺(tái)執(zhí)行節(jié)點(diǎn)。

硬件配置：每臺(tái)虛擬機(jī)CPU為四核四線程，內(nèi)存為4 GB，磁盤容量為40 GB。操作系統(tǒng)是64位的Ubuntu18.04。

軟件配置：Spark2.4.0、hadoop3.1.3、java1.8.0_162。實(shí)驗(yàn)中，我們采用具有函數(shù)式編程特性的python語言，同時(shí)為驗(yàn)證SPAMACO算法的有效性，采用自適應(yīng)動(dòng)態(tài)搜索蟻群算法（ADACO）[25]和自適應(yīng)貪婪蟻群算法（GSACO）[26]作為對(duì)比實(shí)驗(yàn)。其中，為了保證公平性，GSACO和ADACO的參數(shù)選用原文中的參數(shù)設(shè)置。3個(gè)算法的迭代次數(shù)均為200次。

3.2 小規(guī)模算例實(shí)驗(yàn)結(jié)果

對(duì)于小規(guī)模算例，本文采用CVRPLIB中的A類數(shù)據(jù)集（SET A Benchmark），并選取 A-n60-k9、A-n61-k9、A-n62-k9、 A-n62-k10、 A-n63-K9、 A-n64-k9、 A-n65-k9、A-n69-k9、A-n80-k10進(jìn)行求解。實(shí)驗(yàn)結(jié)果如表1所示，其中V表示當(dāng)前算法最優(yōu)解，T表示程序運(yùn)行時(shí)間。

▼表1 小規(guī)模算例實(shí)驗(yàn)結(jié)果

從表1可以看出，和ADACO、GSACO相比，SPAMACO在求解精度上有所提升。但是由于受到Spark集群初始化時(shí)間、廣播時(shí)間和組間通信等的影響，在小規(guī)模算例上，SPAMACO的運(yùn)行時(shí)間優(yōu)勢(shì)并不明顯。在客戶點(diǎn)大于65后，并行的執(zhí)行時(shí)間優(yōu)勢(shì)逐漸體現(xiàn)。在執(zhí)行A-n80-k10算例時(shí)，本文算法執(zhí)行時(shí)間比ADACO低28.8%，比GSACO低17%。

由圖4可以看出，對(duì)于小規(guī)模算例，隨著客戶點(diǎn)數(shù)的增加，3個(gè)算法的執(zhí)行時(shí)間會(huì)逐步增加。其中，除A-n80-k10以外，這種增加比例幾乎相同。

▲圖4 小規(guī)模算例運(yùn)行時(shí)間

3.3 大規(guī)模算例實(shí)驗(yàn)結(jié)果

對(duì)于大規(guī)模算例，本文采用CVRPLIB中的X類數(shù)據(jù)集（Uchoa et al. Benchmark），選取X-n101-k25、X-n106-k14、X-n148-k46、 X-n181-k23、 X-n200-k36、 X-n237-k14、X-n303-k21，并進(jìn)行求解，結(jié)果如表2所示。

從圖5可以看出，在大規(guī)模算例上（n＞100），隨著客戶點(diǎn)數(shù)的增加，ADACO和GSACO的執(zhí)行時(shí)間呈指數(shù)增長，而本文所提算法的時(shí)間增加比率幾乎不變。這是因?yàn)榇藭r(shí)程序運(yùn)行的大部分時(shí)間都是算法執(zhí)行時(shí)間，同時(shí)Spark初始化、廣播時(shí)間和組間通信所用時(shí)間占比也變小了。因此Spark基于內(nèi)存的并行計(jì)算優(yōu)勢(shì)逐步體現(xiàn)出來。

▲圖5 大規(guī)模算例運(yùn)行時(shí)間

在101個(gè)點(diǎn)時(shí)，本文所提算法的執(zhí)行時(shí)間比ADACO快39.7%，比GSACO快29.0%。當(dāng)客戶點(diǎn)數(shù)增加時(shí)，如在200個(gè)點(diǎn)時(shí)，本文所提算法的執(zhí)行時(shí)間比ADACO快66.6%，比GSACO快60.1%。在300個(gè)點(diǎn)時(shí)，本文所提算法的執(zhí)行時(shí)間比ADACO快82.1%，比GSACO快79.7%。因此，SPAMACO更適合處理大規(guī)模算例，并且隨著算例規(guī)模的增加，時(shí)間提升效果明顯增加。

4 結(jié)束語

本文提出了一種基于Spark框架的自適應(yīng)蟻群算法SPAMACO，結(jié)合2-opt局部?jī)?yōu)化算子，在解決大規(guī)模CVRP上效果明顯。數(shù)值實(shí)驗(yàn)表明，該算法在大規(guī)模算例應(yīng)用上具有明顯優(yōu)勢(shì)。在保證時(shí)間優(yōu)勢(shì)的條件下，未來我們將進(jìn)一步探討最優(yōu)解。