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

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

0 引言

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

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

圖1 CVRP 問題示意圖

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

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

CVRP 的數(shù)學(xué)模型可表示為：

其中式（3）為目標(biāo)函數(shù)，式（4）為車輛的容量約束條件，式（5）～式（7）表示每個(gè)客戶點(diǎn)有且只有一輛車進(jìn)行配送，由N 輛車共同完成配送。

CVRP 問題是NP 難（NP-Hard）問題[7]，CVRP 問題的解空間會(huì)隨問題規(guī)模的增加呈指數(shù)增長(zhǎng)，其無(wú)法在有限的時(shí)間里驗(yàn)證所得到的解是否為全局最優(yōu)解[8]。

目前，智能優(yōu)化算法是最常用的用于求解VRP 問題的方法[9]。依據(jù)統(tǒng)計(jì)，在2009-2015 年間，有71.25%的論文使用了智能優(yōu)化算法對(duì)VRP 問題進(jìn)行求解[10]。智能優(yōu)化算法的允許解發(fā)生退化，并且求解過程存在隨機(jī)因素，這使得智能優(yōu)化算法能夠跳出局部最優(yōu)解，去更好的尋找待求問題的全局最優(yōu)解。同時(shí)因?yàn)樯鲜鎏匦?，智能?yōu)化算法通常求得為可接受解而非最優(yōu)解，結(jié)果的優(yōu)劣與算法有關(guān)。

本文對(duì)比研究了粒子群算法、模擬退火算法以及蟻群算法的三種算法思想和它們應(yīng)用于車輛路徑問題上的計(jì)算流程，并且選取了Solomon 標(biāo)準(zhǔn)測(cè)試算例進(jìn)行測(cè)試，分析它們求解結(jié)果，并對(duì)算法進(jìn)行了評(píng)價(jià)。

1 粒子群算法

粒子群算法（Particle swarm optimization，PSO）最早是于1995 年由Kennedy 和Eberhart 提出的一種群智能算法[11]，其最初是為了模擬人們觀察到的鳥群集群飛行尋食時(shí)出現(xiàn)的群體協(xié)作模式。人們發(fā)現(xiàn)如果某個(gè)群體能夠?qū)⒚總€(gè)個(gè)體探查到的信息進(jìn)行共享，那么這個(gè)群體更可能獲得優(yōu)勢(shì)，跟據(jù)個(gè)體對(duì)環(huán)境的適應(yīng)度的不同，群體中的每個(gè)單獨(dú)的個(gè)體會(huì)向群體中已知的更適宜達(dá)成目標(biāo)的區(qū)域移動(dòng)[12]。

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

式中，ω 為慣性權(quán)重系數(shù)，決定了每次迭代后原來(lái)速度的保留，表示著粒子保持上一代飛行趨勢(shì)的能力。c1，c2為算法的學(xué)習(xí)因子，c1 影響著粒子的“自我經(jīng)驗(yàn)學(xué)習(xí)”能力，c2 影響著粒子的“社會(huì)經(jīng)驗(yàn)學(xué)習(xí)”的能力。rand1 和rand2 被稱為加速度權(quán)重系數(shù)，是介于[0，1]之間的隨機(jī)數(shù)。

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

圖2 粒子群算法流程圖

2 模擬退火算法

模擬退火算法（Simulated Annealing，SA）是一種模擬金屬退火過程的算法，Metropolis 等人最早使用數(shù)學(xué)語(yǔ)言來(lái)描述此方法[13]。在金屬退火過程中，需要先進(jìn)行升溫，增大金屬的內(nèi)能，再以極慢的速度冷卻，粒子的排布逐漸有序。若冷卻的速度足夠慢，金屬最終可以達(dá)到內(nèi)能最小的一種狀態(tài)。模擬退火算法是一種隨機(jī)優(yōu)化算法，最大的特點(diǎn)是其可以依概率接受一個(gè)比當(dāng)前結(jié)果更差的解，接受概率與溫度有關(guān)。

模擬退火算法的主要參數(shù)包括初始溫度T0、終止溫度Te，退火因子α。退火因子影響著算法的收斂速度，退火因子過小，降溫過快，會(huì)導(dǎo)致算法更容易收斂到局部最優(yōu)。設(shè)當(dāng)前溫度為T，溫度按照公式（10）進(jìn)行更新。

Metropolis 準(zhǔn)則是模擬退火算法中的一個(gè)重要概念，模擬退火算法采用此準(zhǔn)則來(lái)判斷是否接受新解。Metropolis 準(zhǔn)則用數(shù)學(xué)語(yǔ)言表達(dá)如公式（11）所示。

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

圖3 模擬退火算法流程圖

3 蟻群算法

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

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

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

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

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

圖4 蟻群算法流程圖

4 實(shí)驗(yàn)及分析

為了對(duì)比三種智能算法求解CVRP 問題的性能，經(jīng)過調(diào)研，本文選擇了在相同運(yùn)行時(shí)間內(nèi)，各算法求得的所有解的最優(yōu)值和平均值作為評(píng)價(jià)指標(biāo)，數(shù)據(jù)集選用了Solomon 數(shù)據(jù)集的5 個(gè)算例，分別選取前25、前50 和全部100 個(gè)客戶點(diǎn)進(jìn)行實(shí)驗(yàn)。實(shí)驗(yàn)只采用其客戶點(diǎn)坐標(biāo)和客戶需求，不考慮其所給的時(shí)間窗約束。實(shí)驗(yàn)中兩點(diǎn)的距離計(jì)算均采用歐氏距離（Euclidean Distance）。

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

圖5 算法收斂曲線

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

表1 25 客戶點(diǎn)的距離實(shí)驗(yàn)結(jié)果

表2 50 客戶點(diǎn)的距離實(shí)驗(yàn)結(jié)果

表3 100 客戶點(diǎn)的距離實(shí)驗(yàn)結(jié)果

4.2 數(shù)據(jù)分析

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

圖6 不同數(shù)據(jù)集三種算法實(shí)驗(yàn)結(jié)果最優(yōu)值

圖7 不同數(shù)據(jù)集三種算法實(shí)驗(yàn)結(jié)果平均值

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

在大規(guī)模CVRP 問題中，蟻群算法在各數(shù)據(jù)集上的最優(yōu)值和平均值均顯著小于另外兩種算法的求解結(jié)果；在數(shù)據(jù)集C101 和C102 中，模擬退火算法的結(jié)果平均值與粒子群算法結(jié)果相差不大，最優(yōu)值小于粒子群，在R101，R102 和RC101 中，模擬退火算法的各項(xiàng)指標(biāo)均優(yōu)于粒子群算法。

綜合考慮各數(shù)據(jù)集求得結(jié)果，可以認(rèn)為蟻群算法對(duì)于CVRP 問題的求解性能在三種算法中最好。

5 結(jié)論

本文選用了不同規(guī)模和不同分布的Solomon 數(shù)據(jù)集，通過對(duì)比結(jié)果的最優(yōu)值和平均值可以發(fā)現(xiàn)，蟻群、模擬退火和粒子群算法在求解CVRP 問題時(shí)的性能不同，并且問題的規(guī)模對(duì)算法的求解性能產(chǎn)生影響。得到的結(jié)論如下：

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

②模擬退火算法的算法結(jié)構(gòu)簡(jiǎn)單，在中小規(guī)模時(shí)該算法求得最優(yōu)解能力更好；

③蟻群算法的算法復(fù)雜度高，其在大中小規(guī)模CVRP問題的求解能力均較強(qiáng)且求解精度高，該算法性能的綜合性能評(píng)價(jià)最高。