粒子群算法求解物流路徑優(yōu)化問題

何 泉

(監(jiān)利縣尺八鎮(zhèn)初級中學(xué)，湖北 監(jiān)利 433328)

1 物流配送路徑優(yōu)化問題描述

物流問題是當(dāng)今最流行的運輸優(yōu)化問題，描述為：有n個客戶點，最多使用m輛汽車，要求安排車輛行駛路線使車輛行駛總距離最少.并滿足條件：

1)每個客戶點的需求只能由一輛車來完成；

2)每個客戶點需求量總和必須小于等于汽車載重量；

3)所有路徑的長度總和必須小于等于單次配送行駛的最大距離。

2 粒子群算法

粒子群優(yōu)化算法主要模擬鳥集群飛行覓食行為，每個粒子利用自身歷史最優(yōu)位置和整個粒子群的全局最優(yōu)解提供的信息，在解空間內(nèi)不斷飛行，實現(xiàn)尋找最優(yōu)解的目的。在基本PSO算法中，第i個粒子的飛翔速度是一個D維的向量，第i個粒子迄今為止發(fā)現(xiàn)的最好位置(個體極值),整個粒子群迄今為止發(fā)現(xiàn)的最好位置(全局極值),整個粒子群是通過個體極和全局極值來更新自己的飛行速度和飛行位置，在解空間中尋求最優(yōu)解。c1和c2是學(xué)習(xí)因子,r1和r2是隨機數(shù)。PSO算法每粒子采用如下公式來更改自己的速度和位置：

3 算法流程

步驟1：初始化種群規(guī)模、粒子的位置向量、速度向量，計算粒子的適應(yīng)度；

步驟2：根據(jù)初始化粒子的全局最優(yōu)值和個體最優(yōu)值；

步驟3：并將粒子的pBest設(shè)置為個體當(dāng)前最優(yōu)位置，gBest設(shè)置為初始群體中整個粒子群體最佳位置；

步驟4：若算法滿足收斂條件或達(dá)到最大迭代次數(shù),則執(zhí)行步驟7,否則，執(zhí)行步驟6；

步驟 5：根據(jù)公式(1)和公式(2)求出粒子移動后的新個體最優(yōu)和全局位置最優(yōu)值；

步驟6：將迭代次數(shù)加1，并執(zhí)行步驟3；步驟7：輸出gBest，算法結(jié)束。

4 實驗結(jié)果分析

某物流公司有一個配送中心，各配送點位置坐標(biāo)和需求量如表1所示。

所有試驗均在操作系統(tǒng)為windows 7，雙核3.16GHz的Intel處理器和4GB內(nèi)存，Matlab2010的平臺上完成。連續(xù)計算50次，路線仿真圖如圖1所示，遺傳算法和粒子群算法運行50次實驗結(jié)果如表2所示。

從表2可以看出：PSO算法無論是從最優(yōu)解、平均值、50次找到最優(yōu)解次數(shù)還是平均計算時間均優(yōu)于GA算法。實驗數(shù)據(jù)說明PSO算法收斂速度快，對物流配送路徑優(yōu)化問題具有一定的可行性和有效性。

表1 各客戶點到中心倉庫的距

圖1 CHCS算法路線仿真圖

表2 算法運行50次結(jié)果

5 結(jié)論

針對物流問題的特殊性，提出了一種粒子群算法的物流車輛路徑優(yōu)化解決方案。仿真結(jié)果表明此算法，有效防止算法陷入局部最優(yōu)解，加快了路徑優(yōu)化問題求解效率，并求得了最優(yōu)解?？梢杂糜诮鉀Q尋求最優(yōu)路徑這一類實際問題。

[1]Kennedy J,Eberhart R.Particle swarm optimization[C]//IEEE Int Conf on Neural Networks.Piscataway:IEEE Press,1995:1942-1948.

[2]Azzawi A A G,Al-Saedi M A H.Face recognition based on mixed between selected feature by multiwavelet and particle swarm optimization[C]//Developments in E-systems Engineering(DESE).Piscataway:IEEE Press,2010:199-204.

[3]Wang fan,He xing shi,Wang yan.The cuckoo search algeorithm based on Gaussian disturbance[J].Journal of Xian.