智能優化算法求解車輛路徑問題的對比分析

李京忱LI Jing-chen；劉春LIU Chun

（①北京工業大學材料與制造學部，北京100124；②北京郵電大學人工智能學院，北京100876）

0 引言

物流業是社會生產生活的重要保障。隨著經濟水平和現代信息技術快速發展，社會對于物資配送的需求在日益增加，用戶分布和用戶需求也都愈發復雜。時至今日，商品的配送已經成為了一個專門的行業，即物流業。物流業被譽為“第三利潤源泉”，是市場中重要的競爭領域[1]。其中，運輸成本在整個物流配送成本中的占比最高[2]，因此對物流配送環節的優化，將能夠有效減少物流配送成本。車輛路徑問題（Vehicle Routing Problem，VRP）是對車輛配送活動進行抽象所建立數學模型，VRP 問題通常會提供倉庫和客戶位置的信息、服務需求、以及一個或者幾個約束條件，所求得的路徑需要力爭滿足指定的優化目標。VRP問題作為組合優化問題具有極大的科學意義，其給定的約束越詳細，越接近于現實中的運輸問題，求解難度也會越大[3]。

1956 年，Dantzig 和Ramser 基于加油站運輸石油卡車車隊的路線安排問題，提出了一種車輛調度運輸的數學模型[4]，隨后由Clarke 和Wright 將此問題推廣至物流和運輸領域，即車輛路徑問題[5]。只對車輛的裝載有限制的VRP問題被稱為帶容積限制的車輛路徑問題（Capacitated Vehicle Routing Problem，CVRP），這也是最基本的一類VRP 問題，圖1 為CVRP 問題示意圖。

圖1 CVRP 問題示意圖

CVRP 問題可用公式描述如下[6]：

某配送點需要為K 個用戶提供配送服務，每個客戶的貨物需求為di（i=1，2，3，…，K），該配送點有N 輛型號完全相同的車，每輛車的最大負載均為Q。設客戶i 到客戶j 的路徑長度為cij，設配送點i=0，定義變量如式（1）、（2）所示：

CVRP 的數學模型可表示為：

其中式（3）為目標函數，式（4）為車輛的容量約束條件，式（5）～式（7）表示每個客戶點有且只有一輛車進行配送，由N 輛車共同完成配送。

CVRP 問題是NP 難（NP-Hard）問題[7]，CVRP 問題的解空間會隨問題規模的增加呈指數增長，其無法在有限的時間里驗證所得到的解是否為全局最優解[8]。

目前，智能優化算法是最常用的用于求解VRP 問題的方法[9]。依據統計，在2009-2015 年間，有71.25%的論文使用了智能優化算法對VRP 問題進行求解[10]。智能優化算法的允許解發生退化，并且求解過程存在隨機因素，這使得智能優化算法能夠跳出局部最優解，去更好的尋找待求問題的全局最優解。同時因為上述特性，智能優化算法通常求得為可接受解而非最優解，結果的優劣與算法有關。

本文對比研究了粒子群算法、模擬退火算法以及蟻群算法的三種算法思想和它們應用于車輛路徑問題上的計算流程，并且選取了Solomon 標準測試算例進行測試，分析它們求解結果，并對算法進行了評價。

1 粒子群算法

粒子群算法（Particle swarm optimization，PSO）最早是于1995 年由Kennedy 和Eberhart 提出的一種群智能算法[11]，其最初是為了模擬人們觀察到的鳥群集群飛行尋食時出現的群體協作模式。人們發現如果某個群體能夠將每個個體探查到的信息進行共享，那么這個群體更可能獲得優勢，跟據個體對環境的適應度的不同，群體中的每個單獨的個體會向群體中已知的更適宜達成目標的區域移動[12]。

初始化一群隨機分布在給定尋優空間中的粒子，其種群規模為popsize，每個粒子的位置更新與粒子群的個體極值和群體極值有關，粒子的維數為m，算法的迭代次數為maxiter，每個粒子在第k 代時的飛行速度和在搜索空間中的位置分別為：，粒子第k 代的個體極值和群體極 值 分 別 為 ：，所有的粒子按照如式（8）、（9）的更新方式在搜索空間中飛行以找到最優解：

式中，ω 為慣性權重系數，決定了每次迭代后原來速度的保留，表示著粒子保持上一代飛行趨勢的能力。c1，c2為算法的學習因子，c1 影響著粒子的“自我經驗學習”能力，c2 影響著粒子的“社會經驗學習”的能力。rand1 和rand2 被稱為加速度權重系數，是介于[0，1]之間的隨機數。

算法的流程圖如圖2 所示。為了避免粒子出現飛行范圍過大的情況，算法對粒子的每個維度加上最大飛行速率限制Vmax ，每次迭代后，若存在粒子的某一維度上的飛行速度大于Vmax 或是小于-Vmax 時，將粒子在該維度上的速度設置為Vmax 或-Vmax。

圖2 粒子群算法流程圖

2 模擬退火算法

模擬退火算法（Simulated Annealing，SA）是一種模擬金屬退火過程的算法，Metropolis 等人最早使用數學語言來描述此方法[13]。在金屬退火過程中，需要先進行升溫，增大金屬的內能，再以極慢的速度冷卻，粒子的排布逐漸有序。若冷卻的速度足夠慢，金屬最終可以達到內能最小的一種狀態。模擬退火算法是一種隨機優化算法，最大的特點是其可以依概率接受一個比當前結果更差的解，接受概率與溫度有關。

模擬退火算法的主要參數包括初始溫度T0、終止溫度Te，退火因子α。退火因子影響著算法的收斂速度，退火因子過小，降溫過快，會導致算法更容易收斂到局部最優。設當前溫度為T，溫度按照公式（10）進行更新。

