物流配送路線優(yōu)化粒子群改進(jìn)算法

陳 艷

(池州學(xué)院 機(jī)電工程學(xué)院，安徽 池州 247000)

物流配送路線優(yōu)化的主要目標(biāo)是確定最優(yōu)的配送路線，使得配送時間總和最少，總成本最省，它是物流運(yùn)輸中心經(jīng)營中一個至關(guān)重要的問題[1]。如今世界市場的現(xiàn)代物流產(chǎn)業(yè)競爭日趨激烈，運(yùn)輸配送時間和成本的控制，成為物流企業(yè)贏得市場和利潤的關(guān)鍵因素之一。運(yùn)輸配送路線優(yōu)化問題受眾多的因素影響，如何在這些因素之間進(jìn)行權(quán)衡越來越受到研究人員的關(guān)注。隨著物流企業(yè)日漸增長的現(xiàn)實需求，過去被應(yīng)用到物流配送路線優(yōu)化的傳統(tǒng)算法表現(xiàn)效率較低，漸漸地不能夠適應(yīng)現(xiàn)代物流配送企業(yè)需求。

物流中心配送路徑優(yōu)化需要考慮的最重要的兩個因素是配送時間和配送成本，想要同時兼顧兩個因素，需要優(yōu)化能力極強(qiáng)的優(yōu)化方法。目前，研究人員已經(jīng)有大量的優(yōu)化方法用來解決物流運(yùn)輸中心配送路徑優(yōu)化選擇問題。針對冷鏈物流網(wǎng)絡(luò)的網(wǎng)點布局和運(yùn)輸問題,張文峰等提出了一種非線性混合整數(shù)規(guī)劃模型，該模型是基于冷鏈物流的網(wǎng)點建設(shè)成本和運(yùn)營成本為優(yōu)化目標(biāo)，采用量子粒子群算法求解[2]。為了優(yōu)化車間的物料運(yùn)輸配送路徑,楊家平等建立一種數(shù)學(xué)優(yōu)化模型，該模型是基于車間物流通道節(jié)點,采用新型的單親遺傳算法用于求解[3]。針對物流配送過程中的不同交通環(huán)境和工具，以及不同的配送路徑,葉威惠等采用改進(jìn)的遺傳算法解決物流運(yùn)輸配送過程中的兩個層次的路徑優(yōu)化[4]?？紤]到快遞和物流配送的異同,麻存瑞等在物流配送路徑優(yōu)化問題的基礎(chǔ)上，建立了符合快遞配送路徑優(yōu)化問題的數(shù)學(xué)模型，并基于此設(shè)計了一種采用自然數(shù)編碼,綜合考慮快件數(shù)量、車輛載重、車輛容量等約束的解碼方式的遺傳算法[5]。針對傳統(tǒng)資源調(diào)度算法中資源利用率低等缺點，以上方法能夠一定程度的解決配送優(yōu)化的相關(guān)問題，但該算法依然有進(jìn)一步改進(jìn)的空間。

物流運(yùn)輸中心配送路徑優(yōu)化問題的求解往往令人不甚滿意。這主要有兩個方面的原因：一方面是物流中心配送路徑優(yōu)化問題的優(yōu)化模型較難，不容易尋到滿意的優(yōu)化解；另一方面則是因為現(xiàn)有的優(yōu)化算法及其改進(jìn)策略大多存在著一些缺陷，使得其優(yōu)化達(dá)不到預(yù)期效果。為了切實有效改善現(xiàn)有優(yōu)化算法的優(yōu)化性能，需要針對性地對其改進(jìn)。因此，為使粒子群方法達(dá)到全局收斂的目的，本文在慣性權(quán)重粒子群算法的基礎(chǔ)上，加入了混沌隨機(jī)數(shù)擾動，并在進(jìn)化過程中隨機(jī)給出相應(yīng)的加速度系數(shù)，從而達(dá)到改進(jìn)粒子群優(yōu)化方法的目的，使粒子群算法的優(yōu)化性能有效改善。本文基于3種測試函數(shù)和1個物流運(yùn)輸中心配送路線優(yōu)化問題的實際算例，對3種不同的粒子群算法進(jìn)行了優(yōu)化性能上的比較，其試驗結(jié)果說明了本文提出的粒子群改進(jìn)算法的優(yōu)化能力更強(qiáng)，能有效解決物流運(yùn)輸中心配送路線優(yōu)化問題。

1 物流運(yùn)輸中心配送路線優(yōu)化問題的數(shù)學(xué)模型

