跨層穿梭車雙提升機系統(tǒng)多目標問題優(yōu)化

李軍濤，胡啟賢，劉朋飛，郭文文

(上海海洋大學工程學院，上海 201306)

0 引言

近年,隨著電商物流的快速發(fā)展,密集型倉儲系統(tǒng)受到眾多復雜性因素制約,如:訂單的小批量多批次的特性、倉儲系統(tǒng)的能耗、車輛的調(diào)度、市場上的競爭者所身處的市場經(jīng)濟和社會政治形勢環(huán)境等。密集型倉儲系統(tǒng)變得越來越復雜，使用自動化傳統(tǒng)的立體倉庫無法高效地解決密集型倉儲系統(tǒng)中遇到的各種問題。跨層穿梭車雙提升機系統(tǒng)[1]是近年來出現(xiàn)的一種新型智能密集型存儲立體倉庫。相比于每層一輛車的多層穿梭車系統(tǒng)，跨層穿梭車可以通過換層提升機到其他層進行入庫，從而減少穿梭車的數(shù)量，具有更高的柔性和魯棒性。同時政府對能耗也提出了更高的要求，在確保訂單快速、準確入庫的同時也需兼顧系統(tǒng)的能耗。

目前，國內(nèi)外學者對于穿梭車系統(tǒng)調(diào)度問題進行了研究。Kuo等[2]以時間最小為目標對多層穿梭車進行了研究，并針對系統(tǒng)中車輛和提升機等待時間的問題，提出了M/G/V和M/G/L排隊模型。Roy等[3]提出了一種半開環(huán)排隊網(wǎng)絡(luò)，以研究機架配置、區(qū)域資源分配和車輛分配規(guī)則的影響。Yang等[4]從分析模型的角度驗證了共享存儲下運行模式的優(yōu)越性，提出了一種求解大型問題的變鄰域搜索算法，研究了不同參數(shù)對計算效率的影響。Zou等[5]構(gòu)造了一個fork-join排隊網(wǎng)絡(luò)來研究穿梭車系統(tǒng)的并行處理策略的性能。Carlo等[6]對同一軌道的雙提升機系統(tǒng)進行研究，以最短出入庫時間為目標函數(shù)建立模型，確定了提升機的工作順序。牟善棟[7]對多層穿梭車系統(tǒng)進行了研究,以出庫時間最短建立模型，通過非支配遺傳算法對模型進行了求解。王珊珊[8]對由單提升機和單穿梭車組成的跨層穿梭車系統(tǒng)進行研究，以出入庫總時間最小建立路徑優(yōu)化模型，并使用改進的離散粒子群優(yōu)化算法對其求解。于巧玉等[9]為降低任務(wù)超時率，將任務(wù)出庫期限引入穿梭車系統(tǒng)任務(wù)調(diào)度模型中，使用雙層智能優(yōu)化算法對模型進行求解。國內(nèi)外對跨層穿梭車雙提升系統(tǒng)的相關(guān)文獻較少，且研究多是以系統(tǒng)作業(yè)時間最短為優(yōu)化目標，缺乏對其他因素的考慮，對跨層穿梭車雙提升機系統(tǒng)調(diào)度有著一定的局限性。

對于調(diào)度中能耗的問題，韓星[10]通過分析穿梭車和提升機運動時的能耗，建立了穿梭車和提升機的速度和加速度的優(yōu)化模型。Banu等[11]開發(fā)了一個基于穿梭車模型的分析工具，可以估計提升機和穿梭車時間的平均值和方差，以及預測每筆交易的平均能耗和能量再生量。Habibi等[12]針對雙梭式穿梭車調(diào)度問題，構(gòu)造穿梭車總成本和能耗目標模型，并提出一種改進的雙層協(xié)同進化優(yōu)化算法(MCoBRA)進行求解。敏感性分析表明在上層考慮基于類的存儲策略對整個目標函數(shù)有顯著影響。Liu等[13]考慮到能耗問題，建立了雙指令周期的交叉穿梭車立體倉庫系統(tǒng)模型，并對其最大吞吐量、行程時間和能量消耗進行了估算，分析了吞吐量與能耗的關(guān)系。劉紫薇[14]以出庫作業(yè)時的能耗為目標建立多層穿梭車調(diào)度模型，利用改進粒子群算法對模型進行求解。在穿梭車能耗問題上，國內(nèi)外多以能耗單目標建立模型，未能同時考慮作業(yè)時間，影響系統(tǒng)作業(yè)效率。

