李雪竹

宿州學(xué)院，安徽宿州 234000

基于免疫螢火蟲算法的RFID倉儲車輛動態(tài)調(diào)度

李雪竹

宿州學(xué)院，安徽宿州 234000

針對物流配送實時倉儲車輛調(diào)度問題，提出了一種基于RFID技術(shù)的免疫螢火蟲車輛動態(tài)調(diào)度框架。建立了基于配送成本的帶約束條件車輛路徑問題數(shù)學(xué)模型，運用免疫螢火蟲優(yōu)化算法求解該模型，免疫螢火蟲優(yōu)化算法將螢火蟲優(yōu)化及免疫克隆技術(shù)融合，采用多層進化模式，在低層螢火蟲操作中及高層免疫操作中分別引入多態(tài)子種群自適應(yīng)機制和全局極值篩選策略，以提高算法全局收斂效率，在此基礎(chǔ)上設(shè)計了倉儲車輛動態(tài)調(diào)度框架，將車輛動態(tài)調(diào)度過程分為車輛調(diào)度任務(wù)控制和路徑優(yōu)化兩個階段，給出了車輛動態(tài)調(diào)度任務(wù)處理流程。實驗仿真表明，該車輛動態(tài)調(diào)度算法能夠有效地解決大規(guī)模動態(tài)物流車輛調(diào)度問題。

物流配送；路徑優(yōu)化；螢火蟲優(yōu)化算法；免疫算法；動態(tài)調(diào)度

隨著國民經(jīng)濟的不斷繁榮，物流產(chǎn)業(yè)得到了迅猛發(fā)展，物流配送已成為制約物流企業(yè)生存的重要因素[1-2]。車輛路徑問題（Vehicle Routing Problem，VRP）是物流配送研究的重要內(nèi)容[3]，為此學(xué)者展開了深入研究，并提出了針對不同類型VRP的配送路徑優(yōu)化求解方法，如動態(tài)規(guī)劃法、基于網(wǎng)絡(luò)模型的帶時間窗VPR（VRPTW）求解[4]、基于兩階段禁忌啟發(fā)式算法的選址-分配問題（Location-Allocation Problem，LAP）求解[5]等。隨著智能理論的不斷成熟，一些智能優(yōu)化算法如蟻群算法[1]、神經(jīng)網(wǎng)絡(luò)法[6]等被大量地應(yīng)用到VRP求解中，為物流配送路徑優(yōu)化提供了新的研究思路。然而大部分VRP求解方法屬于靜態(tài)、離線調(diào)度，并沒有考慮物流配送過程中數(shù)據(jù)的動態(tài)變化，顯然不能滿足現(xiàn)代物流實時動態(tài)調(diào)度的需要，而且智能算法自身固有缺陷對VRP求解結(jié)果的影響也值得進一步研究。

RFID[7]（Radio Frequency Identification）技術(shù)、信息技術(shù)、物聯(lián)網(wǎng)技術(shù)的有機結(jié)合，實現(xiàn)了物流配送動態(tài)追蹤和實時監(jiān)控，為物流配送動態(tài)管理提供了技術(shù)支撐。本文提出了一種基于RFID技術(shù)的免疫螢火蟲[8-9]車輛動態(tài)調(diào)度框架。車輛動態(tài)調(diào)度框架將車輛動態(tài)調(diào)度過程分為車輛調(diào)度任務(wù)控制和路徑優(yōu)化兩個階段，并給出了車輛動態(tài)調(diào)度任務(wù)處理流程，對于路徑優(yōu)化階段，建立了基于配送成本的帶約束條件車輛路徑問題數(shù)學(xué)模型，并運用免疫螢火蟲優(yōu)化算法求解該模型，車輛動態(tài)調(diào)度框架的提出為解決動態(tài)物流配送車輛調(diào)度問題提供了新的思路。

1 VRP問題描述及數(shù)學(xué)模型建立

