求解物流配送問題的混合粒子群算法

胡文皓， 陳曙東， 辛欣

(1. 中國科學院大學 電子電氣與通信工程學院, 北京 100049；2. 中國科學院 微電子研究所, 北京 100029；3. 中國物聯網研究發展中心, 江蘇 無錫 214135)

?

求解物流配送問題的混合粒子群算法

胡文皓1,3， 陳曙東2,3， 辛欣1,3

(1. 中國科學院大學 電子電氣與通信工程學院, 北京 100049；2. 中國科學院 微電子研究所, 北京 100029；3. 中國物聯網研究發展中心, 江蘇 無錫 214135)

摘要：為了加快粒子群算法(PSO)在解決限定車輛配送問題時的收斂速度和減少時間花費，采取先驗判斷粒子個體最優位置與全局最優位置的距離決定粒子的更新方式，提出一種混合策略，設計魚群-粒子群算法(AFSA-PSO)，并通過對函數極值的求解進行驗證.實驗結果表明：該方法能夠得到正確解，并具有收斂快、尋優佳的特點.

關鍵詞：粒子群算法; 魚群算法; 混合算法; 物流配送問題

物流配送問題屬于復雜的求解最優方案的問題,在實際問題中求解最優解存在難度.因此，出現了通過種群中個體的協作能力尋找最優解的方法[1].以粒子群算法(PSO)為代表的群智能[2]是基于此思想而產生的.粒子群算法是群智能理論中應用廣泛的一類，它是個體學習迭代產生更佳解的算法.粒子群算法解決配送問題的研究主要體現在粒子編碼方式和改進解的精度上[3-6].粒子群算法為得到更精確解而增大了迭代次數，導致收斂速度慢、時間花費多等問題.為縮小迭代次數、加快解的收斂速度，本文設計了一種求解物流配送問題的混合粒子群算法.

1問題模型

車輛路徑問題是物流配送的關鍵，引入不同因素可以推導出不同的數學模型.文中采用有能力約束的車輛路徑問題[6].假定配送中心編號為0；用戶編號依次為1,2,…,n；第i個用戶的需求量為gi；可供使用的車輛數量為K；每輛車的容量為q；ci,j表示從點i到點j的單位費用.則有

又

(1)

(2)

(3)

式(1)為成本函數；式(2)為全部車的容量限制；式(3)限定了一個用戶僅能由一輛車完成.由于車容量的限制，采用判罰值修正成本函數.其中，R=(1+t)/4(t為當前迭代次數).式(1)可轉化為

(4)

采用自然數對配送路徑進行編碼，對粒子維數值進行遞增排序，得到相應用戶序列.此外，每輛車必須從中心出發再回到中心.

2混合粒子群算法

2.1粒子群算法

粒子群算法是個體尋優算法，粒子本身有感知能力.每次迭代后得到一個候選解，粒子維數代表解方案，在組合優化問題上應用廣泛，如求路徑規劃問題[7]、股票預測[8]、工程數學應用問題[9-11].

粒子x的函數值f(x)稱為個體適應度值pbest，一次迭代后，得到新位置xnew.若f(xnew)比f(x)更佳，則該粒子的個體最優位置pbest,X為xnew，pbest為f(xnew)；否則，pbest,X為x，pbest為f(x)；種群中最優位置gbest,X是全部個體適應度值最佳的粒子xbest，全局適應值gbest為f(xbest).粒子更新位置為

(5)

(6)

式(5)，(6)中:r1，r2均為(0,1)的隨機數；c1，c2為學習因子.

2.2魚群算法原理

魚群算法(AFSA)是個體尋優算法，具有易實現、適用性強等優點.如粒子群算法一樣，AFSA是連續型算法，對于離散型問題需對解編碼.AFSA算法有以下4個關鍵步驟.

1) 追尾.個體魚i在其鄰域內滿足有更好的位置best_j，且位置best_j的鄰域內的個體魚數量滿足一定條件.則魚i向best_j前進一步；否則,群聚.