跨層穿梭車雙提升機調(diào)度問題屬于NP-hard問題[15]。國內(nèi)外對于穿梭車系統(tǒng)同時考慮綜合能耗與時間的相關(guān)文獻較少，將能耗目標引入跨層穿梭車雙提升機系統(tǒng)調(diào)度中，建立時間與能耗雙目標最優(yōu)的作業(yè)模型，運用自適應(yīng)遺傳模擬退火算法對該模型求解，通過對比實驗，證明了模型和算法的有效性。

1 跨層穿梭車雙提升機倉儲系統(tǒng)建模

1.1 問題描述

圖1 跨層穿梭車雙提升機系統(tǒng)貨架立面圖Fig.1 Shelf elevation of tier-to-tier multi-shuttle warehouse system with double lifts

跨層穿梭車雙提升機系統(tǒng)由貨架、直線穿梭車、貨物提升機、換層提升機、輥道等組成。其中直線穿梭車在貨架上水平移動,負責貨物的搬運和存取。貨物提升機和換層提升機位于巷道的兩端，分別負責貨物的垂直運動和穿梭車的換層運動[16]。系統(tǒng)立面圖如圖1所示。

該系統(tǒng)采用穿梭車和提升機協(xié)同作業(yè)，首先貨物提升機將貨物從站臺送至入庫所在層，然后穿梭車將貨物送至指定貨位，完成一次任務(wù)入庫。入庫流程圖如圖2所示。

定義1N={(1,s1),(2,s2)…(i,si)…(n,sn)}為入庫任務(wù)集合，i為入庫任務(wù)序號，si=(xi,yi)為入庫任務(wù)i坐標。R={1,2…j…r}為一個巷道中穿梭車的集合，j為穿梭車編號。本文以入庫任務(wù)排序為例，研究跨層穿梭車雙提升機系統(tǒng)任務(wù)調(diào)度。

圖2 入庫流程圖Fig.2 Flow chart of storage

條件假設(shè)為：1)本研究只考慮一個巷道；2)每個任務(wù)只能由一輛穿梭車執(zhí)行，每個車只能執(zhí)行一個任務(wù)；3)穿梭車的初始位置在巷道首端，提升機初始位置在貨架最底層；4)任務(wù)請求小車的時刻為任務(wù)到達I/O處，即前一任務(wù)乘坐貨物提升機的時刻；5)入庫所在層沒有穿梭車時，優(yōu)先請求離入庫所在層最近的空閑穿梭車，若有多輛穿梭車距離入庫所在層最近，則選擇編號最小的穿梭車；6)穿梭車移動到巷道首端后，申請貨物提升機；穿梭車移動到巷道末端后，申請換層提升機；7)兩種提升機的調(diào)度遵循FCFS原則——先到先服務(wù)原則，若多輛穿梭車同時申請，則優(yōu)先響應(yīng)編號最小的穿梭車；8)每層至多有一輛穿梭車，以免發(fā)生碰撞和死鎖；9)不考慮貨物的重量對速度和加速度的影響。

1.2 作業(yè)時間分析

1.2.1 入庫作業(yè)流程分析

考慮到穿梭車初始位置與入庫貨位可能不在同一層，可以根據(jù)入庫任務(wù)層是否有穿梭車分為跨層入庫和不跨層入庫兩種情況，入庫作業(yè)示意圖如圖3，橫軸為貨架的列，縱軸為貨架的層。

