基于滾動時域優(yōu)化策略的多載AGV充電調(diào)度

丁 一， 陳 婷

(上海海事大學 物流科學與工程研究院， 上海 201306)

近年來，隨著全球貿(mào)易量不斷增長，集裝箱運輸?shù)氖袌鲂枨笾饾u增多。港口運營商不僅要面對集裝箱吞吐量不斷增長的壓力，而且要面對降低集裝箱港口運營成本的壓力。目前，各大自動化集裝箱碼頭均已使用以電能為動力源的自動導引運輸車(Automated Guided Vehicle, AGV)。SCHMIDT等[1]結(jié)合集裝箱碼頭的大型電力項目數(shù)據(jù)，分析在集裝箱碼頭運營中采用以電池為動力源的AGV的商業(yè)可行性，實例驗證結(jié)果表明：該方式可使碼頭運營商節(jié)省10%以上的總支出。

越來越多的學者對多載AGV進行研究，這反映了多載AGV在碼頭應用的廣泛性和多載AGV相比單載AGV的優(yōu)越性。電力驅(qū)動的AGV本質(zhì)上是無人駕駛的電動汽車，由計算機控制系統(tǒng)控制，與港口岸橋和場橋等其他設備協(xié)同調(diào)度。集裝箱港口的控制系統(tǒng)復雜多變，有許多不可控的因素，如設備故障和設備延遲等。總體來說，在港口對多載AGV進行調(diào)度是一個非確定性多項式難題(Non-Deterministic Polynomial Hard, NP-Hard)，對在確定環(huán)境下建立的模型進行優(yōu)化計算所得結(jié)果可能無法適應港口真實復雜的環(huán)境。

多載AGV存在運輸任務難以確定、交付地點難以選擇、裝載調(diào)度復雜和負載選擇多變等困難，其調(diào)度比單載AGV更復雜。HO等[2-3]在不同的情境下對9種裝載規(guī)則進行對比分析，結(jié)合卸載規(guī)則，通過數(shù)值分析求解出最優(yōu)規(guī)則組合。霍凱歌等[4-5]從作業(yè)費用、完成時間和空載率等方面對多載AGV和單載AGV進行對比分析，采用遺傳算法驗證多載AGV不僅能提升自動化集裝箱碼頭的作業(yè)效率，還能減輕交通擁堵的情況。CHAWLA等[6]使用模因-粒子群組合算法縮短多載AGV的最短完成時間和最短等待時間，在不同規(guī)模的試驗中有效地解決多載AGV的調(diào)度問題。

GRUNOW等[7-8]考慮到多載AGV在自動化集裝箱港口的工作環(huán)境和自身調(diào)度的動態(tài)性，利用車輛的有效性提出一種基于優(yōu)先權(quán)的調(diào)度算法，將多載AGV裝載狀態(tài)分為AGV完全可用、AGV部分可用和AGV不可用等3種狀態(tài)，通過建立混合整數(shù)規(guī)劃(Mixed Integer Linear Programming,MILP)模型驗證基于滾動時域的優(yōu)先權(quán)調(diào)度算法的有效性。KLERIDES等[9]提出對多載AGV執(zhí)行滾動時域，既可使用于調(diào)度的信息在一定的時間間隔內(nèi)更新，又能執(zhí)行新的調(diào)度方案，對該方法在不同規(guī)模的港口中進行實例分析，驗證滾動時域的方法能使多載AGV快速適應復雜且動態(tài)的工作環(huán)境。劉國寶等[10]采用改進的滾動時域優(yōu)化策略驗證動態(tài)調(diào)度方法的有效性。宋李俊等[11]基于滾動時域優(yōu)化框架，設計出適于在故障情況下應用的周期與事件混合驅(qū)動的動態(tài)調(diào)度策略，采用遺傳算法對動態(tài)調(diào)度模型進行求解，通過仿真試驗驗證該策略的可行性和有效性。BIAN等[12]提出一種考慮電池容量約束的事件驅(qū)動分配模型，當事件發(fā)生時，AGV執(zhí)行新的調(diào)度方案，通過與現(xiàn)有的算法相比較，證明這種動態(tài)調(diào)度算法適用于AGV的動態(tài)調(diào)度。

上述研究主要集中在多載AGV運輸任務的確定、交付調(diào)度、裝載調(diào)度和負載選擇等方面，而對多載AGV運輸動態(tài)調(diào)度開展的研究較少，同時未考慮電量、負載等約束條件。本文研究電量約束和負載約束條件下的電力驅(qū)動多載AGV，采用先到先服務(First Come First Service,FCFS)的調(diào)度策略建立MILP模型，在滾動時域框架下，采用周期與事件相結(jié)合的混合驅(qū)動調(diào)度方法，對電力驅(qū)動的多載AGV進行動態(tài)調(diào)度分析。

