基于群智能混合算法的物流配送路徑研究

朱亞琪，方建安

0 引言

車輛路徑問題（Vehicle Routing Problem, 簡稱VRP）是物流系統研究中的一項重要內容，根據車輛路徑模型，可以將其轉化為TSP問題。蟻群算法在解決旅行商（TSP）等著名問題時，已得到了卓有成效的應用，但解決大規模問題時，其收斂速度較慢且耗時較長[1]。

粒子群優化算法（PSO）[2,3]是一種全局優化算法，由Eberhart和Kennedy于1995年提出的。該算法的優點：1) 具有較大范圍的全局搜索能力；2) 搜索從群體出發，具有穩定性；3) 搜索使用評價函數值啟發；4) 收斂速度快，參數調整簡單；5) 具有可擴展性, 容易與其他算法結合。存在的缺點是：在算法后期的局部搜索能力差，反饋信息利用不充分。

差分進化法可以解決不可微分非線性函數最優化問題，采用隨機直接搜索法，利用上、下代問的競爭原理，收斂速度快，同時族群多樣性大幅度減小，但存在收斂過早、易陷入局部最優等問題。文獻[4]則提出改進差分進化法，稱為混合差分進化法（hybrid differential evolution method），然而，混合差分進化法的突變操作共有5種方法，本文根據蟻群算法的特點，在混合算法中使用螞蟻系統搜尋適當的突變操作，以利于加速算法搜索全局最優解。

本文提出一種雙種群蟻群算法，在蟻群的基礎上引入差分進化（DE）和粒子群算法（PSO）。通過在 PSOAS種群和 DEAS種群之間建立一種信息交流機制，使信息能夠在兩個種群中傳遞，以免某一方因錯誤的信息判斷而陷入局部最優點。

1 物流配送的路徑問題

為了降低服務商的運營成本，物流系統都會在車輛配送路徑上做優化。選取合適的運輸路線，可以加快對客戶需求的響應速度，提高服務質量，增強客戶對物流系統的滿意度。車輛路徑問題，一般定義為對一系列發貨點和/或收貨點，組織適當的行車路線，使車輛有序地通過它們，在滿足一定的約束條件下，達到一定的目標（如路程最短、費用最小、時間盡量少、使用車輛盡量少等）。

物流配送路徑問題，實際上是旅行商(Traveling Sales-man Problem, TSP)的問題，對TSP的問題描述如下：一個貨郎要走訪 N個橙色，每個城市必須經過一次且只能經過一次，最后回到出發的城市，就算是完成了一次旅行，找到一條最短的路徑。其相應數學描述如下：設有一城市集合，每對城市間的距離為。求一條經過C中每個城市正好一次的最短路徑。

2 蟻群算法

蟻群算法（Ant Colony Algorithm, ACA）于20世紀90年代由Colony等提出，該算法模擬蟻群的群體協作覓食過程，由若干個螞蟻共同構造解路徑，通過在解路徑上遺留并交換信息素提高解的質量，進而達到優化的目的。由于物流配送路徑問題實際上是一個旅行商問題，下面以 TSP為例介紹算法內容：

設m是蟻群中螞蟻的數量，dij是城市i與j之間的距離，ηij(t)=1/dij為啟發函數；τij是t時刻路徑(i,j)上的信息量；pijk(t) 表示在t時刻螞蟻k由城市i轉移到城市j的概率，公式（1）

其中，j是尚未訪問的城市；allowedk={C-tabuk}表示螞蟻k下一步允許選擇的城市；α和β為啟發式因子；tabuk(k=1,2,…,m)用以記錄在t時刻螞蟻k已走過的城市，不允許該螞蟻在本次循環中重復經過，本次循環結束后清空禁忌表。

螞蟻完成一次循環，更新各路徑信息素，公式（2）

其中，ρ∈[0,1)表示信息素揮發系數；(1?ρ)表示信息素殘留因子；△τij表示本次循環中路徑ij上的信息量增量，初始時△τij(0)=0；△τijk表示螞蟻k在本次循環中在城市i和j之間留下的信息量，公式（3）

其中，Lk表示螞蟻k環游一周的路徑長度；Q為常數。蟻群算法中，參數的選取方法與選取原則直接影響到蟻群算法的計算效率和收斂性[5]；另外，該算法存在著初始信息素缺乏、收斂速度慢、容易陷入局部最優等缺點。

本文采用雙種群策略，種群一采用蟻群算法與差分演化結合，可以很好地解決參數優化問題。種群二采用蟻群混合粒子群算法，增強了大范圍全局搜索能力，很好地解決了收斂速度慢、容易陷入局部最優問題。