2) 群聚.個體魚i在其鄰域內的個體魚數量滿足一定條件，并且該鄰域內有一個中心位置，若位置更佳，則魚i向中心位置前進一步；否則,覓食.

3) 覓食.個體魚i鄰域內隨機選擇位置new_i,若該位置更佳，則魚i向其前進一步;否則,位置不變.選擇一定次數后，都沒有更佳的位置，則隨機移動.

4) 隨機移動.在可行域內，隨機生成新位置，個體魚向其前進一步.

2.3混合策略改進粒子群算法

魚群算法根據適應值規定不同個體應有各自的優化方向，為粒子群算法改進提供了思路，即粒子應針對性地依靠不同感知能力指導粒子位置更新.

粒子的不同感知能力決定了粒子的搜索范圍和粒子種群的收斂速度.粒子在大范圍內搜索最優位置，需依仗整體感知和自我感知，使粒子位置更新后足夠分散.而為實現收斂速度快，應讓粒子向全局最優位置靠攏，這就不能擴大整體感知和自我感知.因此，應平衡粒子位置更新時所具備的3種感知能力.引入權重維持粒子的繼承能力，即

(7)

為加速粒子種群的收斂速度，每次迭代更新位置時，對粒子進行個體適應值與全局適應度差值檢測.如果接近，則“追尾”可以得到解，這些粒子的位置可信度高，為了維持粒子的搜索能力，采取信任3種感知能力的方式進行更新；如果臨近，則“群聚”即可，采取信任自我感知能力，粒子向著自己鄰近的粒子靠攏，即它們的個體最優位置pbest,X是鄰近的粒子的pbest,X；其余情況，為加速收斂，這些粒子的位置和當前個體最優位置是不足夠可信的，則直接忽略，采取信任整體感知能力，向全局最優位置gbest,X靠攏.由此，粒子會整體向當前全局最優位置靠攏，加速了收斂速度.新的混合算法記為AFSA-PSO.

3結果與分析

為驗證文章算法解決車輛路徑問題的可行性和有效性，在Windows7系統下，基于MatlabR2010b工具實現算法，通過求函數極值驗證搜索性能，并與其他文獻方法進行對比.

3.1尋優性能的驗證

由線性遞減策略可得到標準粒子群算法(SPSO).模擬退火算法與粒子群算法的融合[12](SA-PSO)是混合策略研究的熱門.設粒子數量N=40；c1=c2=1.496 18；wstart=0.9；wend=0.4；最大迭代次數為1 000次；初始溫度為10 000 ℃；最低溫度為0.01 ℃；溫度遞減因子K=0.9；最大接受誤差為0.5.

(a) Ackley函數　　　　　(b) Sphere函數圖1　混合策略和SPSO求解函數極值Fig.1　Mixed strategy and SPSO for function extremum

混合策略和SPSO求解函數極值，如圖1所示.圖1中：n為迭代算法的次數；fx為函數極值.由圖1可知：SA-PSO算法收斂速度慢，搜索范圍廣；而AFSA-PSO算法收斂速度快，搜索范圍??；SPSO算法收斂速度比AFSA-PSO稍微慢，搜索過程穩定.

3.2車輛路徑問題

配送路徑問題的數據來源于文獻[6].AFSA-PSO參數設置：粒子個數為60；迭代次數為150；粒子維數為9；最大速度限制100；權重始于0.9，終于0.4；學習因子c1=c2=1.496 18.隨機運行20次，結果如表1所示.表1中：HAPS為加入蛙跳算法的粒子群優化算法.

表1　算法結果比較表

由表1可知：AFSA-PSO最小值為65，其余最小值為67.5，但AFSA-PSO的平均成本值不是最小.此外，文獻[5]采用輪盤選擇策略選擇粒子，加入退火算法解決車輛路徑問題，記為PSOSA，運行50次，二者最優值相同，皆為67.5，但AFSA-PSO平均值為69.77，大于PSOSA的平均值68.11.

