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

何 泉

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

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

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

1)每個(gè)客戶點(diǎn)的需求只能由一輛車來完成；

2)每個(gè)客戶點(diǎn)需求量總和必須小于等于汽車載重量；

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

2 粒子群算法

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

3 算法流程

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

表1 各客戶點(diǎn)到中心倉庫的距

圖1 CHCS算法路線仿真圖

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

5 結(jié)論

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

[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.