王俊峰，李玉華，張凱麗

（合肥工業(yè)大學　管理學院，安徽　合肥　230009）

基于螢火蟲算法帶時間窗的雙向配送調(diào)度

王俊峰，李玉華，張凱麗

（合肥工業(yè)大學管理學院，安徽合肥230009）

針對帶時間窗的雙向配送調(diào)度問題，重新建立新的帶多目標的數(shù)學模型，提出一種離散型螢火蟲算法和編碼策略，并重新定義了個體交叉變異移動公式。同時，根據(jù)螢火蟲編碼個體之間的邏輯距離，構(gòu)建鄰域集合，提高局部搜索能力。并引進個體歷史最優(yōu)記憶功能，加快收斂速度。最后利用隨機數(shù)和求余函數(shù)對編碼個體進行擾動，防止過早陷入局部極值。通過仿真案例實驗驗證了算法的有效性。

雙向配送；時間窗；多目標；離散型螢火蟲算法

1　引言

如今，全球經(jīng)濟的繁榮和生活節(jié)奏的加快，快捷及時、低碳環(huán)保的運輸配送日益重要。其中，車輛路徑問題VRP（Vehicle Routing Problem，VRP）一直是學者專家熱衷的研究課題。隨著信息智能化技術(shù)的發(fā)展，研究學者更是把人工智能優(yōu)化算法引入到車輛配送調(diào)度問題中，為配送問題提供了比較滿意的解決方案。對此，針對不同類型的車輛配送調(diào)度問題，研究學者提出了不同的解決方案。

文獻［1］Jayaraman對包含多產(chǎn)品、單個生產(chǎn)工廠、多個配送中心的物流配送網(wǎng)絡(luò)優(yōu)化問題進行了研究，并用模擬退火算法對該問題的直撥運輸情況進行了一定程度的優(yōu)化。文獻［2］分析了大中城市市內(nèi)郵政運輸路徑規(guī)劃中存在路徑重復的弊端，利用禁忌搜索算法對大中城市市內(nèi)的郵政運輸車輛配送問題進行了探索，并提出了輻射型郵路的解決方案。文獻［3］運用整體優(yōu)化的思想，利用離散型粒子群優(yōu)化算法并加入了變異和擾動因子，對定位-運輸路線安排問題進行了深入研究，得到了一定的效果。文獻［4］利用RFID技術(shù)實現(xiàn)物流配送動態(tài)數(shù)據(jù)的跟蹤，但是研究目標單一，不能很好地滿足現(xiàn)實中物流配送的及時性和提高客戶滿意度的要求。在分析了前面研究的基礎(chǔ)上，本文將利用螢火蟲算法解決車輛雙向配送調(diào)度問題。

螢火蟲優(yōu)化算法（Glowworm Swarm Optimization，GSO）是由印度學者K.N.Krishnanad和D.Ghose于2005年提出的一種新型仿生群智能優(yōu)化方法［5］。該算法具有較好的全局優(yōu)化搜索能力，在函數(shù)優(yōu)化［6-8］、多信號源追蹤定位［9］等連續(xù)優(yōu)化問題方面取得了一些成果，但是在組合優(yōu)化具有離散性質(zhì)問題方面的研究才剛剛起步。并且，螢火蟲算法也和其他群智能優(yōu)化算法一樣，存在優(yōu)化精度低、收斂速度慢、震蕩等缺點［10］。郭麗萍、周永權(quán)等［11-13］將螢火蟲算法應用到離散型TSP組合優(yōu)化問題中，不過螢火蟲算法缺少個體的自身反饋和群體引導沒有被考慮到，以致優(yōu)化不明顯。對螢火蟲算法進行全面深入的研究，在理論拓展和工程應用實踐上都具有重要意義。本文不僅豐富了解決物流配送調(diào)度問題的優(yōu)化解決算法，還拓寬了螢火蟲算法的應用領(lǐng)域。

2　帶有時間窗的雙向配送問題描述和數(shù)學模型建立