現(xiàn)代物流網(wǎng)絡(luò)中存在多個物流配送中心，在進行物流配送服務(wù)之前需要通過“選址-分配”方法將整個物流網(wǎng)絡(luò)劃分成多個“單配送中心-多需求點”結(jié)構(gòu)[10]。物流配送路徑優(yōu)化問題可以描述為：配送中心具有m輛載重量已知的配送汽車（汽車集合為V={i|i=1，2，…，m}，第i輛汽車載重量為Qi），面向n個需求點進行服務(wù)（需求點集合為C={j|j=1，2，…，n}，第j個需求點需求量為qj），需求點地理位置及需求量確定，VRP優(yōu)化是指尋求某一汽車行駛路線，使得總成本最低。設(shè)配送中心與需求點集合為S={k|k=0，1，…，n}，其中，k=0表示配送中心，k=j表示第j個需求點。定義決策變量∈{0，1}(a，b∈S)、∈{0，1}。其中，=1表示車輛i由點a駛向點b，=1表示需求點j由車輛i服務(wù)。設(shè)S中兩點間的距離為dab，車輛i從點a駛向點b運輸單位成本為，車輛i在需求點j消耗固定成本為。物流配送VRP數(shù)學(xué)模型可以描述為：

其中，式（2）表示每條配送路徑的配送總量不大于配送車輛的載重量及車輛配送路徑長度不大于配送汽車最大配送距離Di，式（3）表示需求點只能由一輛配送車輛服務(wù)，式（4）表示訪問唯一性。

2 免疫螢火蟲優(yōu)化算法（IGSOA）

IGSOA采用多層進化模型，低層為M個子螢火蟲種群組成的螢火蟲群體集合G={E1，E2，…，EM}，高層為免疫抗體種群C。IGSOA算法初期對G群體進行多態(tài)自適應(yīng)螢火蟲操作，在算法后期，篩選子種群個體極值，并進行高層CSA操作，經(jīng)過CSA操作后粒子更新低層子種群個體極值。

2.1 多態(tài)子種群自適應(yīng)GSO操作

基本GSO算法工作過程可以描述為：隨機生成N只螢火蟲群體P，對于n維的優(yōu)化問題，螢火蟲Xi= (xi1，xi2，…，xin)代表問題的一個解。螢火蟲Xi攜帶的熒光素量為li(t)，其數(shù)量的大小由目標(biāo)函數(shù)值f(Xi)決定。初始時刻螢火蟲具有相同的熒光素l0和決策范圍rd，在t時刻，li(t)按式（5）更新。

其中，ρ∈(0，1)、γ∈(0，1)為熒光素控制因子。螢火蟲Xi在其決策范圍內(nèi)選擇亮度高于自己的粒子組成領(lǐng)域集Ni(t)，并以概率pij選擇Xj(Xj∈Ni(t))按式（7）進行轉(zhuǎn)移。

基本GSO與其他智能算法相比，同樣具有算法收斂效率不高的缺陷[11]，特別是在算法后期，當(dāng)某個螢火蟲為局部極值點時，其他粒子會向其聚攏，使得算法出現(xiàn)早熟現(xiàn)象。為了提高GSO尋優(yōu)能力，本文提出了多態(tài)子種群自適應(yīng)機制：對于子種群Ei，其螢火蟲按f(Xi)降序排列，具有較優(yōu)適應(yīng)度的螢火蟲劃分為精英群，其余的為搜索群。由于精英群內(nèi)的螢火蟲良好的較優(yōu)的適應(yīng)度值，因此采用式（9）精英機制進行更新，使得螢火蟲很容易跳出局部極值；對于搜索群內(nèi)的螢火蟲，借鑒PSO粒子更新機制，采用式（10）（11）的改進粒子更新策略，充分利用了群體歷史最優(yōu)信息，提高了樣本搜索空間。

其中，Xg為整個螢火蟲種群適應(yīng)度最好的解，Xb為Ei中適應(yīng)度最優(yōu)的解，Tmax為算法最大迭代次數(shù)。式（9）的基礎(chǔ)上增加了群體優(yōu)秀個體信息，提高了樣本多樣性，式（10）為自適應(yīng)的高斯變異，隨著迭代次數(shù)增加，σ逐漸減小，使得螢火蟲在算法后期，能夠在較小的學(xué)習(xí)空間內(nèi)進行精細(xì)度搜索，提高了算法精度。

定義螢火蟲種群進化因子D(t)為：

其中，α為極小正數(shù)。D(t)取值代表了種群進化程度，根據(jù)D(t)的大小可以自適應(yīng)的調(diào)整精英群和搜索群規(guī)模。對于Ei，其搜索群規(guī)模Ni，s(t)按式（13）更新。

通常設(shè)定Nmin≤Ni，s(t)≤Nmax。從式（12）（13）可以看出，算法運算初期D(t)取值較大，表明樣本空間比較大，因此搜索群規(guī)模較小；算法運算后期，D(t)取值減少，表明種群多樣性降低，而搜索群規(guī)模變大，使得粒子能在更大的空間中尋找最優(yōu)解。得到Ni，s(t)后，精英群規(guī)模Ni，L(t)按式（14）確定。