3 蟻群算法與差分演化結合（DEAS）

差分演化算法擅長連續問題的優化，并且已成功應用于很多算法的參數控制中。由于蟻群算法的控制參數是連續變化的，因此可以利用DE 對其進行參數優化，進而改善蟻群算法的性能。

DEAS 將蟻群算法的參數（包括種群大小m、啟發式因子α和β，信息素揮發系數ρ）作為DE 解空間向量的元素，每個個體是一個四維向量。以DE 解空間中個體為參數組合的蟻群，搜尋最優路徑Iter代中得到的最優解作為 DE 的適應評價函數。以解決TSP 問題為例對DEAS 作具體應用說明，參數設置按文獻[6]所示。F=0.5，CR=0.9；NP∈[3D,8D]，本文中取 5D，算法的終止條件為滿足優化要求或達到最大迭代數。步驟如下：

步驟1：差分演化算法初始化：

設置目前進化代數t=1，差分演化算法的F、CR、NP以及迭代次數MAX_G，隨機選擇NP個個體，每個個體包含4 個參數，是一個NP×4 的隨機數組。其中每一維各代表m、α、β、ρ，分別在[0,2N]、[0,5]、[0,10]、[0,1]隨機取值。

步驟2：若t≥MAX_G，跳轉到Step5；否則：

蟻群算法初始化：在每個參數向量下的蟻群運行的代數Iter；對每條路徑設定初始信息量，τij=τo，將M只包含各自參數的螞蟻隨機地放置在N個節點上(N為城市數)，將第k只螞蟻的出發城市加入tabuk；根據各自的參數向量值，求Iter迭代后的最優解，即求參數向量對應的適應值。

完成對每只螞蟻的一次路徑搜索，并找出本次搜索得到的最優解：

1、根據公式（1）的計算方法，求所有城市作為下一個城市的概率，使用輪盤賭的方法隨機確定下一個要走向的城市，循環進行公式（1）直到只剩下一個城市未走時，直接到達那個城市，此時，表示一只螞蟻已經完成了一次路徑求解；

2、計算得到這只螞蟻此次路徑的長度；

根據公式（2）對全局信息素進行更新，并找到本次求解所找到的最優解，記錄最優解對應的參數向量；將本次迭代產生最優解，即得到參數向量對應的適應值，與歷史記錄最優解進行比較，選取較小的一個解來更新歷史最優解；

步驟3：將尋徑后的每個蟻群的最短路徑作為相應參數向量的適應函數值。根據公式（4）～公式（6）進行差分運算的變異、交叉和選擇運算（在選擇操作中的求解適應值函數即以新的解向量為參數，進行步驟2 中的內兩層循環），生成新一代種群。t值加1，跳轉至步驟2；在執行公式（6）進行選擇的時候，如果發現出現比歷史最優解好的解，也要進行歷史最優值的更新。

其中：j∈[1,D],randb(j) ≥[0,1]是同一隨機數發生器的第 j個值；CR∈[0,1]是變異概率；randr(j)∈[1,2,…,D]是隨機選擇指數，它確保能從中得到至少一個參數。

（c）選擇操作，采用貪婪策略，得公式（6）

其中Φ(x)代表適應函數。

步驟 4：最后輸出全局最優 TSP 路徑值以及全局最優參數向量[m,α,β,ρ]。

4 蟻群算法與粒子群算法結合（PSOAS）

蟻群算法利用了信息素進行傳遞信息，而粒子群優化算法利用了本身信息、個體極值信息和全局極值3個信息，來指導粒子下一步迭代位置。蟻群算法利用正反饋原理和某種啟發式算法的有機結合，容易出現早熟現象以及陷入局部最優解?；旌系乃悸肥亲屛浵佉簿哂小傲Ｗ印钡奶匦?，首先螞蟻按照蟻群算法，完成一次遍歷后，再讓螞蟻根據局部最優解和全局最優解進行調整。

解TPS問題的混合算法如下：

步驟 1：nc←0，（nc為迭代步數或搜索次數），初始化，產生大量的路徑（如100條），從中選擇比較優的（如30條），使這些路徑留下信息素，將m個螞蟻置于n個頂點上；

步驟2：根據當前位置計算適應值（各路徑的長度）ltsp0，設置當前適應值為個體極值Ptbest，當前位置為個體極值位置pbcest，根據各個粒子的個體極值Ptbest找出全局極值bgtest和全局極值位置gcbest；

步驟3：將各螞蟻的初始出發點置于當前解集中，對每個螞蟻k(k=1，2，…，m)，按概率移至下一頂點j，將頂點j置于當前解集；