基于實際情況，本文考慮了多個物流中心、多種資源下的多輛配送車輛的配送場景。其主要運(yùn)輸需求如下：

(1)n1種不同資源；

(2)空間上分布著n2個物流中心；

(3)空間上分布著n3個客戶，客戶對不同資源有不同需求；

(4)盡可能的使得配送時間總和最少和配送成本總和最少，最大配送時間不超過一定數(shù)值。

配送路線優(yōu)化問題的核心是節(jié)約其配送成本和配送時間。因此，配送路線優(yōu)化問題的優(yōu)化目標(biāo)有兩個，配送時間總和和配送成本總和，記為Tsum和Csum。具體的以配送時間總和和配送成本總和作為優(yōu)化目標(biāo)的優(yōu)化模型為[6]：

(1)

(2)

式中，用l={1,2,3,…,n1}表示資源集合，包含n1個不同的資源；用i,j={1,2,3,…,n2+n3}表示節(jié)點集合，包含n2+n3個節(jié)點，不包括物流中心和客戶；Ci,j和Ti,j表示第i個節(jié)點在第j個節(jié)點的配送成本和配送時間。若車輛k完成從節(jié)點i和j的配送，xi,j,k=1；否則，xi,j,k=0。若節(jié)點i的配送由車輛k完成，yi,k=1；否則，yi,k=0。約束1為車輛的載重限制，每輛車的每一種資源的配送總量不得超過車輛該資源的最大載重量；約束2保證每個客戶只由一輛車輛負(fù)責(zé)配送一次，不能重復(fù)配送；約束3和約束4則保證所有物流中心和客戶都被配送到。目標(biāo)1和目標(biāo)2表示該配送優(yōu)化問題的優(yōu)化目標(biāo)是配送時間總和Tsum和配送成本總和Csum。由上述物流中心配送優(yōu)化問題的優(yōu)化模型可知，該問題的解不易得到。

2 改進(jìn)的粒子群算法

2.1 基本粒子群算法

(3)

上式中用i=1,2,…,N表示粒子編號，用t表示粒子維度，用d表示迭代優(yōu)化次數(shù)，用w表示權(quán)重因子，用c1和c2表示加速系數(shù)，且0

2.2 慣性權(quán)重因子線性遞減的粒子群算法

基本粒子群算法非常容易局部收斂。其中，慣性權(quán)重因子ω線性遞減的粒子群改進(jìn)算法受到研究人員的廣泛關(guān)注。慣性權(quán)重線性遞減的粒子群算法更新迭代計算公式如下述公式(4)所述。

(4)

式中：ωk—慣性權(quán)重因子的遞減斜率；

ωmax—初設(shè)的最大慣性權(quán)重因子。

慣性權(quán)重因子ω的設(shè)置既影響收斂速度，又關(guān)系尋優(yōu)精度，因此ω在粒子群方法中至關(guān)重要。若慣性權(quán)重因子取值較大則能夠改善收斂速度，有利于全局搜索，但同時也降低了解的精度；若慣性權(quán)重因子取值較小則有利于改善局部搜索，達(dá)到尋優(yōu)精度要求，但同時也會以其收斂速度為代價，并且使粒子群算法局部收斂的概率隨之增加。采用粒子群算法時，在迭代前期，收斂速度較為重要；在其迭代后期，尋優(yōu)精度的重要性愈發(fā)明顯。

在慣性權(quán)重因子線性遞減(LDW)方法優(yōu)化過程中，慣性權(quán)重因子ω與進(jìn)化代數(shù)t呈現(xiàn)線性遞減的關(guān)系[8]，其遞減斜率為ωk。其慣性權(quán)重因子ω和進(jìn)化代數(shù)t的線性遞減關(guān)系曲線(見圖1)[8]。

圖1 慣性權(quán)重因子ω和進(jìn)化代數(shù)t的關(guān)系曲線

2.3 慣性權(quán)重因子線性遞減的粒子群增加混沌隨機(jī)數(shù)擾動法

由上面論述可知，相對于常規(guī)基本粒子群方法，慣性權(quán)重因子線性遞減(LDW)粒子群算法，可以兼顧收斂速度和尋優(yōu)精度，具有更好的尋優(yōu)效果。但是這種線性遞減的慣性權(quán)重因子ω并不能反映粒子群方法的實際搜索過程，因為粒子群方法的實際搜索優(yōu)化過程的是非線性的，所以采用線性遞減的慣性權(quán)重因子ω并不能有效改善粒子群方法的優(yōu)化效果[8]。因此，粒子群算法迭代過程中，如果算法長時間的得不到更好的全局極值，可以采用迅速加入混沌隨機(jī)數(shù)擾動的方法，選取合適的擾動可以使得慣性權(quán)重因子ω迅速遞增，有效確保粒子群方法全局收斂至最優(yōu)值。