通常一個高級的物流配送中心周圍存在著多個低級的物流配送中心，并進行雙向交流。我們把此簡化成“一個中心，多個供需點”結(jié)構(gòu)。然而，傳統(tǒng)的配送路徑規(guī)劃通常只考慮路徑最短或配送車輛最少的單個性能指標，不能很好地滿足現(xiàn)代物流配送的及時性要求和客戶滿意度。針對此結(jié)構(gòu)，我們對帶時間窗的雙向配送路徑調(diào)度優(yōu)化問題重新建立數(shù)學模型和多目標指標并進行研究。

2.1問題描述

配送中心需要m臺相同的配送車輛。車輛最大載重為w，平均速度為v，最長行駛路程為L。供需點有n個，供需點i需求量為ri，供應量為ui，與配送中心之間的距離為di0，要求服務時間段為［］ai，bi。任意兩個供需點i和 j之間的距離為dij。裝載或卸掉每噸貨物需要時間長為t小時。用集合Rk表示第k輛車的行駛路徑，Rk中供需點的順序表示被服務的先后順序，用Ck表示Rk中元素的個數(shù)，即第k輛車所服務供需點的個數(shù)。Rk中元素rky表示供需點rky被第k輛車服務的順序為y（y=1，2，…，Ck），令rk0表示配送中心?，F(xiàn)規(guī)定：在此時間段之前到達或之后離開，都將耽誤時間；車輛在配送過程中其載貨量不能超過其最大載重量；每條配送路徑的長度不能超過配送車輛的最長行駛路程。

2.2模型建立

以配送總路程最短為主要目標，以使用的車輛數(shù)最少、耽誤的時間最短為輔助目標。其中，目標函數(shù)、約束條件公式如下：

在目標函數(shù)中，tia表示提前到達供需點i而等待耽誤的時間，tib表示晚點離開供需點i而耽誤的時間；公式（6）表示達到下一供需點的時間=達到當前供需點時間+等待時間+卸貨和裝貨時間+行駛時間，srki表示到達供需點rki的時間，trkia表示在供需點rki時間窗之前到達需要等待的時間。如果在時間窗內(nèi)到達，則trkia=0；公式（7）表示車輛行駛到下一供需點卸掉該點需求量，裝上該點供應量之后不能大于最大載重，uk0表示配送中心。

3　基本的螢火蟲算法描述

螢火蟲算法是模擬自然界中螢火蟲覓食行為的一種群智能優(yōu)化算法。螢火蟲會發(fā)光，光亮強度由自身所攜帶的熒光素決定。熒光素越多，發(fā)光越亮，代表該螢火蟲所在位置的適應度值也高，從而在感知范圍內(nèi)吸引其他螢火蟲移動。每只螢火蟲的移動分為三個階段，即熒光素更新、螢火蟲個體移動和感知范圍更新。螢火蟲算法無非就是此三個階段的反復迭代。每個階段的相關(guān)描述如下［14］：

第一階段：熒光素更新。利用公式（8）計算螢火蟲Xi第t代的熒光素值。其中是螢火蟲 Xi第代的熒光素值，ρ是熒光素揮發(fā)因子是螢火蟲Xi第t代的位置是所對應的適應度值，γ是熒光素更新率。

第二階段：螢火蟲個體移動。利用公式（9）計算螢火蟲Xi向內(nèi)每只螢火蟲移動的概率，且利用公式（10）計算螢火蟲Xi第代的位置。其中是第t代在螢火蟲Xi感知范圍內(nèi)的并且比自己亮、比自己適應度值高的螢火蟲的鄰域集合，s是移動步長。

第三階段：感知范圍更新。利用公式（11）計算螢火蟲Xi第代的感知范圍半徑。其中，rs是每只螢火蟲的初始感知半徑，β是感知范圍更新率，nt是感知范圍內(nèi)包含螢火蟲數(shù)目的閾值是螢火蟲Xi感知范圍內(nèi)的并且比自己亮的螢火蟲的數(shù)目。

4　改進的螢火蟲算法

4.1編碼策略

針對上述提到的車輛雙向配送調(diào)度模型，對配送中心編號為0，n個供需點編號為1，2，…，n。并進行編碼：對n個供需點從1到n進行無重復地隨機全排列，構(gòu)成一個螢火蟲個體 Xi=（xi1，xi2，…，xij，…，xin），j=1，2，…，n，xij∈（1，2，…，n）。

4.2適應度值計算

