基于粒子群算法的物資配送優(yōu)化研究

方文超

(廣東工貿(mào)職業(yè)技術(shù)學院經(jīng)濟貿(mào)易系，廣東廣州510510)

0 引言

物資配送是企業(yè)運營的基礎(chǔ)之一，其關(guān)系到生產(chǎn)和銷售的正常開展。優(yōu)化物資配送不僅能夠有效降低費用，而且能保障企業(yè)物資流轉(zhuǎn)的協(xié)調(diào)發(fā)展。物資配送如何進行優(yōu)化已成為企業(yè)運作的關(guān)鍵。但是，物資配送往往受到許多因素約束，這大大增加其復雜性。因此，優(yōu)化物資配送成為學術(shù)界和企業(yè)界的研究熱點。

粒子群算法是近年來新興的人工智能技術(shù)，其通過模仿鳥群覓食而求得最優(yōu)解，屬于群智能算法。它能夠通過個體與群體之間相互作用，突出群體智能的優(yōu)勢，并具有強大并行計算能力，有著高度魯棒性。

關(guān)于物資配送優(yōu)化研究，現(xiàn)有文獻主要采用最小元素法、遺傳算法、粗糙集等方法。［1］108-111，［2］13-16，［3］119-122目前采用粒子群算法求解物資配送優(yōu)化問題的研究基本處于空白。因此，本文探索采用粒子群算法進行物資配送優(yōu)化問題的求解，嘗試填補該領(lǐng)域空白。由此為物資配送優(yōu)化提供一種新的研究方法，并為企業(yè)決策提供參考。

1 粒子群算法

粒子群算法(Particle Swarm Optimization)是一種群智能算法，屬于啟發(fā)式全局優(yōu)化算法。該算法通過模擬鳥群覓食行為尋找最優(yōu)解。其所模擬的鳥群覓食過程是:假設(shè)鳥群正在隨機尋找食物(即最優(yōu)解)，當其中一只鳥成功找到食物，那么其周圍的鳥就會向這個成功者學習，向著食物所在位置飛去，即成功者會引導其周圍鳥類飛向食物所在地。并且鳥類覓食還有一個顯著特點，這就是每只鳥既向成功者學習和模仿，使其能向食物所在地飛去，但也會設(shè)計自己的專屬路線或個性化路線，以至于不會與其他鳥類發(fā)生碰撞。因此，粒子群算法的特點是既要使每個個體尋找最優(yōu)解時與其他個體不發(fā)生碰撞，即保持其個性，又要使其向成功者學習模仿，走向目的所在地，即保持其社會性或共性。也就是說粒子群算法實現(xiàn)了個性和共性或社會性的協(xié)調(diào)和平衡，是一種新興的人工智能技術(shù)。

粒子群算法的數(shù)學模型是［4］63-85，［5］269-273:

設(shè) Si=(si1，si2，…，sin)為粒子i的當前位置，Vi=(vi1，vi2，…，vkn)為粒子i的當前飛行速度，Hi=(hi1，hi2，…，hin)為粒子i所經(jīng)過的最佳位置，即最好的適應(yīng)值。

一般地，設(shè)f(X)為實現(xiàn)最小化的目標函數(shù)，那么粒子i的當前位置由下式確定:

其中，k為粒子i的第k次循環(huán)。

粒子群算法的基本方程如下:

由式(2)可得，等式右邊的第一項表示粒子以前的飛行速度，第二項表示粒子向自身最佳位置飛去，第三項表示粒子向全局最佳位置飛去。

在實際使用中，使用粒子群算法需進行改進和調(diào)整。這是因為由式(2)可知，如果w取值較大，可以提高全局搜索能力，但是也使得運算量變得過大;如果w取值較低，則可能會出現(xiàn)局部極小化的缺陷。而傳統(tǒng)的基本算法中w設(shè)為1，會影響收斂能力。因此，本文使用權(quán)重線性調(diào)整法調(diào)整w，能夠有效提高算法的全局搜索能力。慣性權(quán)重w 的調(diào)整公式是［5］269-273:

