基于自適應動態(tài)搜索蟻群算法的車輛路徑規(guī)劃

賀智明，鄭 麗，梁 文

(江西理工大學 信息工程學院，江西 贛州 341000)

0 引 言

車輛路徑問題(vehicle routing problem，VRP)是指一組車輛從指定點出發(fā)，且遍歷到一系列特定點的路線[1]。由于該問題的傳統(tǒng)求解方法效果不佳，如精確算法[2]和啟發(fā)式算法[3,4]。因此，學者們將AI技術(shù)與啟發(fā)式算法結(jié)合，如：模擬退火算法[5]、禁忌搜索算法[6]、遺傳算法[7]和蟻群算法[8]等。相對而言，蟻群算法(ant colony，ACO)在尋徑方面占據(jù)獨特優(yōu)勢。然而，當問題規(guī)模較大時，算法易陷入局部困境，無法對搜索空間進行深層次挖掘。為此，學者們做出不同的改進，例如：文獻[9]將人工免疫和ACO算法相結(jié)合，有效解決緊急糧食分配問題；徐坤等[10]將信息素揮發(fā)因子采用萊維飛行模式更新，提高了算法的全局尋優(yōu)能力；王飛鵬等[11]在求解TSP問題的最優(yōu)解集中按比例選取部分解集構(gòu)造近似骨架，并基于近似骨架對問題分段求解，有效解決算法精度不高等問題。

上述改進方法主要通過改變部分更新規(guī)則或同其它算法互補。然而ACO算法中關(guān)鍵參數(shù)的設置以及群體的合作行為都直接影響著算法性能。為此，本文提出自適應動態(tài)搜索蟻群算法(ADACO)，通過實驗性配置關(guān)鍵組合參數(shù)和自適應偽隨機策略協(xié)助群體選擇合理的轉(zhuǎn)移方向。此外，信息素強度的分段化設定有效預防了群體長時間滯留于困境中而無法跳脫的現(xiàn)象，減少了時間開銷。

1 模型建立

本小節(jié)針對車輛路徑問題建立數(shù)學模型，其中包括模型假設、符號說明和目標優(yōu)化函數(shù)的設定。

1.1 模型假設

依據(jù)實際問題對該模型做出如下假設：

(1)指定配送中心負責完成一系列需求點的配送服務；

(2)配送中心以及各個需求點的相對地理位置和對應需求量是明確給定的；

(3)車輛配送完畢，返回指定配送中心；

(4)配送車輛是同種規(guī)格，不存在些許誤差；

(5)不考慮城市交通堵塞問題；

(6)配送車輛始終以勻速行駛，單位距離內(nèi)的配送成本是等同的，因此行駛距離可代表配送成本；

(7)每個需求點當且僅當由一臺配送車輛服務，且該車輛服務的所有需求點的需求量之和小于或等于車輛的額定限載量。

1.2 符號說明

該模型包含的相關(guān)符號說明見表1。

表1 相關(guān)符號說明

1.3 設定目標優(yōu)化函數(shù)

首先，決策變量如下

目標優(yōu)化函數(shù)如式(1)所示

(1)

其中，cij計算如式(2)所示

(2)

cok表示配送中心調(diào)度成本；cs表示單位距離內(nèi)車輛行駛成本；當i=0時，需要配送車輛越多，總的成本也隨之增加。由式(2)可知，減少配送車輛的派遣數(shù)量以及縮短車輛的行駛距離是降低配送成本的關(guān)鍵所在。

相關(guān)約束條件如式(3)至式(11)所示

(3)

(4)

(5)

(6)

(7)

(8)

xijk(xijk-1)=0，i=1,2,…,n
j=1,2,…,nk=1,2,…,m

(9)

yik(yik-1)=0，i=1,2,…,nk=1,2,…,m

(10)

(11)