把主要目標配送的總路程當做適應度值。計算適應度值就是計算配送的總路程，就得在編碼的基礎(chǔ)上插入0。插入0的規(guī)則是：這個全排列首尾插入0，然后根據(jù)約束條件，從頭到尾在適當位置依次插入0。0與0之間的編號表示一輛車從配送中心出發(fā)，所要配送的供需點，最后又回到配送中心。把所有車輛配送的距離加起來，就是配送的總距離，就是適應度值。并借鑒魚群算法中的公告板［15］，將適應度值和當前編碼狀態(tài)保存到公告板。此時，作為輔助目標，需要的車輛個數(shù)就是0的個數(shù)減1。比如，隨機生成的全排列632451，插0之后，變成序列0632405010，表示需要3輛車。第1輛車從配送中心出發(fā)，先后配送6，3，2，4四個供需點，最后回到配送中心。第2輛車配送5號供需點，第3輛車配送1號供需點。

4.3個體之間的邏輯距離計算

針對本文具體的編碼方式，重新定義構(gòu)建感知范圍內(nèi)鄰域集合的方法。螢火蟲個體Xi（t）依公式（12）計算出與其他個體之間的邏輯距離dij（t），并將dij（t）與rid（t）進行比較。將與Xi（t）之間距離dij（t）比rid（t）小的且比Xi（t）適應度值大的螢火蟲個體放入鄰域集合。

4.4定義個體移動方式

借鑒粒子群算法的個體產(chǎn)生機制［16］，更改公式（9）、（10）概率移動方式，重新定義離散型螢火蟲算法的個體移動方式，并引進個體歷史最優(yōu)。個體Xi（t）移動除了受前一次移動結(jié)果的影響外，還要受個體歷史最優(yōu)Xh、感知范圍內(nèi)最優(yōu)個體Xg的影響。個體Xi（t+1）中第 j個元素xij（t+1）是在個體Xi（t）中第 j個元素xij（t）基礎(chǔ)上根據(jù)概率被Xi（t）本身或Xh（t）或Xg（t）中第j個元素所代替形成的，見移動方式公式（13）。在替換過程中，如果被替換之后所形成的Xi（t+1）第 j個元素xij（t+1）與Xi（t）第j個元素之后的某個元素xik（t）相同，則把xik（t）替換成xij（t），保證在后面的替換過程中Xi（t+1）個體元素不會出現(xiàn)重疊；如果被替換之后所形成的Xi（t+1）第 j個元素xij（t+1）與Xi（t+1）第j個元素之前的某個元素xih（t+1）相同，則把Xi（t+1）第 j個元素xij（t+1）替換成xij（t），防止元素出現(xiàn)重疊。

表1　移動方式演示

4.5添加擾動項

螢火蟲算法在尋優(yōu)時容易出現(xiàn)早熟現(xiàn)象陷入局部極值中。為了讓算法跳出局部極值，增加個體多樣性，本文采用了加隨機數(shù)、求余數(shù)擾動項。采用公式（14）對螢火蟲個體Xi（t）里面的元素xij（t）進行擾動。其中，rand（）表示隨機生成一個從1到29的整數(shù)，mod（a，b）表示求a除以b的余數(shù)。公式對算法起到擾動效果，并且確保了元素都在1到30之間，增加了個體多樣性。

4.6改進的螢火蟲算法求解配送路徑優(yōu)化的步驟

（1）按照編碼方式隨機生成N個螢火蟲個體，并初始化算法參數(shù)。

（2）計算每只螢火蟲初始時所在位置的適應度值，并將每只螢火蟲初始時的位置狀態(tài)和適應度值保存到公告板。

（3）利用公式（8）更新每只螢火蟲的熒光素值。

（4）每只螢火蟲利用式（12）尋找感知范圍內(nèi)比自己熒光素值大的個體，添加到鄰域集合。如果找不到，利用式（14）進行擾動移動，再轉(zhuǎn)步驟（6）。

（5）在感知范圍內(nèi)，每只螢火蟲利用式（13）向自己的歷史最優(yōu)、鄰域集合內(nèi)最優(yōu)個體移動。

（6）計算每只螢火蟲移動之后的適應度值，并將每只螢火蟲在移動迭代過程中適應度值最高時的位置狀態(tài)和最高適應度值更新到公告板。