步驟4：對每個螞蟻進行如下操作，第j個螞蟻路徑Co(j)與gcbest交叉得到與pbcest交叉得到，對產生變異得到，根據當前位置計算路徑長度ltsp1，若新的目標函數變好，接受新值，否則就拒絕，第j個粒子路徑仍然為Co(j)。重新找出各個螞蟻子的個體極值ptbest和極值位置pbcest，找出全局極值gtbest和全局極值位置gcbest；

步驟5：計算各螞蟻的路徑長度Lk(k=1,2,…,m)，記錄當前的最好解；

步驟6：對路徑長度Lk小于給定值的路徑，按公式（2）中的更新方程修改軌跡強度：

步驟7：nc←nc＋1；

步驟8：若nc< 預定的迭代次數且無退化行為（即找到的都是相同解）則轉步驟2；

步驟9：輸出目前最好解。

5 雙種群混合算法

對比分析 PSO 和 DE 兩種算法的特點可以發現，DE算法具備的記憶能力使其可以跟蹤當前的搜索情況，以調整其搜索策略，具有較強的全局收斂能力和魯棒性；PSO 算法簡單，具有運算速度快、搜索能力強等特點。本文提出基于蟻群算法的差分進化混合粒子群算法的本質，是基于一種雙種群策略，其中一個種群中的個體按照 PSOAS 操作進化，另一個種群中的個體按照 DEAS操作進化，在進化過程中，通過引入一種信息交流機制，使信息能夠在兩個種群中傳遞，有助于個體避免錯誤的信息判斷而陷入局部最優點。采用非線性動態自適應慣性權重策略，以提高算法的性能，其更新狀態如公式（7）

其中，k為控制因子，控制w與t變化曲線的平滑度。

6 算法仿真

利用實例對雙種群混合算法性能進行測試，并將結果與單一的DEAS算法、單一的PSOAS算法的結果進行對比。實驗獨立進行30次，統計結果，如表1所示：

表1 獨立試驗30次的統計結果

結果表明，雖然蟻群算法與粒子群算法結合能夠提高收斂速度，但是PSOAS算法得到的最差解較多，表明算法極易收斂到局部最小解。而蟻群算法與差分進化相結合能夠改善算法全局優化能力，能得到較解且相對穩定。雙蟻群混合算法則吸收了兩種算法的優點，該算法達到最好解的次數最多，增加了最優解的概率；另外，由于兩個種群中的通信機制，PSOAS種群提高了DEAS種群的搜索效率。

圖1和圖2分別為PSOAS種群與DEAS種群得到的最優路徑，其中種群2的解優于種群1，因此最終解為種群2的運算結果。由圖3，圖4可以看出，原本收斂較慢的DEAS算法由于通信機制，收斂速度與PSOAS算法比較接近。

圖1 種群1(PSOAS混合算法)計算結果

圖2 種群2(DEAS混合算法)計算結果

圖3 種群1中最佳路徑隨迭代的變化

圖4 種群2中最佳路徑隨迭代的變化

7 結束語

本文針對物流過程中配送路徑最優問題，設計了基于蟻群算法的雙種群混合算法，種群一采用蟻群算法與差分演化結合，種群二采用蟻群混合粒子群算法，在進化過程中通過引入一種信息交流機制使信息能夠在兩個種群中傳遞，提高了螞蟻在選路時的協同合作能力。仿真實驗表明，該算法能較好地發現全局最優解，并且有較快的收斂速度和較高的穩定性，在綜合性能上遠遠高于 DEAS算法，并在計算效率上優于PSOAS算法。

[1]Colorni A, Dorigo M, Theraulaz G. Swarm intelligence:From natural to artificial systems[M]. New York: Oxford University Press, 1999.

[2]KENNEDY J, EBERHART R C. Particle Swarm optimization[C]//IEEE International Conference on Neural Network. Perth, Australia:[s.n.], 1995.

[3]SHI Y, EBERHART R C. A modified swarm optimizer[C]//IEEE International Conference of Evolutionary Computation. Anchorage, Alaska:[s.n.], 1998.

[4]CHIOU J P, WANG F S, A Hybrid method of differential evolution with application to optimal control problems of a bioprocess system[J]．Proc l 998 IEEE on Evolutionary Computation Conf, 1998, l：627—632．

[5]崔嬌，黃少榮．基于差分演化的自適應參數控制蟻群算法[J]．計算機工程，2011,37(6):190-193．

[6]KENNEDY J，EBERHART R． Particle swarm optimization［C］/ /Proc of IEEE International Conference on Neural Networks． 1995:1942-1948．