其中，wmax為最大慣性權(quán)重，wmin為最小慣性權(quán)重，q為當前粒子循環(huán)次數(shù)，qmax為預(yù)先設(shè)定最大循環(huán)次數(shù)。使用中，wmax通常在0．8 ～1．2之間取值，wmin通常在0．4～0．5之間取值。［6］69-73，［7］84-89

2 物資配送問題的描述

假設(shè)一個廠商生產(chǎn)一種產(chǎn)品，該產(chǎn)品在n個工廠生產(chǎn)，并對m個區(qū)域進行產(chǎn)品供應(yīng)。設(shè)F1，F(xiàn)2，F(xiàn)3，…，F(xiàn)n為所擁有的共 n 個生產(chǎn)工廠，設(shè) R1，R2，R3，…，Rm為其供應(yīng)共m個區(qū)域。設(shè)每個生產(chǎn)工廠的產(chǎn)量不大于Gi(i∈{1，2，…，n})，每個區(qū)域供應(yīng)量不少于 Lj(j∈ {1，2，…，m})。并且，第 i個生產(chǎn)工廠把產(chǎn)品運到第j個區(qū)域的單位配送費用為Cij。設(shè)Xij為從第i個生產(chǎn)工廠運到第j個區(qū)域的產(chǎn)品數(shù)量，該物資配送問題的求解目標是實現(xiàn)總配送費用最小化。一般地，以上各個參數(shù)均不小于零，問題所求解的未知數(shù)為Xij。

上述物資配送問題的數(shù)學模型是:

以上數(shù)學模型的本質(zhì)是一個優(yōu)化問題，即求解Xij，實現(xiàn)y最小化。

3 粒子群算法對于物資配送問題的求解

使用粒子群算法對于上述物資配送問題求解的基本思路是:設(shè)所要求解的未知數(shù)Xij為粒子i在第j維的當前位置，并經(jīng)過若干次循環(huán)后，滿足設(shè)定精度，實現(xiàn)目標函數(shù)最小值的求解。

參考相關(guān)文獻［5］269-273，根據(jù)物資配送問題的設(shè)計，本研究提出的粒子群算法對于物資配送問題求解的基本過程如下:

步驟1:初始化粒子群的基本參數(shù)。

步驟2:使用目標函數(shù)計算每個粒子適應(yīng)度。

步驟3:把每個粒子的目前適應(yīng)度與其之前最優(yōu)適應(yīng)度比較，如果目前適應(yīng)度更優(yōu)，則以目前適應(yīng)度取代之前最優(yōu)適應(yīng)度;否則，不更新粒子自身最優(yōu)適應(yīng)度。

步驟4:設(shè)定群體最優(yōu)值保持不變的次數(shù)為e，把每個粒子自身最優(yōu)適應(yīng)度與整個群體最優(yōu)適應(yīng)度比較，如果粒子自身最優(yōu)適應(yīng)度更優(yōu)，則以該粒子自身最優(yōu)適應(yīng)度取代群體最優(yōu)適應(yīng)度，并設(shè)e=0;否則，不更新群體最優(yōu)適應(yīng)度，e增加1，若e大于設(shè)定次數(shù)，則需要對部分粒子初始化。

步驟5:更新每個粒子的位置和速度。

步驟6:如果達到設(shè)定精度，則算法結(jié)束，得到最優(yōu)解;如果循環(huán)次數(shù)達到規(guī)定循環(huán)次數(shù)，但精度不滿足要求，則返回步驟1，重新初始化算法;如果循環(huán)次數(shù)未達到規(guī)定次數(shù)，且精度不滿足設(shè)定精度，則返回步驟2，繼續(xù)尋找最優(yōu)解。

本研究的粒子群算法對于物資配送問題求解的基本過程如圖1所示。