（7）若滿足終止條件，則輸出公告板紀錄的結(jié)果；否則，根據(jù)公式（11）更新感知半徑，轉(zhuǎn)步驟（3）。

5　仿真實驗

5.1仿真環(huán)境

采用Matlab R2012a軟件編碼測試，編譯運行程序PC機的設(shè)置：32位Win7操作系統(tǒng)，處理器：Intel（R）Core（TM）i5-3570 CPU@3.40GHz，安裝內(nèi)存：4.00GB。

5.2參數(shù)設(shè)置

為了驗證改進螢火蟲算法對本文配送路徑優(yōu)化具體問題的求解性能，對改進的離散型螢火蟲算法參數(shù)設(shè)置如下：螢火蟲個體數(shù)N=100、最大迭代次數(shù)Max=500、熒光素揮發(fā)因子ρ=0.4、熒光素更新率γ=0.6、感知半徑更新率β=8、感知范圍域閾值nt=5、初始熒光素值l0=5、初始感知半徑rs=50。并給出1個配送中心、30個供需點進行模擬運算。配送中心坐標為（20km，20km），配送車輛速度為20km/h，最大載重為2t，最長行駛距離為55km。每1h卸掉或裝載貨物1t，即t=1。供需點坐標及時間窗、供應量、需求量見表2。

表2　供需點坐標及時間窗、供應量、需求量

5.3結(jié)果分析

采用改進的螢火蟲算法對配送路徑調(diào)度經(jīng)過500次的迭代運算之后，得到比較滿意的結(jié)果見表3。

針對表5的運算結(jié)果，我們給出了最終比較滿意的車輛調(diào)度仿真可視化路線，如圖1所示。

為了進一步驗證改進螢火蟲算法的性能，分別采用遺傳算法、粒子群算法求解的結(jié)果和改進螢火蟲算法求解的結(jié)果進行對比，見表4。

表3　運算結(jié)果

圖1　車輛雙向配送調(diào)度仿真結(jié)果

表4　結(jié)果對比

由表4看到，不管是主目標還是輔助目標，改進的螢火蟲算法都取得了最好的求解結(jié)果，

圖2　配送距離與迭代次數(shù)的關(guān)系

通過圖2可以清楚地看到，在求解配送距離迭代過程中，不管在收斂速度上還是最終最短路徑上，改進的螢火蟲算法都要優(yōu)于粒子群算法和遺傳算法。收斂速度，改進的螢火蟲算法要優(yōu)于粒子群算法和遺傳算法，得益于添加的歷史最優(yōu)記憶功能，加快了收斂速度。通過圖3，雖然粒子群算法剛開始收斂比較快，不過最后變慢了，并且收斂值不如遺傳算法和改進的螢火蟲算法，改進的螢火蟲算法效果更優(yōu)。從圖4可以看到，隨著迭代次數(shù)的增加，配送車輛數(shù)逐漸收斂，達到了比較滿意的狀態(tài)。這三張圖的數(shù)據(jù)都表明了改進的離散型螢火蟲算法還是比較優(yōu)越的。改進的螢火蟲個體邏輯距離公式更適合離散的編碼個體距離計算，用改進的計算方法構(gòu)建了鄰域集合，加快了局部搜索精度。歷史最優(yōu)記憶功能和擾動項的加入提高了收斂速度，比較符合實際情況。

圖3　耽誤時間與迭代次數(shù)的關(guān)系

圖4　配送車輛數(shù)和迭代次數(shù)的關(guān)系

6　小結(jié)

車輛路徑問題VRP是一類很復雜的NP問題，是目前熱點研究問題。本文利用改進的離散型螢火蟲算法對帶有時間窗的車輛雙向配送調(diào)度問題進行了深入研究，構(gòu)建了新的帶多目標的數(shù)學模型和特殊的編碼方式，給出了求解步驟和處理流程。移動方式的改進，擾動項的添加，提高了算法收斂速度和局部搜索能力。最后通過實例驗證，并和遺傳算法、粒子群算法進行了對比，結(jié)果證明改進的離散型螢火蟲算法求解帶有時間窗的雙向配送調(diào)度問題的可行性和優(yōu)越性。

［1］Jayaraman V，Ross A.A simulated annealing methodology to distributionnetworkdesignandmanagement［J］.European Journal of Operational Research，2003，144:614-643.

