李奕穎,秦 剛

1(中國科學院 計算機網絡信息中心,北京 100190)

2(中國科學院大學,北京 100049)

引言

車輛路徑問題是指在一個存在供求關系的系統中,在一定的約束條件下,合理安排車輛的行車路線和出行時間,把客戶需求的貨物從配送中心送達客戶,并使目標函數取得最優(yōu)化[1].隨著研究的深入和實際應用場景的需求,增加了對客戶偏好服務時間的約束,即個性化地限定了客戶被服務時間的范圍,延伸出了帶時間窗的車輛路徑問題(VRPTW),在實際生產應用中有廣泛應用,比如O2O 外賣配送、冷鏈物流、生產線上的工作調度、網絡路由策略等.

VRPTW 是NP-hard 的組合優(yōu)化問題[2],計算復雜度高,難以有效率地使用精確算法求得最優(yōu)解,目前的研究大多集中在如何設計高質量的啟發(fā)式算法,求取近似解以換取計算效率的提高,如蟻群算法[3]、粒子群算法[4]、遺傳算法[5]、模擬退火等群體智能算法.目前算法研究主要集中于兩方面,一是提升VRPTW 的求解精度,二是提升計算速度.

現階段VRPTW 求解存在的問題是:(1)算法過早收斂,易陷入局部最優(yōu)解；(2)相較于集中式節(jié)點分布,算法對隨機分布的節(jié)點處理精度差；(3)算法能處理的節(jié)點數少,一般為100 節(jié)點之內；(4)面對大規(guī)模問題出現單機處理效率瓶頸,忽視使用分布式平臺進行并行計算[6].針對上述問題,本文對蟻群算法進行改進,基于Spark平臺進行編程求解VRPTW,在Solomon benchmark 和Gehring & Homberger benchmark 上進行實驗,為快速有效地求解大規(guī)模VRPTW 提供了一種新思路.

1 傳統蟻群算法求解VRPTW

1.1 VRPTW 多目標0-1 規(guī)劃模型

VRPTW 可被定義為:某物流配送網絡中,記0 為配送中心,{ 1,2,···,n}為n個待配送客戶點,已知各客戶點的位置坐標為 (xi,yi) 、貨物需求為Di,允許的開始服務時間窗為[S Ti,ETi](i=1,2,···,n),安排裝載能力為Q的m輛車從0 出發(fā),共同完成對n個客戶的配送后回到起點0,優(yōu)化目標是最小化配送路徑長度和車輛數目.

由上述定義可知,VRPTW 是一個離散組合優(yōu)化問題,我們將其抽象為多目標0-1 規(guī)劃問題[6],其數學模型具體如下:

決策變量:

目標函數:

約束條件:

式(2)中l(wèi)ij為 點i和點j間路徑長度,ρ1和 ρ2分別為目標函數中路徑長度和車輛數目的優(yōu)化重要度,如ρ1∈[0,1]越大則表示以路徑長度最短為第一目標.約束目標中式(3) 表示車輛從 0出發(fā)并回到0 形成閉環(huán)；式(4) 表示各客戶點有且只有一輛車對其服務；式(5) 表示各車輛的載重約束；式(6) 表示時間窗約束；式(7)表示決策變量為0-1 變量.

1.2 傳統蟻群算法求解VRPTW

蟻群算法啟發(fā)于真實螞蟻自組織的覓食行為[3],對VRPTW 這種難解的離散優(yōu)化問題有優(yōu)秀的求解能力,得益于正負反饋機制的協同作用和其并行性.核心思想是:單只螞蟻在其走過的路徑上釋放信息素,根據信息素濃度和啟發(fā)式信息決策轉移路徑；螞蟻之間通過信息素進行通信,單次迭代后信息素進行揮發(fā)且增加優(yōu)秀路徑上的信息素濃度,使得大概率選擇目前優(yōu)秀解的同時擴展搜索范圍,通過多只螞蟻間相互協作多次迭代尋優(yōu).

蟻群算法是構建解和更新信息素的相互作用[7],具體如下:

(1)構建解:通過計算狀態(tài)轉移概率逐步構建完整解后,對解進行評估.狀態(tài)轉移概率公式見式(8):