圖1 粒子群算法對于物資配送問題求解的基本過程

4 算例分析

在上文物資配送模型中，假設(shè)該產(chǎn)品在3個工廠生產(chǎn)，并對4個區(qū)域進行產(chǎn)品供應(yīng)。設(shè)F1，F(xiàn)2，F(xiàn)3為所擁有的共 3 個生產(chǎn)工廠，設(shè) R1，R2，R3，R4為其供應(yīng)共4個區(qū)域;設(shè)F1，F(xiàn)2，F(xiàn)3的產(chǎn)量分別不大于5 000 個、9 000 個、11 000 個，設(shè)R1，R2，R3，R4供應(yīng)量分別不少于7 000個、6 000個、4 000個、8 000個。并且第i個生產(chǎn)工廠把產(chǎn)品運到第j個區(qū)域的單位配送費用為Cij(單位:元 /個)，Cij的設(shè)置如表1所示。設(shè)Xij為從第i個生產(chǎn)工廠運到第j個區(qū)域的產(chǎn)品數(shù)量(單位:個)，該物資配送問題的求解目標是實現(xiàn)總配送費用最小化。

表1 單位配送費用 單位:元 /個

現(xiàn)使用粒子群算法進行求解。粒子群算法參數(shù)設(shè)置如下:wmax=0．95，wmin=0．4，c1=2，c2=2，粒子數(shù)為100，預(yù)定精度為0．001，最大循環(huán)次數(shù)為120。采用MATLAB編寫程序運行程序，得到最優(yōu)解即實現(xiàn)總配送費用最小值的方案是:只要從F1配送5 000個產(chǎn)品到R4，從F2配送7 000個產(chǎn)品到R1，從F2配送2 000個產(chǎn)品到R3，從F3配送6 000個產(chǎn)品到R2，從F3配送2 000個產(chǎn)品到R3，從F3配送3 000個產(chǎn)品到R4，就能實現(xiàn)最小總配送費用，即85 000元。并且，本算例在預(yù)定循環(huán)次數(shù)內(nèi)達到預(yù)定精度。

這表明粒子群算法是求解物資配送優(yōu)化問題的一種可行方法，能很好解決物資配送優(yōu)化問題。

5 結(jié)語

粒子群算法是一種仿生型計算技術(shù)，是新興的人工智能技術(shù)，有著高度魯棒性等優(yōu)點。本文探索把該算法應(yīng)用于物資配送優(yōu)化問題求解，構(gòu)建了一個物資配送模型，闡述了粒子群算法對于物資配送優(yōu)化的基本思路和流程，并通過一個實例計算驗證。運算結(jié)果表明，粒子群算法對于物資配送優(yōu)化問題求解取得良好效果。把粒子群算法拓展到其他領(lǐng)域，粒子群算法與其他算法結(jié)合使用將是未來的研究方向。

［1］耿雪，段會川．改進的最小元素法及其在物資配送問題中的應(yīng)用［J］．物流工程與管理，2010(6)．

［2］陳城輝，徐永能，楊愛梅，等．遺傳算法在多車型軍備物資配送路徑優(yōu)化中的應(yīng)用［J］．四川兵工學報，2010(2)．

［3］宋曉宇，劉鋒，常春光．基于廣義粗糙集的應(yīng)急物資調(diào)度模型［J］．控制工程，2010(1)．

［4］ 段海濱，張祥銀，徐春芳．仿生智能計算［M］．北京:科學出版社，2011．

［5］ 曹承志．人工智能技術(shù)［M］．北京:清華大學出版社，2010．

［6］SHI Y H，Eberhart R．A modified particle swarm optimizer［C］．Proceedings of IEEE International Conference On Evolutionary Computation，1998．

［7］Angeline P．Using selection to improve particle swarm optimization［C］．Proceedings of IEEE International Conference On Evolutionary Computation，1998．