4結束語

粒子群算法的改進在于對粒子位置更新時3種能力的優化.新算法提升了收斂速度、減少了時間花費，在面對車輛路徑問題時，可以快速地找到解.未來可以采用階段求解的方法，先更新粒子位置，然后計算適應值與原來的差距判定更新位置方式，并且具體的方式使用漸進函數優化，以達到搜索解過程穩定、保證解精度的目標.

參考文獻：

[1]王文杰,葉世偉.人工智能原理與應用[M].北京:人民郵電出版社,2004：3-4.

[2]HACKWOOD S,BENI G.Self-organization of sensors for swarm intelligence[C]∥International Conference on Robotics and Automation.Piscataway：IEEE Press,1992:819-829.

[3]吳斌.車輛路徑問題的粒子群算法研究與應用[D].杭州:浙江工業大學,2007：28-40.

[4]肖麗，包駿杰.一種改進粒子群算法在物流配送路徑問題中的應用[J].湖南科技大學學報(自然科學版),2012,27(2):88-92.

[5]楊凌云.改進粒子群算法在車輛問題中的應用研究[D].鄭州:河南大學,2011：25-32.

[6]張思亮，葛宏偉.粒子群和蛙跳的混合算法求解車輛路勁問題[J].計算機工程與應用,2011,47(21):246-248.

[7]章權，溫惠英，孫博.適于配送車輛導航路徑規劃的遍歷模型的改進型粒子群優化算法[J].華南理工大學學報(自然科學版),2011,39(8):109-112.

[8]LU Jinna,BAI Yanping.Applications of GRNN based on particle swarm algorithm forecasting stock prices[C]∥International Conference on Information, Business and Education Technolog.Atlantis：Atlantis Press,2013:69-73.

[9]WANG Wei,GONG Shuiqing,LI Peilin,et al.Research on convex polyhedron collision detection[C]∥International Conference on Mechanical Engineering and Material Science.Atlantis：Atlantis Press,2012:479-483.

[10]周書敬，高延安，楊柳，等.改進的粒子群-模擬退火算法在桁架結構優化設計中的應用[J].工業建筑,2012，27(163):37-41.

[11]孫祥云,邵輝，趙家宏.采用粒子群優化算法在液壓挖掘機高效空中運動軌跡規劃方法[J].華僑大學學報(自然科學版)，2014,35(5):498-502.

[12]李麗，牛奔.粒子群優化算法[M].北京:冶金工業出版社,2009：72-94.

(責任編輯： 錢筠 英文審校： 吳逢鐵)

Hybrid Particle Swarm Algorithm for the Logistics Distribution Problem

HU Wenhao1,3, CHEN Shudong2,3, XIN Xin1,3

(1. School of Electronic, Electrical and Communication Engineering，University of Chinese Academy of Sciences, Beijing 100049, China;2. Institute of Microelectronics, Chinese Academy of Sciences, Beijing 100029, China;3. China Research and Development Center for Internet of Things, Wuxi 214135, China)

Abstract：In order to speed up convergence and reduce the time, when using the particle swarm algorithm (PSO) to solve the limited vehicle distribution problem, we use the distance between the individual optimal position and the global optimal position to decide particle updating mode, and propose a hybrid improved strategy, then we design a new AFSA-PSO algorithm. Experimental results show that it can get correct solution and has the characteristics of fast convergence and good searching effect.

Keywords：particle swarm algorithm; artificial fish swarm algorithm; hybrid algorithm; logistics and distribution problem

中圖分類號：TP 18

文獻標志碼：A

基金項目：農村信息服務數據智能處理技術研究與應用(2013BAD15B03)

通信作者：陳曙東(1977-)，女，教授，博士，主要從事大數據管理的研究.E-mail:chenshudong@ciotc.org.

收稿日期：2015-08-09

doi:10.11830/ISSN.1000-5013.2016.03.0295

文章編號：1000-5013(2016)03-0295-04