由此，慣性權(quán)重因子線性遞減的粒子群增加混沌隨機(jī)數(shù)擾動后的更新迭代計算公式如下述公式(5)所述。

(5)

式中，At為慣性權(quán)重的混沌擾動隨機(jī)數(shù)，在一定的擾動概率下，At∈(0,0.1)，其余，At=0?；煦绗F(xiàn)象是非線性系統(tǒng)中一種普遍的現(xiàn)象，它的變化過程看似混亂，實際上其內(nèi)在具有規(guī)律性，能夠在一定范圍之內(nèi)，按照自身規(guī)律不重復(fù)地遍歷所有狀態(tài)。具體的慣性權(quán)重因子的混沌擾動隨機(jī)數(shù)At的隨機(jī)公式如式(6)所述。

At=0.1×rand2×sin(π×rand)

(6)

其增加混沌隨機(jī)數(shù)擾動的慣性權(quán)重因子ω和進(jìn)化代數(shù)t的關(guān)系曲線(見圖2)。

圖2 增加混沌隨機(jī)數(shù)擾動的慣性權(quán)重因子ω和進(jìn)化代數(shù)t的關(guān)系曲線

2.4 隨機(jī)加速度系數(shù)的粒子群算法

為改善粒子算法的優(yōu)化性能，一部分學(xué)者對c1和c2的取值進(jìn)行了深入研究。其中，一些研究表明，對于較多的優(yōu)化問題，相比于采用固定加速系數(shù)的粒子群算法，采用動態(tài)加速系數(shù)的粒子群算法具有更好的優(yōu)化性能；與對稱策略的粒子群算法相比，非對稱策略的粒子群算法具有更好的優(yōu)化性能[9-10]。由沈艷等的研究成果可知，一般來說，加速度系數(shù)取值c1和c2的取值范圍在(0.5,2.5)區(qū)間[11]?；谏鲜鲅芯砍晒?，本文給出一種隨機(jī)生成加速度系數(shù)的原則：每次粒子群算法的迭代計算，c1和c2都取不同的值，其令c1≠c2。具體的權(quán)重的加速度系數(shù)c1和c2的隨機(jī)公式如式(7)所述。

csum=2×(0.5+2×rand)r=randc1=r×csumc2=(1-r)×csum

(7)

式(7)中：csum—c1和c2的和值;

r—為c1的比例系數(shù)；

1-r—c2的比例系數(shù)。

2.5 粒子改進(jìn)算法

由上論述可知，粒子群優(yōu)化方法雖然優(yōu)化搜索能力極強(qiáng)，但在迭代優(yōu)化后期，粒子群優(yōu)化方法面臨降低收斂速度，以及因陷入局部收斂而不易得到令人滿意的最優(yōu)解的問題。為具有更好的尋優(yōu)效果，克服粒子群算法的不足，兼顧收斂速度和尋優(yōu)精度的性能，本文提出了一種新的粒子群改進(jìn)算法，該算法同時改進(jìn)加速度系數(shù)和慣性權(quán)重，記為IPSO。具體的計算步驟如下所述：

Step 1初始化混合優(yōu)化算法的各項參數(shù)：粒子種群規(guī)模(粒子數(shù)量)N、迭代次數(shù)d、最大慣性權(quán)重ωmax、慣性權(quán)重因子的遞減斜率ωk；

Step 2隨機(jī)生成N種不同的解，也即生成初始種群；

Step 3計算N個粒子的適應(yīng)度函數(shù)值，并基于此對當(dāng)前粒子群進(jìn)行排序，以得到個體極值和全局極值；

Step 4采用公式(7)得到當(dāng)前迭代次數(shù)下的加速度系數(shù)c1和c2；

Step 5采用慣性權(quán)重因子線性遞減(LDW)的粒子群增加混沌隨機(jī)數(shù)擾動法的更新規(guī)則對所有粒子進(jìn)行更新；

Step 6確定迭代次數(shù)是否達(dá)到最大，如果達(dá)到最大則轉(zhuǎn)步驟Step 7，否則轉(zhuǎn)步驟Step 2；

Step 7輸出計算得到的最優(yōu)解的適應(yīng)度函數(shù)值。

3 仿真實驗

3.1 基于測試函數(shù)的仿真對比