其中,pij表示由節(jié)點i選 擇轉移到節(jié)點js 的概率；τij表示路徑(i,j)上 的信息素濃度；ηij表示路徑(i,j)的啟發(fā)式因子,通常是路徑長度的倒數；α和 β分別表示信息素和啟發(fā)式因子的重要程度.

(2)更新信息素:一次迭代后,根據解評估結果更新信息素濃度,之后繼續(xù)迭代尋優(yōu).信息素更新包括追溯增加和揮發(fā)減少兩種,具體見式(9):

其中,螞蟻t時刻位于節(jié)點i,t+1時 刻位于節(jié)點j,ρ表示殘留因子,△τij(t,t+1)表示信息素增量,(t,t+1)表示第k輛車信息素增量,通常為1/Ck,Ck為第k輛車路徑總長度.

傳統蟻群求解VRPTW 仍存在引言中提到的4 個共性問題,為了避免陷入局部最優(yōu),提升各類點分布和大數據下的求解精度和速度,下面提出基于Spark 平臺的改進蟻群算法求解VRPTW.

2 基于Spark 的改進蟻群算法求解VRPTW

2.1 算法思路

本文采用基于Spark 的改進蟻群算法求解帶時間窗車輛路徑問題,該算法從算法層和實現層進行改進,在算法層面,通過改進狀態(tài)轉移規(guī)則[8]、加入輪盤賭選擇機制、結合k-opt 鄰域搜索[9]進行路徑構建優(yōu)化,改進最大最小蟻群中的信息素更新策略,在實現層面,用Spark 計算平臺對改進蟻群算法并行實現,采用Spark 提供的API 對蟻群彈性分布式數據集(Resilient Distributed Dataset,RDD)進行操作,實現蟻群并行構建解的過程.

2.2 路徑構建優(yōu)化

蟻群算法是從最初的空解開始,逐步添加解成分直到構建完整解,只能生成數量有限的解,鄰域搜索最初依賴一個好的初始解,不斷通過局部調整嘗試改進當前解.本文采用蟻群算法和鄰域搜索相結合的方式進行路徑構建,通過狀態(tài)轉移規(guī)則和輪盤賭選擇機制構建初始解后,使用鄰域搜索進行局部優(yōu)化獲得高質量解.

針對VRPTW 問題,由于增加了時間窗約束,因此狀態(tài)轉移規(guī)則除了以信息素濃度高、路徑長度小為優(yōu)先選擇原則外,還要在滿足車載限制和時間窗的前提下,以等候時間短、時間窗緊為優(yōu)先選擇原則,則螞蟻由節(jié)點i選擇轉移到節(jié)點j的概率見式(10):

記tij為 到達節(jié)點j的時間,當tij≥S Tj時 ,等待時間為0,|tij-S Tj|+|tij-ETj|為時間窗大小,否則當tij＜S Tj時,|tij-S Tj|+|tij-ETj|為時間窗和等候時間的綜合指標.

在式(10)中參數α和β的作用如下:α 和β 分別表示信息素和啟發(fā)式因子的相對重要程度,如果α=0,則算法未使用信息素,而大概率地選擇距離最近的節(jié)點,屬于隨機貪心算法；如果β=0,則算法沒有任何啟發(fā)式信息帶來的偏向性,特別是當 α＞1時,所有螞蟻按照最初信息素濃度最大的同一條路徑移動,算法很快停滯于一個精度很差的解.因此這里選擇最大最小蟻群算法(MMAS)具有良好性能的參數設置:α取值1～2,β取值2～5.

若每次迭代均按照狀態(tài)轉移規(guī)則pij直接選擇最大概率的節(jié)點作為下一個待配送客戶,則信息素向局部最優(yōu)路徑聚集,使算法過早收斂停滯于次優(yōu)解,為了增加算法隨機性,本文使用輪盤賭選擇機制對路徑構建進行優(yōu)化,具體做法是:隨機選取一個實數T∈[0,1],分別減去各候選節(jié)點被選擇的概率pij,若T-pij≤0,則選擇城市j作為下一個配送節(jié)點,否則重復上述過程.