圖3 入庫作業(yè)示意圖Fig.3 Schematic diagram of storage

穿梭車j(j=1,2,…,r)執(zhí)行任務(wù)i(i=1,2,…,n)，當yi=yj時，不跨層入庫，需要經(jīng)過3個節(jié)點變化：

1)穿梭車j由穿梭車所在位置節(jié)點移動至入庫層巷道首端節(jié)點，時間為tstj：

(1)

2)貨物提升機由I/O節(jié)點移動至入庫層巷道首端節(jié)點，時間為sti：

(2)

3)穿梭車j由入庫層巷道首端節(jié)點移動至入庫貨位節(jié)點，時間為reti：

(3)

穿梭車j執(zhí)行任務(wù)i不跨層入庫時所用時間為Dtij：

Dtij=tstj+sti+swtij+reti+2srt

(4)

其中，swtij為穿梭車j執(zhí)行任務(wù)i等待貨物提升機響應(yīng)的時間。srt為穿梭車取/放貨物的時間。

當yi≠yj時，需要經(jīng)過6個節(jié)點變化：

1)穿梭車j由穿梭車所在位置節(jié)點移動至巷道末端節(jié)點，時間為tctj：

(5)

2)換層提升機由上次換層節(jié)點移動至穿梭車j所在層節(jié)點，時間為wtjk：

(6)

3)換層提升機由穿梭車j所在層巷道末端節(jié)點移動至入庫層巷道末端節(jié)點，時間為ctij：

(7)

4)穿梭車j由巷道末端節(jié)點移動至巷道首端節(jié)點；為固定時間tH：

(8)

5)貨物提升機由I/O節(jié)點移動至入庫層巷道首端節(jié)點，時間為sti。

6)穿梭車j由入庫層巷道首端節(jié)點移動至入庫貨位節(jié)點，時間為reti。

穿梭車j執(zhí)行任務(wù)i跨層入庫時所用時間為Ctijk：

Ctijk=tctj+cwtij+wtjk+ctij+2set+tH+sti+reti+2srt

(9)

其中，cwtij為穿梭車j執(zhí)行任務(wù)i等待換層提升機響應(yīng)的時間，set為換層提升機裝載或者卸載穿梭車的時間。

根據(jù)穿梭車跨層入庫和不跨層入庫兩種作業(yè)方式，建立穿梭車j完成入庫任務(wù)所需時間的數(shù)學模型Tj：

(10)

其中,

θij={0,1}i=1,2,3…,n；j=1,2,3,…,r

(11)

δij={0,1}i=1,2,3…,n；j=1,2,3,…,r

(12)

公式(10)中θij和δij為決策變量，當穿梭車j執(zhí)行任務(wù)i時，θij為1，否則為0；當穿梭車j執(zhí)行任務(wù)i需跨層時δij為1，否則為0。

圖4 穿梭車和提升機的配合作業(yè)圖Fig.4 Working diagram of shuttle and lift

在跨層穿梭車雙提升機系統(tǒng)中，穿梭車為并行作業(yè)模型，因此整個任務(wù)的入庫時間為完成時間最大的穿梭車的工作時間。建立入庫總時間模型：

F(t)=max(Tj)

(13)

1.2.2 等待時間分析

提升機調(diào)度服從FCFS原則，當穿梭車申請?zhí)嵘龣C時，如果提升機的上一個任務(wù)未完成，則穿梭車需等待提升機響應(yīng)。根據(jù)提升機類型不同，可以將穿梭車j(j=1,2,…,r)執(zhí)行任務(wù)i(i=2,3,…,n)等待的時間分為等待貨物提升機的時間swtij和等待換層提升機的時間cwtij：

(14)

(15)

1.3 能耗分析

1.3.1 穿梭車能耗

當穿梭車加速運動時，牽引力和功率分別為Ft和Pt：