1 問題描述

自動化集裝箱港口的AGV主要分為裝載20英尺(1英尺≈0.304 8 m)箱的小型AGV和裝載40英尺箱的大型AGV。在傳統(tǒng)單載模式下，任何時刻AGV只需處理1個集裝箱，其尺寸對AGV的作業(yè)效率沒有影響。在多載模式下，AGV必須考慮多個負載和AGV電量、容量的限制，考慮集裝箱尺寸，從而進行有效的調(diào)度已成為必不可少的條件。本文根據(jù)不同尺寸大箱的占比，分析在不同滾動周期下多載AGV的作業(yè)效率，充分發(fā)揮多載AGV的優(yōu)越性。從AGV的角度看，每個任務只需考慮起點和終點，集裝箱卸船作業(yè)和裝船作業(yè)對AGV并沒有本質(zhì)上的區(qū)別,因此只需研究裝船作業(yè)下的AGV調(diào)度。

為便于調(diào)度，本文假設所有AGV最多同時裝載2個20英尺箱。自動化集裝箱碼頭俯瞰圖見圖1。 AGV一旦收到運輸請求，即從充電站出發(fā)開始執(zhí)行運輸任務。有兩個運輸任務的多載AGV工藝流程見圖2。AGV收到運輸請求后立即從充電站出發(fā)，根據(jù)FCFS的裝載調(diào)度規(guī)則確定集裝箱的裝載順序，根據(jù)最短距離的交付規(guī)則確定集裝箱卸載順序。AGV在確定集裝箱的裝載順序之后，會檢查是否有足夠的箱位和電量來完成任務,在箱位和電量充足的情況下完成接下來的運輸任務，若箱位和電量不能同時滿足運輸要求則僅完成當前的任務。

注：①為岸橋；②為碼頭前沿中轉(zhuǎn)平臺；③為AGV運行軌跡；④為AGV小車；⑤進場中轉(zhuǎn)平臺；⑥為場橋

圖2 AGV工藝流程圖

2 混合驅(qū)動的滾動時域優(yōu)化策略

2.1 AGV的可用性

每次發(fā)出調(diào)度請求時，都應對等待運輸?shù)娜蝿蘸涂捎玫腁GV進行重新分配。目前，許多學者都認同GRUNOW等[7]提出的AGV可用性劃分，結(jié)合AGV的容量和電量約束條件，針對即將執(zhí)行的任務分情況分配調(diào)度:若AGV電量滿足且空車，則AGV完全可用；若AGV電量滿足且AGV有剩余箱位，則AGV部分可用。對于AGV不可用的情況，主要有4種情形，即：AGV電量不足且空車；AGV的電量不足但有剩余箱位；AGV的電量不足且AGV沒有剩余箱位；AGV的電量充足但沒有剩余箱位。例如：多載AGV已裝載第1個20英尺的集裝箱，并已通過FCFS的裝載調(diào)度規(guī)則確定第2個20英尺集裝箱的信息，若經(jīng)檢驗滿足AGV電量充足且有剩余箱位的條件，則對于第2個20英尺集裝箱而言，AGV部分可用。

從調(diào)度的角度看，對于即將到達的集裝箱，AGV不可用，但對于下一個即將到達的集裝箱，AGV可能可用。為更好地完成AGV的裝載運輸任務，本文提出基于混合驅(qū)動的滾動時域優(yōu)化的動態(tài)研究方法，該方法將周期與事件的動態(tài)調(diào)度優(yōu)點相結(jié)合，對多載AGV進行更加有利的分配。

2.2 基于混合驅(qū)動的滾動時域優(yōu)化策略

針對自動化集裝箱碼頭多載AGV的動態(tài)調(diào)度問題，主要有周期型調(diào)度策略、事件驅(qū)動型策略和周期與事件相結(jié)合的混合驅(qū)動的滾動時域優(yōu)化策略等3種動態(tài)調(diào)度策略,其中:周期型調(diào)度策略是指系統(tǒng)每隔固定周期進行重新調(diào)度，要求周期的長短與實際相符合;事件驅(qū)動型調(diào)度策略是指通過定義突發(fā)事件來進行重新調(diào)度。本文采用基于周期與事件相結(jié)合的混合驅(qū)動的滾動時域優(yōu)化策略。當發(fā)生定義的突發(fā)事件時，采用事件驅(qū)動調(diào)度，對突發(fā)事件作出快速反應，否則采用周期調(diào)度。該調(diào)度策略既削弱對定義事件的依賴性，又增強滾動優(yōu)化的穩(wěn)定性，以時間作為滾動窗口推動系統(tǒng)不斷更迭。在t時刻按局部調(diào)整并執(zhí)行運輸任務,經(jīng)過滾動周期時間后將已完成的任務移入完工窗口,再從等待運輸?shù)娜蝿罩羞x取時間Δh內(nèi)的任務進入預測窗口,在t+ΔT時刻開始進行周期調(diào)度決策。基于時間的窗口滾動示意見圖3,其中:F(i)為第i個完工窗口;P(i)為預測窗口;W(i)為等待窗口。在預測窗口P(i)中,結(jié)合事件驅(qū)動的調(diào)度進行再調(diào)度。Δh為AGV無法完成本預測窗內(nèi)的訂單時所能接觸到的下一個預測窗內(nèi)任務所在的時間段。