2.2 高層CSA操作

全局極值篩選策略：設(shè)Ei極值點集合為Pi={X′i}，螢火蟲整個群體全局極值點集合為Pmin。取Ei中的Xb為Pmin第一點，然后依次從Pi中取X′i，如果X′i滿足式（15），則X′i為種群全局極值點。

其中，f(Z)為理論全局極值，ε為判定常數(shù)。定義CSA親和度函數(shù)為aff(ai)。對于高層CSA操作，其種群C由低層Ei的Pmin組成。高層CSA操作工作過程可以描述為：

步驟1克隆擴增。對于Pmin中的抗體按照式（16）進行克隆擴增。

其中，aff(Ej)為低層Ej中最優(yōu)個體親和度值。顯然具有較優(yōu)適應(yīng)度的子種群獲得了較大的克隆倍數(shù)，充分保留了優(yōu)秀個體信息。

步驟2自適應(yīng)變異?？寺『蟮目贵wCk按式（17）進行變異。

其中，Cu、Cl為Ck上下限。式（17）說明Ck能夠根據(jù)進化過程自動調(diào)整粒子變異空間。

步驟3免疫選擇。對于Ck(t)，其克隆及變異后抗體集合為S，取S中親和度最優(yōu)個體C′k(t)，并判斷C′k(t)是否優(yōu)于Ck(t)，若是，則Ck(t+1)←C′k(t)，否則Ck(t)保持不變。

2.3 VRP中IGSOA粒子編碼方式及更新策略

對于VRP問題，每只螢火蟲代表了一種路徑優(yōu)化方案，為此，本文結(jié)合約束條件，給出了螢火蟲粒子編碼方式：在IGSOA中，定義螢火蟲位置為序列為Xi=(0，xi1，xi2，…，0，…，0，xij，…，xin，0)(xij∈[1，n]，Xi∩[1，n]≠?)，而且編碼中取值為0的編碼位數(shù)量為m+1。螢火蟲編碼位取0表示為配送中心，取1～n則表示對應(yīng)的需求點。例如某個螢火蟲編碼序列為(0，3，5，0，4，1，2，0，6，0)，它表示配送中心共3輛汽車，服務(wù)于6個需求點，而且3輛汽車配送路線分別為0→3→5→0、0→4→1→2→0、0→6→0。對于該螢火蟲編碼方式如果仍然采用式（9）、（10）、（17）粒子更新方式會產(chǎn)生大量不符合約束條件的解，嚴(yán)重降低了算法求解效率，為此，本文參考文獻[12]，在式（9）、（10）、（17）的基礎(chǔ)上給出了適用于VRP螢火蟲編碼方式的個體更新策略。通過觀察約束條件及螢火蟲編碼定義，可以發(fā)現(xiàn)，不同的粒子編碼可以相互轉(zhuǎn)化，例如對于編碼A:(0，1，2，0，3，0)和編碼B:(0，3，2，0，1，0)，將編碼A編碼位2和5進行調(diào)換就可以轉(zhuǎn)化為編碼B，因此可以定義編碼為調(diào)換操作EX(i1，i2)，其中i1，i2表示編碼位。任意兩個編碼都可以通過一系列調(diào)換操作進行轉(zhuǎn)化，定義調(diào)換序列為CH(A?B)={EX1，EX2，…，EXl}，顯然0≤l≤m+n。編碼轉(zhuǎn)換可以描述為B=A+CH(A?B)（如圖1所示）。

圖1 改進的IGSOA粒子更新策略

對于式（9），修改后的螢火蟲更新策略為：

其中，|CH(Xb?Xi)|表示CH(Xb?Xi)中調(diào)換操作的個數(shù)，式（20）表示分別取調(diào)換序列的前i、j個調(diào)換操作。

對于式（17），修改后的更新策略為：

對于式（10），采用逆轉(zhuǎn)算子進行領(lǐng)域搜索，逆轉(zhuǎn)算子對編碼內(nèi)子線路進行操作，從子路徑內(nèi)隨機選擇某編碼位進行逆轉(zhuǎn)（如圖2所示），修改后的更新策略為：

