基于自適應動態搜索蟻群算法的車輛路徑規劃

賀智明，鄭 麗，梁 文

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

0 引 言

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

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

1 模型建立

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

1.1 模型假設

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

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

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

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

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

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

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

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

1.2 符號說明

該模型包含的相關符號說明見表1。

表1 相關符號說明

1.3 設定目標優化函數

首先，決策變量如下

目標優化函數如式(1)所示

(1)

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

(2)

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

相關約束條件如式(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)表示兩個變量之間的關系；式(9)和式(10)表示兩變量均滿足0-1約束；式(11)表示配送過程中不存在回路現象。

2 ADACO算法

2.1 基本蟻群算法

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

圖1 ACO算法的基本邏輯結構

2.2 基本算法模型

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

(12)

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

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

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

(13)

(14)

(15)

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

2.3 ADACO算法設計

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

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

(16)

(17)

(2)信息素強度的動態調整

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

(18)

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

(19)

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

(20)

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

2.4 ADACO算法描述

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

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

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

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

(1) nc=1

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

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

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

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

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

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

(8) end if

(9) end forj

(10) forj= 1:Jk(i)

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

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

(13) else

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

(15) end if

(16) end forj

(17) end whileτk

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

(19) end fork

(20) 依據式(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)步單只螞蟻構造解的時間復雜度為O(n2)，第(3)-第(19)步o只螞蟻構造解的時間復雜度為O(o·n2)，第(2)-第(23)步o只螞蟻經過iterations次循環的時間復雜度為O(o·n2·iterations)。由此可以看出ADACO算法較原有算法沒有增加多余的時間開銷，由此驗證該算法的可行性。

3 實驗計算與分析

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

3.1 案例描述

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

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

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

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

3.2 參數設置

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

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

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

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

其中，最差、平均、最優路徑長度以及差值分別表示10次運行結果中的最大值、平均值、最小值、最大值與最小值之差。差值越小，說明系統越穩定，解的質量也越好。上述實驗結果可以看出3個關鍵參數的最佳配置為：α=1，β=4，ρ=0.7。

結合案例，其它相關實驗參數設置見表3。

3.3 案例驗證及結果分析

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

表3 相關實驗參數設置

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

表4 各算法的運行結果比較

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

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

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

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

圖5 ACO算法規劃的配送路線及配送成本

圖6 AACO算法規劃的配送路線及配送成本

圖7 DACO算法規劃的配送路線及配送成本

圖8 ADACO算法規劃的配送路線及配送成本

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

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

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

4 結束語

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