粒子群算法求解物流路徑優化問題

何 泉

(監利縣尺八鎮初級中學，湖北 監利 433328)

1 物流配送路徑優化問題描述

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

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

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

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

2 粒子群算法

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

3 算法流程

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

步驟2：根據初始化粒子的全局最優值和個體最優值；

步驟3：并將粒子的pBest設置為個體當前最優位置，gBest設置為初始群體中整個粒子群體最佳位置；

步驟4：若算法滿足收斂條件或達到最大迭代次數,則執行步驟7,否則，執行步驟6；

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

步驟6：將迭代次數加1，并執行步驟3；步驟7：輸出gBest，算法結束。

4 實驗結果分析

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

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

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

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

圖1 CHCS算法路線仿真圖

表2 算法運行50次結果

5 結論

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

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