其中，EXi表示第i個子路徑調(diào)換操作，μ為控制系數(shù)，在算法進化初期，算法選擇較多的子路徑進行逆轉(zhuǎn)算子操作，提高搜索空間，算法后期，只選擇少量子路徑進行轉(zhuǎn)換，提高了收斂速度。

圖2 逆轉(zhuǎn)算子過程示意圖

2.4 IGSOA算法實現(xiàn)流程

本文采用采用IGSOA對VRP數(shù)學(xué)模型進行求解，因此，IGSOA目標(biāo)函數(shù)為f(X)=minE。IGSOA算法流程描述為：

3 倉儲車輛動態(tài)調(diào)度

圖3 倉儲車輛動態(tài)調(diào)度架構(gòu)

圖3給出了倉儲車輛動態(tài)調(diào)度框架，倉儲車輛動態(tài)調(diào)度框架是指將車輛動態(tài)調(diào)度過程分為車輛調(diào)度任務(wù)控制和路徑優(yōu)化兩個階段。車輛調(diào)度任務(wù)控制就是根據(jù)裝載率和系統(tǒng)剩余派送車輛之間的關(guān)系動態(tài)控制待處理任務(wù)，當(dāng)判定條件滿足時，調(diào)用IGSOA車輛調(diào)度算法，完成調(diào)度任務(wù)處理，任務(wù)處理完成后，進入下一次工作周期。RFID技術(shù)主要為倉儲車輛動態(tài)調(diào)度提供配送車輛實時狀態(tài)、配送任務(wù)處理情況等信息。

判定條件1預(yù)配送車輛數(shù)m′估算根據(jù)任務(wù)請求時間，對待處理任務(wù)進行排序，序列集為R={R1，R2，…，Ri，…}，其中Ri的需求量為qi。在R中取前j個任務(wù)組成預(yù)處理任務(wù)集合R′={R1，R2，…，Rj}，則有：

其中，?為車輛裝載控制因子，Qmax、Qmin分別為配送車輛最大和最小裝載量。

判定條件2裝載率τ計算當(dāng)配送中心剩余車輛大于m′時，定義此時剩余車輛總載量為Qm，則有：

一般設(shè)定裝載率閾值τmin（通常取0.85），只有當(dāng)滿足τ≥τmin時才進行任務(wù)分配。

4 仿真實驗

4.1 實例仿真

為了驗證IGSOA算法求解性能，構(gòu)造30個需求點的算例：配送中心坐標(biāo)為（50，50）（單位：km），共有1輛6 t、3輛8 t和1輛16 t的配送汽車，3種車型成本費用如表1所示。30個需求點位置信息及需求量如表2所示。IGSOA具體參數(shù)設(shè)置為：N=500，M=5，ω1=0.8，ω2= 0.2，ε=1×10-4，l0=5，ρ=0.4，γ=0.6，s=0.03、β=0.08，Nt=5，設(shè)初始時刻rd與rs值相同，取值為30，Tmax=500，ε=1×10-4。

表1 配送車輛使用成本

表2 需求點信息

表3 車輛調(diào)度分配方案

圖4 車輛調(diào)度仿真結(jié)果

4.2 IGSOA算法性能分析

為了進一步分析IGSOA性能，分別采用IGSOA、GSO、SFLA[12]對算例進行解算，運行50次，表4給出了3種算法性能比較（S表示最優(yōu)總運行距離，Sˉ表示平均總運行距離，Tˉ表示算法平均運行時間，tˉ表示算法平均迭代次數(shù)，V表示算法搜索成功率），圖5給出了路徑長度隨迭代次數(shù)變化曲線。

表4 不同算法性能比較

從表3及圖4可以看出，IGSOA能夠有效地給出配送汽車調(diào)度方案，而且每輛車輛的裝載率在85%以上。從表4及圖5可以看出，IGSOA在運行時間、運輸距離和求解成功率方面都高于其他兩種算法，這是因為IGSOA采用低層多態(tài)子種群自適應(yīng)操作機制，因此具有很強的局部搜索能力，同時高層CSA操作進一步提高了算法收斂精度，優(yōu)化結(jié)果更符合實際情況。

圖5 路徑長度隨迭代次數(shù)變化曲線

5 結(jié)語

對物流配送實時倉儲車輛調(diào)度問題進行了研究，建立了車輛路徑問題數(shù)學(xué)模型，給出了IGSOA算法求解VRP流程，設(shè)計了螢火蟲特殊編碼方式和更新策略，并分析了基于RFID技術(shù)的倉儲車輛動態(tài)調(diào)度框架，給出了車輛動態(tài)調(diào)度任務(wù)處理流程。實驗結(jié)果表明，IGSOA可以快速有效地給出優(yōu)化物流配送車輛調(diào)度方案。

