陳 艷

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

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

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

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

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

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

(1)n1種不同資源；

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

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

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

配送路線優(yōu)化問題的核心是節(jié)約其配送成本和配送時間。因此，配送路線優(yōu)化問題的優(yōu)化目標有兩個，配送時間總和和配送成本總和，記為Tsum和Csum。具體的以配送時間總和和配送成本總和作為優(yōu)化目標的優(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保證每個客戶只由一輛車輛負責(zé)配送一次，不能重復(fù)配送；約束3和約束4則保證所有物流中心和客戶都被配送到。目標1和目標2表示該配送優(yōu)化問題的優(yōu)化目標是配送時間總和Tsum和配送成本總和Csum。由上述物流中心配送優(yōu)化問題的優(yōu)化模型可知，該問題的解不易得到。

2 改進的粒子群算法

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)重因子ω線性遞減的粒子群改進算法受到研究人員的廣泛關(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)重因子取值較小則有利于改善局部搜索，達到尋優(yōu)精度要求，但同時也會以其收斂速度為代價，并且使粒子群算法局部收斂的概率隨之增加。采用粒子群算法時，在迭代前期，收斂速度較為重要；在其迭代后期，尋優(yōu)精度的重要性愈發(fā)明顯。

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

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

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

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

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

(5)

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

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

(6)

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗

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

基于3種不同的測試函數(shù)，采用粒子群改進算法(IPSO)、慣性權(quán)重因子線性遞減(LDW)的粒子群增加混沌隨機數(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可知，粒子群改進算法(IPSO)的算法尋優(yōu)能力最強，其尋優(yōu)結(jié)果(見表1)。

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

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

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

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

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

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

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

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

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

4 結(jié) 論

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