Metropolis 準則是模擬退火算法中的一個重要概念，模擬退火算法采用此準則來判斷是否接受新解。Metropolis 準則用數學語言表達如公式（11）所示。

其中，fk，fk+1分別代表第k 個解，第k+1 個解的適應度。模擬退火算法的流程圖如圖3 所示。

圖3 模擬退火算法流程圖

3 蟻群算法

蟻群算法（Ant Colony Optimization，ACO）是Dorigo 受到蟻群覓食行為的啟發在1996 年提出的一種算法。蟻群具有高度的社會性和組織性。當一只螞蟻經過某條路徑時，會釋放出名為信息素的化學物質。信息素的作用是引導后來的螞蟻進行路徑選擇。螞蟻會更傾向于信息素濃度更高的路徑，然后繼續在此路徑上留下信息素。某一條路徑被選擇的次數越多，其路徑上的信息素的濃度就會越高，螞蟻便更可能選擇此路徑，這是一個正反饋過程，在經歷一段時間后，蟻群便會集中在其所找到的最短路徑上。

設一蟻群有n 只螞蟻。某一只在點i 的螞蟻進行路徑選擇時，其選擇前往點j 的概率pij按照公式（12）進行計算[14]：

式中，α 為信息素啟發因子，β 為期望值啟發因子，信息素啟發因子α 影響螞蟻尋路的隨機性的強弱，而期望值啟發因子β 影響了蟻群在搜索路徑時的確定因素作用。T 為路徑上信息素濃度。tabu 為禁忌表，當螞蟻經過了一個客戶點后，會將此點放入禁忌表中，以避免出現客戶點重復訪問。η 為啟發信息，在VRP 問題中，通常采用兩點間距離的倒數進行計算如式（13）所示：

在蟻群全部進行一次尋路之后按照信息素更新式（14）和（15）對各路徑信息素進行更新。

蟻群中螞蟻的數量為n，ρ 為信息素揮發因子，（1-ρ）代表了一次揮發后能夠留下來的信息素變量。Δτij（k）表示節點i 到節點j 的信息素在第k 次迭代內的變化量，Δτijk（t）表示第l 只蟻從節點i 出發去往節點j 在路徑上釋放的信息素量。圖4 給出了蟻群算法的流程圖。

圖4 蟻群算法流程圖

4 實驗及分析

為了對比三種智能算法求解CVRP 問題的性能，經過調研，本文選擇了在相同運行時間內，各算法求得的所有解的最優值和平均值作為評價指標，數據集選用了Solomon 數據集的5 個算例，分別選取前25、前50 和全部100 個客戶點進行實驗。實驗只采用其客戶點坐標和客戶需求，不考慮其所給的時間窗約束。實驗中兩點的距離計算均采用歐氏距離（Euclidean Distance）。

4.1 實驗數據

本文所使用計算機配置為；Intel（R）Core（TM）i7-7500U CPU @ 2.70GHz 2.90 GHz，操作系統為Windows 10，內存為8GB。程序的編譯和算例求解均使用Python（版本：PyCharm Community Edition 2020.3.3×x64）。

給出算法求解25 客戶點的R102 數據集時的收斂曲線，進行收斂性分析，運行時間為10s，如圖5 所示，可以看出在相同時間內蟻群算法的迭代次數顯著少于模擬退火和粒子群算法，這體現出了蟻群算法的每次迭代計算時的計算量更大，且蟻群算法產生的初始解相比隨機生成的路徑距離更短，且收斂代數更少。

圖5 算法收斂曲線

在給定時間限定的條件下，利用三種智能算法對各數據集進行分別求解，并得到距離最優值和平均值如表1、表2 和表3 所示。

表1 25 客戶點的距離實驗結果

表2 50 客戶點的距離實驗結果

表3 100 客戶點的距離實驗結果

4.2 數據分析

圖6、圖7 分別為距離的最優值曲線和平均值曲線。從圖中可以看出，在小規模CVRP 問題中，模擬退火算法的求解性能與蟻群算法的求解性能基本相同，在各數據集模擬退火算法的平均值和最優值均小于蟻群算法，粒子群算法求解路徑距離的最優值和平均值均顯著高于模擬退火算法和蟻群算法求得結果。

圖6 不同數據集三種算法實驗結果最優值

圖7 不同數據集三種算法實驗結果平均值

在中等規模CVRP 問題中，在C101、C102 和RC101數據集結果中，模擬退火的結果最優值為三種方法里最小，而蟻群算法結果的平均值為三種方法里最小，在數據集R101、R102 數據集結果中蟻群算法的最優值為三種方法里最小，而模擬退火算法的平均值為三種方法里最小，粒子群算法求得結果最優值和平均值均顯著高于另外兩種算法。

在大規模CVRP 問題中，蟻群算法在各數據集上的最優值和平均值均顯著小于另外兩種算法的求解結果；在數據集C101 和C102 中，模擬退火算法的結果平均值與粒子群算法結果相差不大，最優值小于粒子群，在R101，R102 和RC101 中，模擬退火算法的各項指標均優于粒子群算法。

綜合考慮各數據集求得結果，可以認為蟻群算法對于CVRP 問題的求解性能在三種算法中最好。

5 結論

本文選用了不同規模和不同分布的Solomon 數據集，通過對比結果的最優值和平均值可以發現，蟻群、模擬退火和粒子群算法在求解CVRP 問題時的性能不同，并且問題的規模對算法的求解性能產生影響。得到的結論如下：

①粒子群算法對各規模CVRP 問題求解的效果均不盡人意；

②模擬退火算法的算法結構簡單，在中小規模時該算法求得最優解能力更好；

③蟻群算法的算法復雜度高，其在大中小規模CVRP問題的求解能力均較強且求解精度高，該算法性能的綜合性能評價最高。