Ft=mgCr+maxfr

(16)

(17)

當穿梭車減速運動時，牽引力和功率分別為Fb和Pb：

Fb=maxfr-mgCr

(18)

(19)

當穿梭車勻速運動時牽引力和功率分別為Fc和Pc：

Fc=mgCr

(20)

(21)

根據(jù)公式(1)、(3)、(5)、(8)分別可以得出：

由原來位置到巷道首端的能耗tswj為

(22)

由巷道口到貨位的能耗rewi為

(23)

由原來位置到巷道末端的能耗tcwj為

(24)

由巷道首端到末端的能耗wH為

wH=t1Pt+t1Pb+(tH-2t1)Pc

(25)

其中，t1為穿梭車由靜止到最大速度的時間。

穿梭車j能耗為

(26)

其中，

Dwij=tswj+rewi

(27)

Cwij=tcwj+wH+rewi

(28)

1.3.2 提升機能耗

(29)

(30)

(31)

(32)

(33)

(34)

根據(jù)公式(2)、(6)、(7)分別可以得出：

貨物提升機由I/O節(jié)點移動至入庫層巷道首端的能耗swi為

(35)

換層提升機由上次換層節(jié)點移動至穿梭車j所在層的能耗wwjk為

(36)

換層提升機由穿梭車j所在層節(jié)點移動至入庫層巷道末端節(jié)點的能耗cwij為

(37)

其中，t2為提升機由靜止到最大速度的時間。

貨物提升機的能耗為

(38)

換層提升機的能耗為

(39)

總能耗模型為

(40)

1.4 目標函數(shù)統(tǒng)一量綱

研究采用模糊數(shù)學方法對總時間函數(shù)F(t)和總能耗函數(shù)F(w)去標量化，并根據(jù)能耗和時間的重要程度賦予權(quán)重，將作業(yè)時間和系統(tǒng)能耗雙目標模型轉(zhuǎn)化成單目標模型。總目標函數(shù)Z為

(41)

約束條件為

(42)

(43)

(44)

其中，φ為權(quán)重系數(shù)，0≤φ≤1，可根據(jù)物流企業(yè)對入庫效率和節(jié)能減排的重視程度對φ取值，若企業(yè)追求效率則取較大的權(quán)重值φ；反之，若企業(yè)追求環(huán)保，則取較小的權(quán)重。本文根據(jù)中國出臺的節(jié)能減排的政策方針[17]，取權(quán)重值φ=0.3。

公式(42)表示每個入庫任務(wù)只能由一輛穿梭車執(zhí)行，入庫任務(wù)對應(yīng)的穿梭車編號唯一。公式(43)表示模型總?cè)霂鞎r間不能小于提升機連續(xù)工作時間。公式(44)表示在執(zhí)行跨層入庫時，請求換層的時間早于請求貨物提升機，且兩次申請的時間間隔不得小于換層所用的時間。

2 算法設(shè)計

處理NP-hard問題常用的算法有遺傳算法、蟻群算法、模擬退火算法等[18]。遺傳算法(GA)作為求解優(yōu)化問題的有效算法，它們是基于“達爾文適者生存理論”推導出來的隨機搜索算法，在選擇、交叉和變異等生物進化機制的引導下，以自適應(yīng)的方式探索一個龐大而復雜的搜索空間[19]。遺傳算法具有全局搜索能力強，魯棒性強的特點[20]，但也存在算法早熟的缺點。當問題復雜時，還有計算時間長等缺陷。為了彌補遺傳算法早熟的缺點，本文將模擬退火算法與自適應(yīng)遺傳算法相結(jié)合,設(shè)計自適應(yīng)遺傳模擬退火算法,既避免了遺傳算法早熟的缺點,又改善了模擬退火算法容易陷入局部最優(yōu)的弱項。

算法設(shè)計規(guī)則為：

1)編碼：采用自然數(shù)編碼方式，入庫任務(wù)編號為編碼序號。