圖3 基于時間的窗口滾動示意

根據(jù)完全可用條件規(guī)則，當事件發(fā)生時，只有AGV的電量和箱位都充足才分配任務給AGV。根據(jù)AGV的狀態(tài)定義3種觸發(fā)事件，即：

1) 在給定的時間窗口出現(xiàn)新的訂單。

2) AGV完成最后的訂單。

3) AGV無法完成本預測窗內(nèi)的訂單，但能完成下一個預測窗內(nèi)的訂單。

當窗口中出現(xiàn)新任務時，需及時調(diào)整AGV的分配，如事件1；當系統(tǒng)中沒有需要運輸?shù)募蝿諘r，AGV不再進行分配，如事件2；事件3可確保AGV能及時更新調(diào)度信息，充分利用AGV的裝載能力。

3 模型建立

3.1 符號說明

無論是裝船還是卸船，都需在時間窗內(nèi)完成。t為預測窗口開始的時間節(jié)點，ΔT為滾動周期。在時間(t,t+ΔT)內(nèi)有m(m∈M)臺AGV完成I個集裝箱的裝卸運輸任務。(i+，i-)為同一集裝箱的裝載與卸載操作。在裝載操作過程中，1個20英尺的集裝箱要占1臺AGV的1個箱位，1個40英尺的集裝箱要占2個箱位；在卸箱操作過程中，卸載1個20英尺的集裝箱，AGV的容量減少1個箱位，卸載1個40英尺的集裝箱，AGV的容量減少2個箱位。具體符號定義見表1。

3.2 調(diào)度模型

以最小化最末任務完成時間為目標，建立自動化集裝箱碼頭多載AGV調(diào)度模型，該模型的目標函數(shù)與約束條件如下:

目標函數(shù) minf

(1)

s.t.f≥zimt, ?i∈I

(2)

xi1i2m(Ei1m+Ei2m)≥max{Ei1m,Ei2m},

?i∈I;m∈M

(3)

(4)

max{zi1mt,zi2mt}≤xi1i2m(zi1mt+zi2mt),

?i∈I;m∈M

(5)

xiim=0, ?i∈I

(6)

xi+i-m=1, ?i+∈I+;i-∈I-

(7)

表1 符號定義

qi2m=di1+di2+N(1-xi1i2m), ?i+∈I+;m∈M

(8)

di≤qim≤Qm, ?i+∈I+

(9)

0≤qim≤Qm+di, ?i+∈I-

(10)

yi1i2mt(Rmt-max{Ei1m,Ei2m}))>R,

?i∈I,m∈M

(11)

yimt=

(12)

xi1i2m∈{0, 1}, ?i∈I

(13)

zimt>0,t>0,f>0, ?i∈I;m∈M

(14)

式(1)為目標函數(shù)，旨在使最末任務完成時總作業(yè)時間最短；式(2)為保證任務順利完成，最末任務的完成時間大于等于任意任務的完成時間；式(3)中，若AGVm執(zhí)行多載操作，且i1的優(yōu)先級高于i2，則總耗費的電量小于等于分別裝載i1和i2耗費的電量；式(4)考慮兩個相繼任務，只能一個任務比另一個任務先執(zhí)行；式(5)為若AGVm執(zhí)行任務i1后立即執(zhí)行任務i2，則到達任務i2卸載的時間小于等于單載運輸?shù)臅r間和；式(6)為任務本身不能成為自身的上一任務；式(7)為對于同一個任務，必須先執(zhí)行裝載操作，再執(zhí)行卸載操作。式(8)～式(10)為AGVm的容量約束，其中:式(9)反映裝載操作的AGVm容量不能超過AGVm的同時所負載的最大容量:式(10)為在卸載操作的AGVm上沒有負載的集裝箱后，也不能繼續(xù)執(zhí)行卸載操作；式(11)為AGVm只有在剩余功率足夠用于完成任務的情況下才能被分配給任務i1和i2；式(12)為決策變量yimt的定義，只有當AGVm的容量和電量同時滿足時才參與分配。式(13)和式(14)為變量的約束條件。

