孟憲秋 邱春艷 姜建華 劉洋 吉林財(cái)經(jīng)大學(xué)管理科學(xué)與信息工程學(xué)院

引言：車輛路徑問題（Vehicle Routing Problem，VRP）來源于交通運(yùn)輸，由Dantzing和Ramser在1959年首次提出的運(yùn)輸組織優(yōu)化中的核心問題，也是運(yùn)籌學(xué)的一類經(jīng)典組合優(yōu)化問題。智能優(yōu)化算法是一種基于物理或仿生學(xué)原理的元啟發(fā)式算法，如模擬退火算法，禁忌搜索算法，遺傳算法，粒子群優(yōu)化算法等，智能優(yōu)化算法能夠在有限的時(shí)間內(nèi)求解車輛最優(yōu)路徑，成為求解車輛路徑問題的常用算法。由于粒子群在求解車輛路徑問題時(shí)性能良好，因此該方面的研究逐漸得到學(xué)術(shù)界的廣泛重視。

國內(nèi)學(xué)者在解決車輛路徑問題時(shí)主要采用兩類策略：一類是使用非智能算法進(jìn)行求解車輛路徑問題，此方法可以有效的結(jié)解決車輛路徑問題；另一類是智能算法進(jìn)行求解車輛路徑問題，包括單目標(biāo)算法，改進(jìn)的單目標(biāo)算法以及混合的智能算法。本文采用粒子群優(yōu)化(Particle Swarm Optimizer,PSO)算法，將慣性因子設(shè)為0，可以增加收斂性且增強(qiáng)局部搜索能力，因此較為客觀。

1 基本問題描述及模型建立

1.1 問題描述

車輛路徑優(yōu)化也就是旅行商問題，即對(duì)每輛車所走的路徑進(jìn)行優(yōu)化，以達(dá)到整體路徑最短。

問題描述：一個(gè)中心倉庫序號(hào)為0，7個(gè)倉庫序號(hào)為1-7，其位置坐標(biāo)見表1，中心倉庫有3輛車，容量均為1，由這3輛車向7個(gè)需求點(diǎn)進(jìn)行貨物配送，出發(fā)點(diǎn)和收車點(diǎn)都是中心倉庫，求解物流配送車輛的最優(yōu)路徑。

1.2 模型構(gòu)建

本論文引用[5]中的模型，問題簡述為：有L個(gè)倉庫（以1,2.....L表示），擁有K輛車（k表示第k輛車），容量分別為。

模型建立如下：

其中：

2 求解物流車輛路徑的粒子群智能算法

2.1 粒子群算法數(shù)學(xué)描述及局限

粒子群算法是通過模擬鳥群捕食行為提出的一種智能算法。PSO算法的工作原理：首先，初始化一組隨機(jī)解，通過迭代跟蹤兩個(gè)極值完成自我更新，包括局部極值點(diǎn)（用pid表示其位置）和全局極值點(diǎn)（用pgd表示其位置）；然后在每輪迭代中，粒子通過：

PSO算法的優(yōu)點(diǎn)是收斂速度較快，算法簡單，容易編程實(shí)現(xiàn)。算法的缺點(diǎn)在于對(duì)于有多個(gè)局部極值點(diǎn)的函數(shù)，容易陷入到局部極值點(diǎn)；算法雖然提供了全局模索的可能，但是不能保證收斂到全局最優(yōu)點(diǎn)上。

2.2 改進(jìn)的粒子群優(yōu)化算法

本文在原有粒子群算法的優(yōu)點(diǎn)基礎(chǔ)上進(jìn)行改進(jìn)，保證粒子群算法的收斂性，即收斂到全局最優(yōu)點(diǎn)上，并且防止全局最優(yōu)解陷入全局的極值點(diǎn)。

當(dāng)慣性系數(shù)為0時(shí)，公式（5）與公式（6）合并后為：

根據(jù)公式可得只有粒子的位移發(fā)生變化，簡化了粒子進(jìn)程，仍然保持著收斂性，并且為線性收斂。本文改進(jìn)的粒子群算法主要步驟如下：

（1）初始化粒子速度和位置，并設(shè)置慣性因子為0；

（2）計(jì)算粒子的適應(yīng)度值；

（3）計(jì)算個(gè)體歷史最優(yōu)解；

（4）計(jì)算全局最優(yōu)解；

（5）根據(jù)迭代公式更新粒子的位置和速度；

（6）判斷是否帶到最大迭代次數(shù)，若沒有則轉(zhuǎn)到（2）；

（7）算法結(jié)束，輸出最優(yōu)解。

2.2.1 初始化

PSO初始化為一群隨機(jī)粒子（隨機(jī)解），然后通過迭代尋求最優(yōu)解，在每次疊代過程中，粒子通過跟蹤兩個(gè)"極值"來更新自己的速度和位置。

當(dāng)W=0，第一個(gè)解是個(gè)體極值（即第一次的解是粒子本身所找到的最優(yōu)解）；第二個(gè)極值是全局極值（即整個(gè)種群目前找到的最優(yōu)解）。

粒子群算法的初始化過程如下：

（1）設(shè)定群體規(guī)模n；

（2）對(duì)任意i,j在內(nèi)服從均勻分布產(chǎn)生；

其中：i，j分別為：“j”表示粒子的第j維，“i”表示第i個(gè)粒子；分別表示第i個(gè)粒子的最佳位置與當(dāng)前位置。

3 實(shí)驗(yàn)結(jié)果與比較

3.1 樣本集描述及參數(shù)設(shè)置

根據(jù)文獻(xiàn)[4、5]中的問題設(shè)置初始值，中心倉庫用0表示，設(shè)每輛車運(yùn)貨量q= 1.0，共3輛車完成任務(wù)。

（1）初始化粒子群為n=40，慣性因子w=0，學(xué)習(xí)因子c1=c2=1.4944，最大代數(shù)為100，搜索空間維數(shù)（未知數(shù)個(gè)數(shù)）為40，運(yùn)用上述建立的車輛路徑模型以及粒子群算法進(jìn)行求解。

（2）利用坐標(biāo)間計(jì)算公式得到需求點(diǎn)之間的距離：

3.2 實(shí)驗(yàn)過程

當(dāng)慣性系數(shù)為0時(shí)，粒子的飛行速度只取決于粒子的當(dāng)前位置，歷史最好位置和粒子群的歷史最好位置，對(duì)于全局最好的粒子將保持不動(dòng)，其他粒子則傾向與最好位置的粒子進(jìn)行移動(dòng)，即粒子群將收縮到全局最好的位置。根據(jù)代碼執(zhí)行的結(jié)果可知，當(dāng)?shù)降?2次得到最優(yōu)值，最優(yōu)的行車總距離為217.8135。

圖1 最終非劣解在目標(biāo)空間的分布

根據(jù)圖1可以得出，改進(jìn)后非劣解的數(shù)量減少，整個(gè)進(jìn)化方程具有很強(qiáng)的局部搜索能力，且改進(jìn)后的粒子群算法收斂性增加，并且不再出現(xiàn)局部極值代替最優(yōu)值情況。

4 結(jié)論

本文主要對(duì)粒子群算法進(jìn)行改進(jìn)，使粒子群算法避免了在搜索最優(yōu)值時(shí)出現(xiàn)局部極值代替全局最優(yōu)值和難以找到最優(yōu)解的情況，提高了微粒群算法的收斂性，達(dá)到最優(yōu)值時(shí)迭代次數(shù)變小，縮減了時(shí)間。