因此每只螞蟻的搜索過程是從候選節(jié)點中依據改進的狀態(tài)轉移規(guī)則并采用輪盤賭選擇機制選擇下一個待服務的節(jié)點,逐步添加解成分直至構成完整初始解,相較于傳統蟻群算法的初始解構建過程該方法可以得到更合理的初始解,狀態(tài)轉移規(guī)則改進后使得減少配送過程中車輛的等待時間并能根據顧客的具體時間需求調配配送方案,輪盤賭選擇機制增強了初始解選擇的隨機性,使得各節(jié)點均有概率被選中且被選擇的可能性與其狀態(tài)轉移概率成正比,能保持發(fā)現新路徑的能力,避免算法陷入局部最優(yōu).

獲得完整初始解后,通常用k-opt(k=2,3)局部搜索策略對當前解鄰域進行局部調整優(yōu)化,核心思想是任意選取k個點(a,b,···,k) ,刪除當前解中的相應k條邊[(a,a+1),(b,b+1),···,(k,k+1)],替換為相關節(jié)點重組的另外k條邊以期獲得更優(yōu)解,若當前解滿足k最優(yōu),則對k′＜k一定也滿足最優(yōu)[10],k-opt 的時間復雜度為O(nk),k越大時雖然效果越好但耗費的計算時間近似指數級增長[11],本文采用Lin 和Kernighan 提出的Lin-Kernighan(LK 算法)局部搜索策略處理大規(guī)模數據,在時間和求解效率間取得較好的平衡,LK 算法通過迭代、回溯不斷尋找邊yi代替初始路徑的邊xi,構成序列X=[x1,x2,···,xr]和Y=[y1,y2,···,yr],其中r不固定,是此序列的最大長度,具體的算法流程如圖1所示.

圖1 Lin-Kernighan 鄰域搜索算法程序

2.3 信息素更新優(yōu)化

通過上述路徑構建方法,每只螞蟻已經可以得到VRPTW 問題的一個較優(yōu)可行解,但是要想獲得精度高的解,還需要群體進行分布式學習的過程,螞蟻之間通過每輪迭代后的信息素更新來交互協作,其中信息素初始化、蒸發(fā)策略、更新策略都會影響算法尋優(yōu)能力[12].

本文選擇最大最小蟻群算法(MMAS)中的信息素更新策略,強調對最優(yōu)路徑區(qū)域的搜索,每輪迭代后只選擇一只構建出最優(yōu)路徑的螞蟻釋放信息素,最優(yōu)路徑分為迭代最優(yōu)TIbest和全局最優(yōu)TGbest,使用全局最優(yōu)更新規(guī)則會使得搜索加速集中到TGbest附近,而使用迭代最優(yōu)規(guī)則能相對減弱搜索導向性[13].針對節(jié)點數較多的情況,本文采用TIbest和TGbest輪流進行更新的策略.

信息素蒸發(fā)策略使得所有路徑上的信息素均隨時間而衰減,避免信息素在某些邊上無限積累或者快速減少[14].傳統蟻群算法中的信息素蒸發(fā)因子1-ρ為一個常數,當 ρ過大時,信息素留存持久度高,信息素在當前局部最優(yōu)路徑上聚集,正反饋作用增強,全局搜索能力差,當 ρ過小時,信息素衰減過快,留存時間少,信息素在路徑選擇過程中的作用降低,最終會導致算法收斂性降低,搜索時間過長且找不到最優(yōu)路徑.為了平衡全局搜索和正反饋尋優(yōu)能力,解決在迭代中后期出現長期找不到新的全局最優(yōu)解的問題,本文采用一種自適應信息素蒸發(fā)策略,見式(11),具體為在迭代初始采用較大的信息素殘留因子 ρmax,加速收斂且增強尋優(yōu)能力,隨后當全局最優(yōu)解的搜索停滯超過總迭代次數的1/10 時,自適應減少殘留因子,擴大搜索范圍,同時設置殘留因子的最小值ρmin.這里取最大殘留值ρmax=0.9,最小殘留值 ρmin=0.5,由于搜索停滯超過總迭代次數的1/10 時殘留因子自適應衰減,則至多衰減10 次,因此衰減系數為