其中，式(1)表示配送總成本達到最??；式(2)表示成本費用計算；式(3)表示車輛k單次累計配送量不高于車輛額定限載量；式(4)表示車輛k單次累計配送距離不超過車輛最大限定行駛距離；式(5)表示單個需求點i僅由一臺車輛負責配送；式(6)表示共有m臺車輛參與配送；式(7)和式(8)表示兩個變量之間的關(guān)系；式(9)和式(10)表示兩變量均滿足0-1約束；式(11)表示配送過程中不存在回路現(xiàn)象。

2 ADACO算法

2.1 基本蟻群算法

M.Dorigo，V.Maniezzo和A.Colorni等意大利學者長期研究自然界中蟻群覓食尋徑行為，發(fā)現(xiàn)不管地理環(huán)境多復雜，蟻群經(jīng)常能克服重重困難和阻礙，在洞穴和食物之間找到一條最佳路徑。究其根本，螞蟻在走過的路上均會放置一種稱之為“信息素”的分泌物質(zhì)。某條路徑上經(jīng)過的螞蟻越多，分泌物則堆積越多，分泌物的濃度也會不斷增強。此外，螞蟻對該分泌物具有一定的感知能力，它們會根據(jù)路徑上分泌物濃度的高低去選擇路徑。然而，隨著時間的逐步增加，分泌物質(zhì)會出現(xiàn)漸進式蒸發(fā)現(xiàn)象。因此，路徑上剩余分泌物質(zhì)濃度的高低與吸引后來螞蟻數(shù)量的多少成正比，從而形成一種正反饋機制。這種機制能夠幫助蟻群在“深度挖掘”和“合理利用”之間尋求一個最佳臨界點，即時找到最佳路徑。為此，學者們多次模擬該生物相互合作的社會性和組織性群體行為，最終在20世紀90年代初期提出啟發(fā)式ACO算法[8]。圖1從整體視角規(guī)劃出該算法的邏輯結(jié)構(gòu)，為解決實際問題提供了清晰而有力的幫助和支持。

圖1 ACO算法的基本邏輯結(jié)構(gòu)

2.2 基本算法模型

ACO算法一經(jīng)提出，學者們紛紛將蟻群尋徑思想運用到經(jīng)典TSP問題上。近些年來，學者們又在單回路TSP問題上逐步衍生出多回路TSP問題，即VRP問題。換言之，TSP是VRP的基礎(chǔ)問題。因此,本小節(jié)以求解TSP的ACO算法為基礎(chǔ)建立求解VRP的ACO算法模型。

(12)

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

當所有螞蟻均實現(xiàn)遍歷任務后，各條路徑上的信息素數(shù)量根據(jù)式(13)和式(14)更新

τij(t+n)=(1-ρ)τij(t)+Δτij(t)

(13)

(14)

(15)

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

2.3 ADACO算法設計

針對ACO算法的不足，本文基于原有算法的框架做出一些改進，以提高算法的性能和效率。

本文采用隨機性選擇和確定性選擇相結(jié)合的策略，并自適應性調(diào)整轉(zhuǎn)移概率，引導算法探索最優(yōu)路徑和提高算法的收斂性能。詳細地講，算法在搜索之前，根據(jù)式(16)中的偽隨機分布轉(zhuǎn)移規(guī)則(pseudo-random distribution transition rule，PRDTR)先執(zhí)行狀態(tài)轉(zhuǎn)換的選擇操作，使得搜索個體更加傾向于選擇信息素累積量多且距離較近的城市j

(16)

(17)

(2)信息素強度的動態(tài)調(diào)整

由式(12)可知，當α=0時，只有路徑啟發(fā)信息β發(fā)揮著作用，此時算法等同于最短路徑尋優(yōu)，如式(18)所示

(18)

當β=0時，路徑啟發(fā)信息β為0，只有路徑信息因子α引導搜索個體進行單純性地隨機搜索，如式(19)所示

(19)

為使算法能夠在α和β的相互作用下始終維持在“深度探索”和“合理利用”的臨界點。本文采用式(20)中的分段函數(shù)Qi替代式(15)中的常數(shù)Q，使得路徑上信息素數(shù)量變化時，群體均能夠有根據(jù)地選擇路徑，改善了群體尋徑時的盲目性選擇