［2］段鳳華，符卓.有軟時窗約束帶取送作業(yè)的車輛路徑問題及其禁忌搜索算法［J］.計算機工程與科學，2009，31（3），68-74.

［3］彭揚，陳子俠，吳承建.定位-運輸路線安排問題的改進離散粒子群優(yōu)化算法［J］.智能系統(tǒng)學報，2010，5（1）:75-79.

［4］吳斌，錢存華，倪衛(wèi)紅.基于免疫螢火蟲算法的RFID倉儲車輛動態(tài)調(diào)度［J］.計算機工程與應用，2013，49（6）.

［5］Krishnanand K N，Ghose D.Glowworm Swarm Optimization for Multimodal Search Spaces［A］.Handbook of Swarm Intelligence［C］. Springer Berlin Heidelberg，2010.

［6］劉佳昆，周永權(quán).一種最大最小熒光素值人工螢火蟲算法［J］.計算機應用研究，2011，28（10）:3 662-3 664.

［7］王湘中，俞壽益.多模態(tài)函數(shù)優(yōu)化的多種群進化策略［J］.控制與決策，2006，21（3）:285-288.

［8］Horng Ming-Huwi，Liou Ren-Joan.Multilevel minimum cross entropy threshold selection based on the firefly algorithm［J］.Expert Systems with Applications，2011，38（11）:14 805-14 811.

［9］Krishnanand K N，Ghose D.Chasing Multiple Mobile Signal Sources:A Glowworm Swarm Optimization Approach［A］.Proc of the 3rd Indian International Conference on Artificial Intelligence［C］.IEEE Press，2007.

［10］Deep K，Bansal J C.Mean particle swarnl optimization for functionoptimization［J］.IntJComputational Intelligence Studies，2009，1（1）:1-19.

［11］張軍麗，周永權(quán).人工螢火蟲與差分進化混合優(yōu)化算法［J］.信息與控制，2011，40（5）:608-613.

［12］郭麗萍，李向濤，谷文祥，等.改進的螢火蟲算法求解阻塞流水線調(diào)度問題［J］.智能系統(tǒng)學報，2013，8（1）:33-38.

［13］周永權(quán)，黃正新.求解TSP的人工螢火蟲群優(yōu)化算法［J］.控制與決策，2012，27（12）:1 816-1 821.

［14］Krishnanand K N，Ghose D.Glowworm swarm optimization:a new method for optimizing multimodal functions［J］.International Journal of Computational Intelligence Studies，2009，1（1）:93-119.

［15］Ma Xian-min，Liu Ni.Improved artificial fish-swarm algorithm based on adaptive vision for solving the shortest path problem［J］.Journal on Communications，2014，（1）:1-6.

［16］Kennedy J，Eberhart R C.Particle swarm optimization［A］. Proc of IEEE International Conference on Neural Network: Service Center［C］.1995.

Study on Bidirectional Distribution Scheduling with Time Window Based on Glowworm Swarm Optimization

Wang Junfeng，Li Yuhua，Zhang Kaili
（School of Management，Hefei University of Technology，Hefei 230009，China）

In this paper，we developed a new multi-objective mathematical model for the bidirectional distribution scheduling problem with time window，proposed a discrete glowworm swarm optimization and the relevant coding strategy，and further redefined the formula of the crossover，mutation and movement of the individuals.Meanwhile，according to the logical distance between the individual glowworm swarm optimization，we established the neighborhood set to improve the local search ability of the algorithm.Next we introduced the optimal historical memory function of the individuals to accelerate convergence.At the end，we used the random number and the remainder function to protect the individual codes from interference and prevent local convergence and demonstrated the validity of the algorithm through a simulated case study.

bidirectional distribution；time window；multi-objective；discrete glowworm swarm optimization

F224；F252.14

A

1005-152X（2016）04-0058-06

10.3969/j.issn.1005-152X.2016.04.016

2016-03-13

王俊峰（1957-），男，湖北黃梅人，博士，主要研究方向：工業(yè)工程、物流優(yōu)化及信息化；李玉華（1990-），男，山東臨沂人，碩士，研究方向：工業(yè)工程、人工智能；張凱麗（1991-），女，山東濰坊人，碩士，研究方向：物流工程、物流優(yōu)化及信息化。