通過信息素擇優(yōu)和衰減策略可以確定一輪迭代后每條路徑上的信息素濃度 τij,t次迭代后 τij的值為各條路徑上的信息素濃度差值過大會造成所有螞蟻向局部最優(yōu)路徑聚集,為了避免算法陷入停滯,這里采用MMAS 中對信息素濃度大小的限制[τmin,τmax],見式(12).

信息素初值 τ0一般將其設為略高于每次迭代中螞蟻釋放的信息素大小的期望值,若 τ0太小,信息素更新會有較強的引導性作用,搜索會快速集中到最初產生的幾條路徑上,導致搜索陷入局部空間,若 τ0太大,迭代初始階段收斂速度慢,直到信息素衰減后更新才開始發(fā)揮作用.本文取 τ0為 τmax,使得在循環(huán)初始階段,具有很強的探索性.

2.4 基于Spark 平臺并行化

目前VRPTW 問題的許多實際應用面對爆炸式的數據增長和實時性求解的要求,出現單機求解的效率瓶頸,而蟻群算法是一個分布式學習的過程[15],有內在的并行性,每次迭代中多只螞蟻獨立的根據規(guī)則同時同地的構建可行解,因此本文將基于Spark 分布式平臺來實現該算法.

Spark 是一個快速且通用的集群計算平臺,擴充了Map-Reduce 計算模型,與Hadoop 不同的是多個任務之間數據通信不需要借助硬盤而是通過內存,減少了IO 時間,提高了程序的執(zhí)行效率[16].Spark 的核心概念是RDD,RDD 的一大特性是分布式存儲,每個RDD可以在不同工作節(jié)點存儲并計算,另一大特性是延遲計算,一個完整的RDD 運行任務被分為Transformation和Action 兩部分[17],Transformation 創(chuàng)建RDD,同時提供map、filter、join 等大量操作方法生成新的RDD,Action 通過執(zhí)行count、reduce、collect 等方法真正執(zhí)行數據的計算部分.

本文將螞蟻封裝為Ant 類,可行路線的搜索過程實現在Ant 類的search()方法中,實例化n個Ant 對象生成蟻群,蟻群間通過ant.set_parameter 方法共享參數,利用Spark 的parallelize()方法將蟻群轉換為分布式的RDD,在每輪迭代中通過Spark 中的map()方法實現n只螞蟻的并行search()過程,一輪迭代結束后通過Spark 中的collect()方法收集蟻群計算結果,得到本輪最優(yōu)結果后統一更新參數,核心計算過程如圖2所示,從而實現蟻群分布式并行構建可行解,提升計算效率.

圖2 Spark 核心計算過程

2.5 算法描述

基于Spark 的改進蟻群算法對VRPTW 的求解流程如圖3所示.

圖3 基于Spark 的改進蟻群算法求解VRPTW 流程圖

具體算法步驟如算法1.

算法1.基于Spark 的改進蟻群算法(1) 讀入算例文件,初始化車輛數m、車輛容量load,構造地圖(橫坐標x、縱坐標y、需求demand、最早開始時間ready、最晚結束時間due、服務時間service_time),并計算地圖上各節(jié)點間距離；(2) 采用最近鄰貪心算法獲得初始可行解和初始路徑長度 C 0；(3) 實例化參數類,設置α,β,ρ,τ0 等參數,基于初始路徑長度設置信息素初值τ0τmax=1/C0,生成全局參數；(4) 將螞蟻封裝為Ant 類,根據螞蟻數目實例化數個Ant 對象生成蟻群ants,通過ant.set_parameter方法設置每只螞蟻的參數,利用Spark 的parallelize(ants)方法將蟻群轉換為分布式的RDD；(5) 在每輪迭代中通過Spark 中的map()方法實現n 只螞蟻的并行search()過程,每只螞蟻search()方法如下:① 初始化當前路徑road,加入原點,設置當前時間current_time=0車輛剩余負載remaind_load=load；② 構造候選節(jié)點集,滿足負載、時間窗要求；③ 從候選節(jié)點中依據狀態(tài)轉移規(guī)則(10)并采用輪盤賭選擇下一個需要服務的節(jié)點next 并加入當前路徑中；④ 若next 節(jié)點為空,將路徑加入路徑集中,新派遣一輛車,置current_time=0,remaind_load=load；⑤ 判斷是否還有未服務的點,若存在則返回步驟(1),否則結束,