2)自適應(yīng)變異率PMi和自適應(yīng)交叉率PCi分別為[21]：

(45)

(46)

其中，PMmax為最大變異概率，PMmin為最小變異概率，PCmax為最大交叉概率，PCmin為最小交叉概率，F(xiàn)i為適應(yīng)度，F(xiàn)max為最大適應(yīng)度，F(xiàn)min為最小適應(yīng)度，e為一個很小的正實數(shù)，防止分母為0。

3)適應(yīng)度函數(shù)：

Fi=1/Zi

(47)

5)跨層穿梭車雙提升機調(diào)度模型的自適應(yīng)遺傳模擬退火算法步驟:

步驟1：初始化種群和參數(shù)；

步驟2：開始迭代。執(zhí)行選擇、變異、交叉操作；

步驟3：計算適應(yīng)度值，更新并記錄最優(yōu)解；

步驟4：取最優(yōu)解S1。對當前解進行隨機干擾，產(chǎn)生新的解S2，若滿足S2

步驟5：判斷λ是否小于P，若滿足，則替換舊個體且按衰減函數(shù)更新溫度，否則不替換舊個體，且更新溫度；

步驟6：判斷是否達到最大迭代次數(shù)，若達到輸出最優(yōu)解，否則轉(zhuǎn)到步驟2。

3 算例分析

為了驗證所提出的模型及求解方法的有效性，本文根據(jù)實際中跨層穿梭車系統(tǒng)的性能參數(shù)和儲存規(guī)格，設(shè)置了跨層穿梭車雙提升機系統(tǒng)的模擬場景，貨架層數(shù)為12層，每層有40列貨格，穿梭車4輛，具體設(shè)備運行參數(shù)如表1所示。

表1 設(shè)備運行參數(shù)Tab.1 Operation parameters of equipment

隨機生成50個入庫任務(wù)，入庫任務(wù)表如表2所示。

3.1 算法有效性驗證

根據(jù)程序隨機得到入庫任務(wù)的一組序列為：9→26→38→43→34→33→35→40→25→11→18→36→46→29→13→45→27→8→3→22→10→31→5→50→2→19→44→39→7→12→6→24→48→30→1→23→14→28→17→20→37→16→4→27→49→47→42→41→32→15。目標函數(shù)值為0.636 5，作業(yè)總時間為943.8s，作業(yè)總能耗為1 733.5KJ。

表2 入庫任務(wù)表Tab.2 Storage task table

圖5 算法收斂效果比較圖Fig.5 Comparison of convergence between two algorithms

通過使用遺傳算法和自適應(yīng)遺傳模擬退火算法分別對模型入庫作業(yè)調(diào)度進行對比，來驗證算法求解該問題的有效性。遺傳算法參數(shù)為：種群數(shù)量取500，迭代次數(shù)1 000，交叉概率PM取0.7，選用部分匹配交叉，變異概率PC取0.1，選用交換變異。優(yōu)化后所得到的入庫任務(wù)序列為：44→20→38→42→5→11→35→13→19→40→12→18→48→50→33→2→26→15→8→31→4→29→22→41→3→32→16→43→21→45→24→1→39→25→49→46→27→34→28→9→6→17→37→47→36→7→30→10→14→23。目標函數(shù)值為0.351 3，作業(yè)總時間為822.7s，作業(yè)總能耗為1 520.3KJ。自適應(yīng)遺傳模擬退火算法的參數(shù)為：種群數(shù)量取500，迭代次數(shù)1 000，最大交叉概率PCmax取0.9，最小交叉概率PCmin取0.8，最大變異概率PMmax取0.05，最小變異概率PMmin取0.01,模擬退火的初始溫度取2 000℃，終止溫度取20 ℃，冷卻系數(shù)取0.95。優(yōu)化后所得到的入庫任務(wù)序列為：6→39→33→47→45→11→26→27→50→46→8→23→10→31→48→3→28→38→35→2→25→21→29→34→32→1→37→15→13→49→40→30→14→24→17→16→5→22→7→41→43→20→18→36→44→19→42→4→9→12。目標函數(shù)值為0.218，作業(yè)總時間為627.8s，作業(yè)總能耗為1 251.4KJ。算法結(jié)果如表3所示，算法收斂效果比較圖如圖5所示。