(20)

其中，式(20)對應著不同區(qū)間內(nèi)的不同取值。當函數(shù)最優(yōu)值在某一時間段內(nèi)持續(xù)沒有變化，說明整個搜索過程可能陷入局部誤區(qū)，此時分段函數(shù)的設定強制增加或減少路徑上信息素數(shù)量的導向，賦予算法跳出局部誤區(qū)的能力。

2.4 ADACO算法描述

通過2.1至2.3小節(jié)對基本ACO算法、算法模型及其改進方面的詳細介紹，本文提出ADACO算法，且該算法求解車輛路徑問題的偽代碼描述如下：

算法1：求解車輛路徑問題的ADACO算法

輸入：目標優(yōu)化函數(shù)minZ，關(guān)鍵參數(shù)α、β、ρ，最大迭代次數(shù)iterations，起始點螞蟻只數(shù)o等各項相關(guān)實驗參數(shù)，起始點和一系列需求點的位置坐標、相應需求量。

輸出：全局配送方案及配送成本

(1) nc=1

(2) while nc≤iterations// 停滯條件

(3) for k=1：o// 對o只螞蟻循環(huán)

(4) whileτk=0 // 禁忌表為0

(5) for j=1:n// 對n個需求點循環(huán)

(6) if 禁忌表τk中不包含需求點j

(7) 將需求點j添加到待訪問需求點列表Jk(i)中

(8) end if

(9) end forj

(10) forj= 1:Jk(i)

(11) if 剩余車載量≥待訪問需求點的需求量

(12) 根據(jù)式(16)選擇待訪問需求點j， 計算裝載距離，并更新禁忌表τk和待訪問需求點列表Jk(i)

(13) else

(14) 起始點重新發(fā)出一臺車且車輛編號加1， 按照式(16)和式(17)繼續(xù)遍歷剩余的待訪問需求點j

(15) end if

(16) end forj

(17) end whileτk

(18) 計算構(gòu)造解的路徑長度， 即配送成本

(19) end fork

(20) 依據(jù)式(13)-式(15)和式(20)更新各路徑信息素增量Δτij， 進而更新全局路徑信息素τk

(21) nc = nc +1

(22) 清空禁忌表τk

(23) end while nc

(24) 輸出最佳配送方案以及對應的配送成本

針對上述偽代碼的描述，分析其時間復雜度：第(5)-第(9)步設置待訪問需求點列表的時間復雜度為O(n)，第(10)-第(16)步單只螞蟻通過自適應偽隨機選擇并遍歷需求點的時間復雜度均為O(n)，第(4)-第(17)步單只螞蟻構(gòu)造解的時間復雜度為O(n2)，第(3)-第(19)步o只螞蟻構(gòu)造解的時間復雜度為O(o·n2)，第(2)-第(23)步o只螞蟻經(jīng)過iterations次循環(huán)的時間復雜度為O(o·n2·iterations)。由此可以看出ADACO算法較原有算法沒有增加多余的時間開銷，由此驗證該算法的可行性。

3 實驗計算與分析

為了驗證算法改進前后的高效性，本文采用鄭州市“家輝生鮮”連鎖店貨物配送問題作為實驗案例，其測試環(huán)境：Windows操作系統(tǒng)；i5處理器；雙核2.5G CPU；4.0 G內(nèi)存；1 T硬盤；MATLAB R2016a仿真平臺。

3.1 案例描述

該連鎖店的倉庫每天都會向各個連鎖分店進行生鮮補給，最大化滿足廣大顧客的生活需求。以下是通過高德地圖獲取到倉庫以及20個分店的相對位置，如圖2所示。編號1-20是各個連鎖店的分布位置，“★”代表倉庫的位置。

圖2 倉庫及連鎖分店的分布位置