基于3種不同的測試函數(shù)，采用粒子群改進(jìn)算法(IPSO)、慣性權(quán)重因子線性遞減(LDW)的粒子群增加混沌隨機(jī)數(shù)擾動法(CLDWPSO)和普通的慣性權(quán)重因子線性遞減粒子群算法(LDWPSO)求極小值，具體的仿真結(jié)果如下所述。

(2)De jong函數(shù)，最優(yōu)解為0.0。其De jong函數(shù)的解析式為F(x1,x2)=100×(x1-x2)2+(1-x1)2。

具體的函數(shù)的尋優(yōu)測試仿真結(jié)果(見圖3—5)。

圖3 采用Sphere函數(shù)的尋優(yōu)測試仿真結(jié)果圖

圖4 采用Dejong函數(shù)的尋優(yōu)測試仿真結(jié)果圖

圖5 采用Schaffer函數(shù)的尋優(yōu)測試仿真結(jié)果圖

由圖3—5可知，粒子群改進(jìn)算法(IPSO)的算法尋優(yōu)能力最強(qiáng)，其尋優(yōu)結(jié)果(見表1)。

表1 3種測試函數(shù)下的粒子群改進(jìn)算法(IPSO)的仿真結(jié)果統(tǒng)計表

3.2 基于實際算例的仿真對比

對于一個物流運(yùn)輸中心配送路線優(yōu)化問題的實際算例，分別采用粒子群改進(jìn)算法(IPSO)、慣性權(quán)重線性遞減(LDW)的粒子群增加混沌隨機(jī)數(shù)擾動法(CLDWPSO)和普通的慣性權(quán)重線性遞減粒子群算法(LDWPSO)求最優(yōu)的配送路線，使得配送總成本和配送總時間都盡可能的小。該實際算例選取沈陽市區(qū)的基礎(chǔ)建材配送案例，該案例中，含5輛配送車輛，車速均為15 km/h，配送成本50元/h分別可最多運(yùn)送130件相關(guān)產(chǎn)品，不可混合運(yùn)輸。此外，實際算例有9個客戶節(jié)點和4個物流中心。具體的相關(guān)數(shù)據(jù)(見表2—3)。

表2 物流中心相關(guān)數(shù)據(jù)表

具體的物流運(yùn)輸中心配送路線優(yōu)化問題的尋優(yōu)仿真結(jié)果(見6—7)。

表3 客戶點相關(guān)數(shù)據(jù)表

圖6中，粒子群改進(jìn)算法(IPSO)最優(yōu)。依據(jù)求解得到的配送路線進(jìn)行配送，其配送時間總和為11.89 h，配送成本為594.5元。粒子群改進(jìn)算法(IPSO)尋優(yōu)得到的具體的配送路線優(yōu)化結(jié)果(見圖7)。圖7中，紅色和藍(lán)色線條示意了運(yùn)送瓷磚的2輛車的配送路線，黃色和綠色線條示意了運(yùn)送地板的2輛車的配送路線，黑色線條示意了運(yùn)送理石的1輛車的配送路線，其配送順序和配送選擇都是非常合理的。

圖6 物流運(yùn)輸中心配送路線優(yōu)化問題的尋優(yōu)仿真測試結(jié)果圖

圖7 物流運(yùn)輸中心配送路線優(yōu)化仿真結(jié)果圖

4 結(jié) 論

本文提出了一種粒子群改進(jìn)算法(IPSO)用于解決物流中心配送路徑優(yōu)化問題的優(yōu)化模型。該方法一方面在慣性權(quán)重線性遞減的基礎(chǔ)上，加入了合理的混沌隨機(jī)數(shù)擾動量；另一方面，每一次迭代計算，都采用隨機(jī)的非對稱的加速度系數(shù)c1和c2，從而使粒子群算法得到更加令人滿意的最優(yōu)解，進(jìn)一步提升了粒子群算法的優(yōu)化性能。最后，本文采用了Sphere函數(shù)、De jong測試函數(shù)、Schaffer測試函數(shù)和一個具體的物流中心配送路線優(yōu)化問題的實際算例對本文提出的改進(jìn)算法IPSO、增加混沌隨機(jī)數(shù)擾動的慣性權(quán)重線性遞減(LDW)的粒子群算法(CLDWPSO)和普通的慣性權(quán)重線性遞減粒子群算法(LDWPSO)進(jìn)行仿真測試，其仿真結(jié)果都能夠表明本文提出的改進(jìn)算法(IPSO)優(yōu)于其它另外兩種優(yōu)化算法，具有更佳的尋優(yōu)性能，更適合于物流中心配送路線優(yōu)化問題的求解。