搜索.(6) 每輪迭代結束后通過Spark 中的collect()方法收集蟻群計算結果,對每只螞蟻搜索得到的可行解進行排序,根據圖1對迭代最優(yōu)解進行k-opt 局部調整優(yōu)化；(7) 得到迭代最優(yōu)解后通過ant.set_parameter 方法統一更新參數,各路徑信息素濃度更新公式參考式(9)、(11)、(12),采用TIbest 和TGbest 輪流進行更新、自適應信息素蒸發(fā)策略且限制信息素范圍為[τmin,τmax]；(8) 判斷迭代是否終止,迭代終止輸出全局最優(yōu)解,否則返回步驟(4)繼續(xù)并行化求解.

3 實驗設計及結果分析

為測試基于Spark 的改進蟻群算法對VRPTW 的求解效果,本文在物理機上利用Virtual Box 構建3 臺虛擬機搭建Spark 集群,并分別在單臺虛擬機和Spark集群上進行實驗.

3.1 實驗環(huán)境及算例說明

實驗環(huán)境如下:

(1) 單機運行環(huán)境

操作系統:Ubuntu 16.04.

硬件環(huán)境:Virtual Box 虛擬機.

Intel Core i7.

2GB 內存.

(2) Spark 集群運行環(huán)境

操作系統:Ubuntu 16.04.

硬件環(huán)境:Virtual Box 虛擬機.

Intel Core i7.

2GB 內存.

部署方式:Standalone 模式.

集群規(guī)模:1 臺Master,2 臺Slave.

實驗采用Solomon benchmark 和Gehring &Homberger benchmark 兩個國際通用基準算例庫中的數據,數據集按照影響VRPTW 求解的地理數據分布、客戶節(jié)點數、時間窗松緊程度、車輛載重上限4 個因素進行分類,Solomon 數據集規(guī)模包括25、50、100 節(jié)點數,標號為X1X2X3X4,X1取值R、C、RC,分別表示客戶節(jié)點隨機、聚集、混合分布,X2表示車輛載重,取值0 或1,X3X4取值一個兩位十進制數,表示時間窗松緊程度,Gehring & Homberge 數據集是大規(guī)模數據集,包括200、400、600、800、1000 節(jié)點數.數據包含車輛數上限、載重上限、客戶位置坐標、客戶需求量、時間窗、服務時間[18].

3.2 實驗設計及結果分析

3.2.1 信息素矩陣可視化表達

為直觀表達蟻群算法求解VRPTW 的行為,選取Solomon-r101 的前25 節(jié)點進行求解并給出信息素矩陣的可視化表達,信息素含量被轉化成灰度值,顏色越暗的方格所對應的信息素值越高,在第0、10、100 次迭代之后的實驗效果如圖4.

圖4 信息素矩陣可視化表達

由圖4可以看出,主對角線的單元格始終為白色,表示這些單元格的信息素被初始化為0 并且永不更新,其余單元格初始為黑色表示 τ0=τmax,隨著迭代過程反復執(zhí)行,單元格間的信息素含量差異越來越大,最后只有少數邊含有較高信息素而被選擇為全局最優(yōu)解.

3.2.2 收斂性比較實驗

為驗證本算法的改進效果,分別將不同信息素更新策略、不同鄰域搜索方法作為控制變量進行實驗.選取Solomon-c101 和Gehring & Homberger-c121 作為實驗數據,分別采用信息素全局更新和交替更新的求解收斂過程如圖5,選取Gehring & Homberger-rc121作為實驗數據,分別采用2-opt、3-opt、k-opt 這3 種鄰域搜索的求解收斂過程如圖6.