4 案例分析

AGV的相關(guān)參數(shù)設置見表2。在上海港洋山4期自動化集裝箱碼頭停靠的某集裝箱船的裝卸作業(yè)數(shù)據(jù)見表3，由于數(shù)據(jù)量過大，僅列出部分數(shù)據(jù)。表3中：根據(jù)最早時刻的大小，按升序進行任務編號；作業(yè)的4個堆場分別用數(shù)字1、2、3、4表示；2臺橋吊在海側(cè)為該船服務，數(shù)字5、6分別表示2臺橋吊。有10臺AGV進行水平運輸，假設 AGV的安全電量為總電量的10%，可保證AGV從碼頭任意位置返回充電站。

表2 AGV參數(shù)設定

1) 分別以30個任務、60個任務和90個任務為研究對象，對多載運輸進行實例分析，并根據(jù)40英尺箱占比的變化對完成時間、容量利用率和電池利用率進行對比分析。有4輛AGV進行服務，涉及4個堆場和2臺橋吊，ΔT=1 000。運行結(jié)果見表4。由表4可知：當大箱占比30%時，任務量的變化對容量利用率和電池利用率的影響較小。在任務量相同的情況下，大箱占比越少，小箱占比越多，AGV能在越短的時間內(nèi)同時運輸更多的集裝箱，縮短完成時間，AGV的空載時間越短，電池利用率越高。然而，考慮到AGV在不同運輸狀態(tài)下的耗電量和運輸速度存在差異，過多的小箱反而會增加AGV的負荷，達不到降低完成時間、提高電池利用率的效果。結(jié)合實際情況可知：40英尺箱占比約30%是最理想的狀態(tài)。

表3 任務屬性表

表4 運行結(jié)果對比

2) 根據(jù)動態(tài)調(diào)度策略，突發(fā)事件發(fā)生時采用事件驅(qū)動型策略，其余時間采用周期性滾動機制。在周期性滾動機制下，滾動調(diào)度的次數(shù)和系統(tǒng)對動態(tài)因素的適應能力由ΔT決定，故設置不同的滾動周期值分別進行試驗，以驗證ΔT與評價指標的相關(guān)性。不同滾動周期調(diào)度結(jié)果對比見表5。為使試驗結(jié)果更具有說服力，試驗保持在同一情景下進行，取I=10。由表5可知：當周期ΔT=800～1 300 s、滾動次數(shù)為2～4次時，AGV動態(tài)調(diào)度作業(yè)效率最好，目標函數(shù)值達到最優(yōu)，電池利用率較高。對試驗結(jié)果進行分析可知：在滾動時域優(yōu)化調(diào)度策略中，滾動周期的取值影響整體的調(diào)度效率，周期過長時無法對系統(tǒng)中產(chǎn)生的干擾進行快速反應，周期過短則會使重新調(diào)度過于頻繁，導致整體任務完成時間延長，AGV電池利用率也不理想。

表5 不同滾動周期調(diào)度結(jié)果對比

3) 為更好地驗證多載AGV的優(yōu)越性，將多載AGV與單載AGV完成相同任務量所需的時間相對比,結(jié)果見圖4。當任務量為10個時，多載AGV的完成時間與單載AGV相差不大;當任務量增加至300個時，多載AGV的完成時間相比單載AGV明顯減少。這表明，在大多數(shù)情況下，多載AGV能在更短的時間內(nèi)完成任務，從而滿足自動化集裝箱碼頭對提高碼頭水平運輸效率的要求,同時隨著任務量的增加，多載AGV的優(yōu)勢更明顯。

圖4 單載 AGV 與多載 AGV對比

5 結(jié)束語

本文對多載AGV的作業(yè)調(diào)度進行研究，基于滾動時域的優(yōu)化策略建立相應的MILP模型。試驗結(jié)果表明：當40英尺箱占比約30%時，能最大化多載AGV的運輸能力；ΔT的取值會影響作業(yè)效率，需根據(jù)實際情況對ΔT進行合理取值，在40英尺箱占比相同的情況下，任務量越多，多載AGV的效率越高。目前，多載AGV在港口水平運輸中的占比越來越大，對多載AGV進行充電調(diào)度研究有利于提高其工作效率。本文的研究結(jié)果可供碼頭多載AGV充電調(diào)度參考，以便碼頭對多載AGV進行調(diào)度管理，提高港口水平運輸設備的整體作業(yè)效率。但是，該研究并未考慮AGV在充電站的等待時間和AGV的數(shù)量差異等因素，這些將在未來做進一步的研究。