為了方便測試，將倉庫及各個連鎖分店的位置坐標映射至XOY平面上，其中倉庫編號為0，對應的位置坐標為(100,400)。各連鎖分店的位置坐標及對應的每日需求補給量見表2，表2中的位置坐標信息轉(zhuǎn)化到直角坐標系上，如圖3所示。

表2 連鎖分店位置坐標及補給量

3.2 參數(shù)設置

ACO算法中，龐大的參數(shù)系彼此關(guān)聯(lián)，密切影響著算法的性能，其中起主要作用的參數(shù)分別為：路徑信息素因子α、路徑啟發(fā)因子β和信息素蒸發(fā)比例ρ。因此，α、β以及ρ的組合配置是衡量算法性能指標和求解效率的關(guān)鍵因素。

圖3 直角坐標系下倉庫及連鎖分店的位置分布

為了得到組合參數(shù)的最佳配置，本小節(jié)在上述測試案例的TSP問題上進行實驗，按照修改一個參數(shù)的值，另外兩個參數(shù)值保持不變的規(guī)則斟酌最佳參數(shù)的設定。初始默認參數(shù)為α=1，β=1，ρ=0.7，iterations為100次，每組實驗分別運行10次，實驗結(jié)果如圖4所示。

圖4 α、β、ρ的不同配置對算法性能的影響

其中，最差、平均、最優(yōu)路徑長度以及差值分別表示10次運行結(jié)果中的最大值、平均值、最小值、最大值與最小值之差。差值越小，說明系統(tǒng)越穩(wěn)定，解的質(zhì)量也越好。上述實驗結(jié)果可以看出3個關(guān)鍵參數(shù)的最佳配置為：α=1，β=4，ρ=0.7。

結(jié)合案例，其它相關(guān)實驗參數(shù)設置見表3。

3.3 案例驗證及結(jié)果分析

本小節(jié)在“家輝生鮮”實際案例中，對4種算法進行測試和對比分析。其中，對改進的兩個方面分別測試，得到自適應轉(zhuǎn)移蟻群算法(AACO)和動態(tài)導向蟻群算法(DACO)，另外兩組則為ACO算法和ADACO算法。

表3 相關(guān)實驗參數(shù)設置

表4列出了4種算法各自運行10次所對應的配送成本、收斂代數(shù)以及CPU運行時間。在配送成本和收斂代數(shù)兩方面，ACO算法的配送成本大多集中于4750附近，最大值為4758，最小值為4744，始終沒有一個較大的突破，收斂代數(shù)也呈現(xiàn)跌宕起伏的狀態(tài)，不具穩(wěn)定性；AACO算法的配送成本則相對穩(wěn)定，主要趨于4729附近，其中配送成本為4725的概率占據(jù)30%，收斂代數(shù)同樣沒有明顯的規(guī)律性；DACO算法得到的配送成本較于前兩者更具穩(wěn)定性，始終維持在4710-4715之間，且4710出現(xiàn)的概率為40%，迭代次數(shù)也相應收斂于30代。對比前三者可知，ADACO算法不僅在配送成本方面則有了一個實質(zhì)性的進展和突破，不再局限于4700的約束，且以50%的概率歸攏于4674，而且最佳的收斂代數(shù)曾達到26.26。此外，10次運行結(jié)果中，4種算法的CPU運行時間都是參差不齊的，但是觀察其最佳值、平均值和最差值，ACO算法均高于其它3種算法，而ADACO算法則略勝一籌。

表4 各算法的運行結(jié)果比較

通過對4種算法運行10次結(jié)果的縱橫對比以及多方面分析，得到AACO算法、DACO算法和ADACO算法較于ACO算法的提升力度和改進空間，見表5，ADACO算法提升力度尤為明顯。

表5 各類算法較于ACO算法的提升力度/%

對照表4中的相關(guān)數(shù)據(jù)，圖5給出了ACO算法中最差配送方案及其對應且出現(xiàn)次數(shù)最多的配送成本和收斂代數(shù)。圖6-圖8則給出了其它3種算法的最佳配送方案、配送成本以及收斂代數(shù)。

