基于改進粒子群算法的物流車輛路徑優(yōu)化問題研究

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

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

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

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

1.1 問題描述

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

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

1.2 模型構(gòu)建

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

模型建立如下：

其中：

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

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

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

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

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

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

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

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

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

（2）計算粒子的適應度值；

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

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

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

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

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

2.2.1 初始化

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

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

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

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

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

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

3 實驗結(jié)果與比較

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

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

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

（2）利用坐標間計算公式得到需求點之間的距離：

3.2 實驗過程

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

圖1 最終非劣解在目標空間的分布

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

4 結(jié)論

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