由表3可知，自適應(yīng)遺傳模擬退火算法比傳統(tǒng)的遺傳算法求解精度高，對時間和能耗的優(yōu)化效率也更好。跨層穿梭車入庫作業(yè)的時間主要優(yōu)化時間是穿梭車等待貨物請求時間，即穿梭車空閑時間，自適應(yīng)遺傳模擬退火算法對穿梭車空閑時間大幅度優(yōu)化，對穿梭車等待兩種提升機時間也有所優(yōu)化。

從圖5中可以看出遺傳算法收斂較慢，求解精度差；而本文提出的自適應(yīng)遺傳模擬退火算法，引入了自適應(yīng)變異率和自適應(yīng)交叉率，并通過模擬退火對解進行干擾，獲得更優(yōu)的解，相比于遺傳算法，其求解收斂快、精度優(yōu)勢較大。故可以證明本文所提出的算法求解該問題的有效性。

3.2 參數(shù)靈敏度分析

為了分析模型中各參數(shù)變化對模型的影響，以初始值為基準，令各參數(shù)逐漸增加(減少)10%,20%,30%,40%。

通過表4、表5可以看出增加穿梭車或提升機的最大速度，總目標函數(shù)變化不大，總時間減少，總能耗增加。其中提升機速度的增加對時間和能耗的影響更為顯著。

通過表6、表7可以看出增加穿梭車或提升機的加速度，都會使總時間減少，但隨著穿梭車加速度增加，總能耗增加，總目標函數(shù)變化不大，而隨著提升機加速度增加，總能耗減少，總目標函數(shù)也出現(xiàn)變小的趨勢。

表4 穿梭車最大速度分析Tab.4 Sensitivity analysis of maximum speed of shuttle

表6 穿梭車加速度分析Tab.6 Sensitivity analysis of acceleration of shuttle

表5 提升機最大速度分析Tab.5 Sensitivity analysis of maximum speed of lift

表7 提升機加速度分析Tab.7 Sensitivity analysis of acceleration of lift

4 結(jié)語

針對跨層穿梭車雙提升機系統(tǒng)任務(wù)入庫問題,分析其作業(yè)流程,建立了作業(yè)時間和系統(tǒng)能耗的雙目標模型。采用自適應(yīng)遺傳模擬退火算法對模型進行求解,實驗結(jié)果表明,所建立的調(diào)度數(shù)學模型及自適應(yīng)遺傳模擬退火算法是可行有效的，在一定程度上能夠減少作業(yè)時間和能耗，提高系統(tǒng)效率，對于企業(yè)來說，一方面提高了穿梭車雙提升機系統(tǒng)的效率，另一方面又能減少能量消耗，降低成本。同時分析了穿梭車、提升機的速度、加速度與系統(tǒng)時間和能耗之間的關(guān)系，改變穿梭車的速度或加速度對總目標函數(shù)的影響不大，增加穿梭車的速度或加速度時，會導致總時間減少，總能耗增加。而增加提升機加速時，導致總時間和總能耗都減少，目標函數(shù)隨之減小。可以通過適當增加提升機加速度來使總時間和總能耗減少。為跨層穿梭車系統(tǒng)的研究和應(yīng)用提供了借鑒意義。

但本文研究所建立模型仍然具有一定程度局限性，本文只考慮任務(wù)排序，未考慮給穿梭車分配任務(wù)，導致會出現(xiàn)穿梭車效率差距過大，部分穿梭車閑置時間過長等問題，未來將對穿梭車任務(wù)分配進行研究。