[1]張維澤，林劍波，吳洪森，等.基于改進蟻群算法的物流配送路徑優(yōu)化[J].浙江大學(xué)學(xué)報：工學(xué)版，2008，42（4）：574-578.

[2]Bell J E，Mcmullen P R.Ant colony optimization techniques for the vehicle routing problem[J].Advanced Engineering Informatics，2004，18（1）：41-48.

[3]朱玲玲，楊愛琴，吳寬仁.基于協(xié)同自適應(yīng)禁忌的多時窗VRP算法實現(xiàn)[J].計算機應(yīng)用研究，2012，29（12）：4542-4545.

[4]田青，繆立新，鄭力.基于運輸規(guī)劃和組合GA的基本物流網(wǎng)絡(luò)設(shè)計[J].清華大學(xué)學(xué)報，2004，44（11）：1441-1444.

[5]張潛，高立群，劉雪梅，等.定位-運輸路線安排問題的兩階段啟發(fā)式算法[J].控制與決策，2004，19（7）：773-777.

[6]Effati S，Jafarzadeh M.Nonlinear neural networks for solving the shortest path problem[J].Applied Mathematics and Computation，2007，189（1）：567-574.

[7]孔寧，李曉東，羅萬明，等.物聯(lián)網(wǎng)資源尋址模型[J].軟件學(xué)報，2010，21（7）：1657-1666.

[8]Krishnanand K N，Ghose D.Theoretical foundations for rendezvous of glowworm-inspired agent swarms at multiple locations[J].Robotics and Autonomous Systems，2008，56（7）：549-569.

[9]Eusuff M M，Lansey K E.Optimization of water distribution network design using the shuffled frog leaping algorithm[J].Water Resources Planning and Management，2003，129（3）：210-225.

[10]彭揚，陳子俠，吳承鍵.定位-運輸路線安排問題的改進離散粒子群優(yōu)化算法[J].智能系統(tǒng)學(xué)報，2010，5（1）：74-79.

[11]孟慶瑩，王聯(lián)國.基于領(lǐng)域正交叉算子的混合蛙跳算法[J].計算機工程與應(yīng)用，2011，47（36）：54-56.

[12]羅雪暉，楊燁，李霞.改進混合蛙跳算法求解旅行商問題[J].通信學(xué)報，2009，30（7）：130-135.

LI Xuezhu

Suzhou University,Suzhou,Anhui 234000,China

For the real-time warehousing logistics vehicle scheduling problem（LVCP）,an RFID-enabled vehicle dynamic scheduling algorithm based on Immune Glowworm Swarm Optimization Algorithm（IGSOA）is proposed.A mathematical model for Vehicle Routing Problem（VRP）with delivery cost is established,and the IGSOA is used to solve this model. IGSOA combines the GSO and CSA technology,and adopts a multi-layer evolution pattern.The polymorphic adaptive population mechanism and global extreme screening strategy are introduced in the low GSO operation and high immune operation,in order to improve the IGSOA convergence efficiency.Based on above analysis,a vehicle dynamic scheduling framework is presented,and the vehicle dynamic scheduling process is divided into two stages as vehicle scheduling tasks control and VRP optimization.The process of LVCP is given.Experimental results show that,the IGSOA can effectively solve large-scale LVCP.

logistic distribution;optimizing routing;glowworm swarm optimization algorithm;immune algorithm;dynamic scheduling

A

TP18

10.3778/j.issn.1002-8331.1305-0429

LI Xuezhu.RFID-enabled dynamic storage vehicle scheduling based on immune glowworm swarm optimization algorithm.Computer Engineering and Applications,2014,50（6）：235-239.

2013年安徽省高校省級自然科學(xué)研究一般項目（No.KJ2013Z320）；宿州學(xué)院第六屆國家級大學(xué)生創(chuàng)新創(chuàng)業(yè)訓(xùn)練計劃項目（No.201210379002）；宿州學(xué)院科研開放平臺項目（No.2013YKF18）。

李雪竹，女，講師，研究領(lǐng)域為人工智能、物聯(lián)網(wǎng)。E-mail：xzli_love@126.com

2013-05-31

2013-08-19

1002-8331（2014）06-0235-05