由圖5可以看出,對100 節(jié)點數據,信息素更新方式對求解過程無明顯影響,而對200 節(jié)點數據,采用全局信息素更新方式使得求解陷入局部最優(yōu)解而過早收斂,采用信息素交替更新方式能在執(zhí)行結束后得到更高質量的解.由圖6可以看出,使用k-opt 進行局部搜索優(yōu)化比2-opt 和3-opt 得到的解的精度高.綜上,改進蟻群算法求解較大規(guī)模VRPTW 時在迭代初期收斂速度較快,在迭代中后期能保持全局搜索能力使求解持續(xù)收斂,最終在期望的時間內收斂于一個精度較好的近似解.

圖5 不同信息素更新策略收斂過程

圖6 不同鄰域搜索收斂過程

3.2.3 求解精度比較實驗

為驗證本算法的求解精度,選取Solomon 節(jié)點數為100 的各類數據和Gehring & Homberger benchmark節(jié)點數為200 及400 的大規(guī)模各類數據進行測試,參數設置為:α =1,β =2 ,ρ =0.9,迭代400 輪計算與當前最優(yōu)解的誤差率見表1.

由表1可以看出,對100 以內小規(guī)模問題求解的精度基本可達最優(yōu)解；對混合分布的RC 類問題求解精度有明顯提升；對隨機分布的R 類問題誤差率仍較高,尤其是對車輛載重小且最大可服務時間短的R1 類問題精度更差,原因是該類問題節(jié)點的隨機分布增大了路徑構造的難度,各子路線可能包含的節(jié)點數差異大；對200、400 節(jié)點的大規(guī)模問題在計算速度提升的前提下精確度在可接受的誤差范圍內.

表1 100、200、400 數據量求解精確度實驗結果

3.2.4 求解速度比較實驗

為比較單機求解和基于Spark 平臺并行求解的求解效率,選取客戶數為25、50、100、200 以及400 的Solomon-r101、Gehring & Homberge-R1_2_1、Gehring& Homberge-R1_4_1 作為實驗數據,基于相同參數和迭 代輪數進行實驗,實驗結果如圖7.

圖7 求解速度比較實驗結果

從圖7可以看出,當問題規(guī)模較小時,由于Spark 內部的通信消耗,基于Spark 的并行蟻群算法的求解效率較單機蟻群算法沒有顯著的提升,而當問題規(guī)模逐步增大時,基于Spark 的并行蟻群算法的求解時間要顯著少于單機算法的求解時間,并行算法的加速比逐步增加,當客戶數為400 時,并行算法的加速比為1.95.

4 總結與展望

本文設計了一種基于Spark 的改進蟻群算法求解帶時間窗的車輛路徑問題,根據改進的狀態(tài)轉移規(guī)則和輪盤賭選擇機制構建初始解,結合k-opt 鄰域搜索進行局部搜索優(yōu)化,采用全局最優(yōu)解和局部最優(yōu)解交替更新策略、自適應信息素蒸發(fā)策略改進最大最小蟻群算法中的信息素更新策略,借助Spark 計算平臺,將蟻群封裝為彈性分布式數據集,實現螞蟻的并行搜索.

實驗結果表明本算法對100 以內小規(guī)模問題求解的精度基本可達最優(yōu)解,對混合分布的RC 類問題求解精度有提升,對200、400 節(jié)點的大規(guī)模問題求解效率有明顯提升.因此把蟻群算法這樣的啟發(fā)式算法和鄰域搜索相結合是解決優(yōu)化問題的有效途徑,另外利用Spark 分布式平臺處理蟻群算法中耗時的迭代過程可以有效降低計算時間.

本文試圖對C、R、RC 類VRPTW 問題同時取得較好的優(yōu)化效果,但對R 類分布的節(jié)點求解精度還不理想,今后可結合其它群體智能算法或者根據隨機分布類問題的特點進行合適的參數調整對R 類VRPTW問題進行進一步優(yōu)化求解.另外本文尚未對600、800、1000 等更大規(guī)模節(jié)點進行實驗,今后可以通過改進算法、充分利用分布式平臺、提升硬件環(huán)境來解決更復雜的大規(guī)模求解問題.