觀察圖5-圖8可得，4種配送方案中2號和4號車輛的行駛路線一致，1號和3號車輛的行駛路線稍有差別，配送成本也是各不相同。其中，各方案中單位車輛的行駛路線及配送成本見表6，圖9也直觀地展示了4種方案的細微差別。對照圖表，并結(jié)合相關(guān)實驗數(shù)據(jù)綜合性地研究和分析，ACO算法在第32代繪制出最佳配送方案，如圖5(a)所示。表6顯示了該算法中1號車輛的行駛路線為：0-20-16-14-13-12-0，該車輛在遍歷完20號、16號分店后轉(zhuǎn)向14號分店，直接違背了公理“兩點之間線段最短”，由此可以判定該路線不是最優(yōu)的。此外，從圖5(b)可以看出，該算法在第5代的配送成本幾乎接近4710，有突破瓶頸的跡象，然而卻沒能穩(wěn)定于這一點，而且算法長期處于動蕩搜索狀態(tài)，最終歸攏于4758，說明該算法具有一定的提升空間；AACO算法和DACO算法分別在第29代和第31代繪制出最佳配送方案，如圖6(a)和圖7(a)所示。對比這兩種配送方案，清晰地看到兩者之間僅3號車輛的行駛路線略有不同，但總的配送成本卻相差15，這項差值充分說明DACO算法中3號車輛的行駛路線是可取的。從圖6(b)可得知，AACO算法同比ACO算法在收斂代數(shù)上縮短了9.68%，并降低了0.69%的配送成本。圖7(b)清楚顯示DACO算法在第20代有陷入局部困境的跡象，但信息素強度區(qū)間性設置引導群體在第30代及時逃離困境構(gòu)造新的解，并且配送成本最終降低并穩(wěn)定于4710；圖8顯示ADACO算法的最佳配送方案于第27代繪制完畢，同圖7(a)相比，兩者僅1號車輛的行駛路線不同，然而對應的配送成本卻迅速降低到4674，而且也不存在交叉或ACO算法中1號車輛的繞路現(xiàn)象，由此可判斷ADACO算法1號車輛的配送路線為最佳路線。此外，ADACO算法中3號車輛的行駛路線與DACO算法相同，均為可取路線。

圖5 ACO算法規(guī)劃的配送路線及配送成本

圖6 AACO算法規(guī)劃的配送路線及配送成本

圖7 DACO算法規(guī)劃的配送路線及配送成本

圖8 ADACO算法規(guī)劃的配送路線及配送成本

表6 單位車輛具體配送方案及配送成本

圖9 4種算法單位車輛的配送成本

綜上所述，AACO算法和DACO算法較于原有算法在時間效率和配送成本方面均有小幅度提升，然而卻遠遠不夠。通過將兩種改進方法進行有效結(jié)合，吸收兩者優(yōu)點得到ADACO算法，而且ADACO算法也展示了具有突破性進展的優(yōu)化效果以及全面的提升能力。由此可見，ADACO算法在求解車輛路徑問題上更具高效性。

4 結(jié)束語

針對原有算法求解車輛路徑問題時的不足，本文在初始時刻對關(guān)鍵參數(shù)采用試湊法設定，保證群體充分利用有效信息。迭代初期引入時變參數(shù)，并在擇徑之前產(chǎn)生一個隨機數(shù)與之比較，使得群體按照既定的偽隨機自適應規(guī)則選擇轉(zhuǎn)移方向。當算法狀態(tài)持久不變時，信息素強度的分段化有效誘導群體跳脫困境繼續(xù)探索。最后基于測試案例對優(yōu)化前后的算法進行多次仿真，結(jié)果表明所提算法規(guī)劃的配送方案最優(yōu)，大幅度縮減了配送成本和時間開銷。本文算法適用于以菜鳥驛站為代表的物流業(yè)務，為了滿足多元化需求，派送和拾取同步進行且增加時間窗的服務將作為下一步的研究方向。