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

丁 一， 陳 婷

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

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

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

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

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

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

1 問題描述

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

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

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

圖2 AGV工藝流程圖

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

2.1 AGV的可用性

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

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

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

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

圖3 基于時(shí)間的窗口滾動(dòng)示意

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

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

2) AGV完成最后的訂單。

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

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

3 模型建立

3.1 符號(hào)說明

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

3.2 調(diào)度模型

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

目標(biāo)函數(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 符號(hào)定義

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

4 案例分析

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

表2 AGV參數(shù)設(shè)定

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

表3 任務(wù)屬性表

表4 運(yùn)行結(jié)果對(duì)比

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

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

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

圖4 單載 AGV 與多載 AGV對(duì)比

5 結(jié)束語

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