考慮充電和等待時(shí)間的集裝箱碼頭AGV調(diào)度

周小凡 萇道方 余芳 高銀萍

摘要：為提高自動(dòng)化集裝箱碼頭自動(dòng)導(dǎo)引小車（automated guided vehicle，AGV）作業(yè)效率和利用率，考慮AGV的電量續(xù)航能力和重空載的耗電差異，在AGV任務(wù)選擇時(shí)綜合考慮任務(wù)距離和各任務(wù)緊急程度，并設(shè)置AGV充電結(jié)束條件以減少AGV排隊(duì)等待的時(shí)間，建立以最小化

完成任務(wù)總時(shí)間為目標(biāo)的AGV調(diào)度模型。用Java進(jìn)行實(shí)例求解。結(jié)果表明，對(duì)AGV采用多頻次充電并將其允許工作電量百分比設(shè)定為71%時(shí)，完成任務(wù)總時(shí)間最短，耗電量最小，且AGV利用率較高。

關(guān)鍵詞：自動(dòng)化集裝箱碼頭; 自動(dòng)導(dǎo)引小車（AGV）; 充電調(diào)度; 充電特性; 等待時(shí)間

中圖分類號(hào)： U691.3

文獻(xiàn)標(biāo)志碼： A

Abstract： In order to improve the work efficiency and utilization rate of AGVs （automated guided vehicles） in automated container terminals， an AGV scheduling model with the objective of minimizing the total task completion time is established. In the model， the AGVs power continuation ability and the difference of power consumption between heavy and empty conditions are considered， the task distance and the emergency degree of each task when AGV task selection are taken into account comprehensively， and the charging end condition of AGV is set to reduce the waiting time of AGVs.An example is solved by Java. The results show that， when AGVs are charged with multi-frequency and the allowable working power percentage is set to 71%， both the total task completion time and the power consumption are the least， and the utilization rate of AGVs is higher.

0 引 言

隨著全球經(jīng)濟(jì)的快速發(fā)展，自動(dòng)化集裝箱碼頭發(fā)展迅猛。為提高集裝箱碼頭的自動(dòng)化作業(yè)效率，各種自動(dòng)化設(shè)備和技術(shù)被引入碼頭實(shí)際操作中，其中自動(dòng)導(dǎo)引小車（automated guided vehicle，AGV）作為自動(dòng)化集裝箱碼頭的重要組成部分，已被廣泛應(yīng)用到碼頭水平作業(yè)中。目前，自動(dòng)化集裝箱碼頭的AGV多采用純電力驅(qū)動(dòng)，具有節(jié)能環(huán)保、智能導(dǎo)航、成本較低等優(yōu)勢(shì)[1]。在實(shí)際作業(yè)中，為保證AGV連續(xù)工作以完成裝卸任務(wù)，需要及時(shí)為AGV充電。同時(shí)，AGV在重載和空載行駛過(guò)程中耗電量不同[2]。因此，本文對(duì)考慮充電和等待時(shí)間的集裝箱碼頭AGV調(diào)度問(wèn)題進(jìn)行研究。

針對(duì)自動(dòng)化集裝箱碼頭水平運(yùn)輸問(wèn)題，大部分學(xué)者主要對(duì)路徑規(guī)劃和車輛調(diào)度進(jìn)行研究來(lái)提升作業(yè)效率。荀燕琴[3]提出基于差分算法的蟻群算法研究AGV的路徑規(guī)劃;LI等[4]提出人造魚算法對(duì)AGV進(jìn)行路徑規(guī)劃;韓曉龍等[5]在不同調(diào)度策略下，對(duì)AGV進(jìn)行調(diào)度配置仿真，尋求最優(yōu)調(diào)度配置策略;CONFESSORE等[6]將 AGV 調(diào)度問(wèn)題轉(zhuǎn)化成最小流問(wèn)題，建立最小流型，利用貪婪算法和單純形算法求解，結(jié)果表明，改進(jìn)后的單純形算法對(duì)最小化完成任務(wù)的平均時(shí)間和最大化AGV利用程度有顯著效果;ANGELOUDIS等[7]提出對(duì)AGV進(jìn)行實(shí)時(shí)控制的調(diào)度方法，并得出該方法優(yōu)于啟發(fā)式算法的結(jié)論;泰應(yīng)鵬等[8]利用A*算法啟發(fā)式地為多個(gè)AGV規(guī)劃路徑，解決多AGV在路徑規(guī)劃中的碰撞沖突問(wèn)題;梁承姬等[9]提出一種基于路段時(shí)間窗的AGV路徑規(guī)劃方法，有效實(shí)現(xiàn)了AGV的避碰;劉二輝等[10]提出一種用于求解復(fù)雜環(huán)境下AGV 路徑規(guī)劃問(wèn)題的改進(jìn)灰狼優(yōu)化算法，并引入路徑微調(diào)算子和鄰域變異算子。查閱大量文獻(xiàn)發(fā)現(xiàn)，現(xiàn)有論文針對(duì)AGV調(diào)度考慮充電的較少，相關(guān)論文的主要研究?jī)?nèi)容如下：張劍韜等[11]研究了非接觸式無(wú)線充電技術(shù)在AGV中的應(yīng)用;HUANG等[12]設(shè)計(jì)了非接觸式AGV充電系統(tǒng)，該系統(tǒng)中AGV具有應(yīng)用雙輸出功能，AGV沿軌道移動(dòng)時(shí)可進(jìn)行充電;LI[13]考慮了電量約束下的車輛路徑優(yōu)化問(wèn)題;FATNASSI等[14]提出具有電池約束的AGV調(diào)度問(wèn)題;傅正堂等[2]考慮了AGV重空載耗電差異，尋求最短總路徑;張亞琦等[15]給出了AGV充電與作業(yè)集成調(diào)度的混合整數(shù)規(guī)劃模型，考慮充電過(guò)程對(duì)AGV實(shí)際作業(yè)的影響，分析AGV數(shù)量對(duì)運(yùn)輸時(shí)間的影響。綜上可知，大多研究主要針對(duì)AGV的充電技術(shù)，對(duì)影響AGV充電調(diào)度的因素考慮較為單一，對(duì)AGV充電調(diào)度的研究還不完善，如對(duì)AGV的充電規(guī)則及充電等待問(wèn)題的研究較少?？傮w上，本文考慮AGV的電量續(xù)航能力和重空載耗電差異，根據(jù)AGV到達(dá)剩余各任務(wù)起點(diǎn)的執(zhí)行時(shí)間與各任務(wù)優(yōu)先級(jí)的加權(quán)值進(jìn)行任務(wù)選擇，設(shè)置AGV充電結(jié)束條件，考慮多頻次充電，縮短AGV充電等待時(shí)間，尋求約束條件下的最短完成任務(wù)總時(shí)間。

1 問(wèn)題描述

某自動(dòng)化集裝箱碼頭在某時(shí)段需完成一定數(shù)量的集裝箱卸船任務(wù)，其中利用AGV將集裝箱從各岸橋緩存區(qū)送至對(duì)應(yīng)的場(chǎng)橋緩存區(qū)。本文考慮AGV的電量續(xù)航能力和重空載耗電差異，對(duì)正充電的AGV設(shè)定一個(gè)允許工作電量百分比PU，當(dāng)其充電量達(dá)到PU且有其他AGV等待充電時(shí)，就斷開(kāi)充電電源投入工作，減少其他AGV的充電等待時(shí)間。港口實(shí)際作業(yè)任務(wù)的緊急情況依據(jù)貨主需要集裝箱離港的時(shí)間而定，本文將需要在3天內(nèi)完成的集裝箱離港任務(wù)按緊急程度劃分為1、2、3級(jí)任務(wù)，分別代表最緊急、較緊急和不緊急任務(wù);AGV不與岸橋綁定，AGV在進(jìn)行任務(wù)選擇的同時(shí)考慮AGV到達(dá)剩余各任務(wù)起點(diǎn)的執(zhí)行時(shí)間和各任務(wù)緊急程度，對(duì)這2個(gè)量進(jìn)行無(wú)量綱化處理后，分別賦予權(quán)重因子α和β，選擇二者加權(quán)值最小的任務(wù)，以此完成所有卸箱任務(wù)。

圖1中：AGV按照任務(wù)選擇原則選擇任務(wù)1后，前往任務(wù)1起點(diǎn)岸橋緩存區(qū)進(jìn)行裝箱，然后沿最短路徑到達(dá)任務(wù)1終點(diǎn)場(chǎng)橋緩存區(qū)進(jìn)行卸箱;完成任務(wù)1后，再按照任務(wù)選擇原則選擇任務(wù)2，先判斷AGV剩余電量是否能使其完成任務(wù)2并返回充電站，若能則去執(zhí)行任務(wù)2，否則去充電站進(jìn)行充電。AGV到達(dá)充電站時(shí)，若有空閑充電樁則直接進(jìn)行充電，否則等待其他正充電的AGV的電量達(dá)到PU后再開(kāi)始充電。若充電站無(wú)AGV等待充電，則正充電的AGV電量達(dá)到PU后將繼續(xù)充電直至有其他AGV前來(lái)充電或該AGV電已充滿才斷開(kāi)充電電源進(jìn)入工作狀態(tài)。

為完成所有集裝箱裝卸任務(wù)，AGV需要進(jìn)行任務(wù)選擇并判斷是否需要充電，圖2為AGV充電調(diào)度仿真流程。

2 模型建立

2.1 符號(hào)定義

K為任務(wù)集合，k∈K;L為充電站集合，l∈L;V為AGV集合，v∈V;PL為AGV需要進(jìn)行充電的最低電量;Zk為任務(wù)k的緊急程度等級(jí);Bk為任務(wù)k的起點(diǎn);Ek為任務(wù)k的終點(diǎn);Ui，j和Hi，j分別為AGV從位置i至位置j的執(zhí)行時(shí)間和消耗的電量;Gvk（t）為決策變量，表示AGV v在時(shí)刻t執(zhí)行待完成任務(wù)k所對(duì)應(yīng)的時(shí)間等級(jí);Tk為決策變量，表示AGV v完成任務(wù)k的時(shí)間;Cv（t）為決策變量，表示AGV v在時(shí)刻t的電量;Sv（t）為決策變量，表示AGV v在時(shí)刻t的位置;W為決策變量，表示待完成任務(wù)集合;wv（t）為決策變量，表示AGV v在時(shí)刻t按照任務(wù)選擇原則需完成的加權(quán)值最小的任務(wù);xvk（t）為決策變量，表示AGV v在時(shí)刻t到達(dá)任務(wù)k起點(diǎn)的執(zhí)行時(shí)間與任務(wù)k緊急程度的加權(quán)值;yv（t）為決策變量，表示AGV v在時(shí)刻t到達(dá)各任務(wù)起點(diǎn)的執(zhí)行時(shí)間與各任務(wù)緊急程度的最小加權(quán)值。

2.2 任務(wù)選擇模型

任務(wù)選擇原則依據(jù)AGV到達(dá)各任務(wù)起點(diǎn)的執(zhí)

行時(shí)間、各任務(wù)的緊急程度進(jìn)行設(shè)定。AGV在完成上一任務(wù)后要選擇下一執(zhí)行任務(wù)，任務(wù)選擇原則為：對(duì)該AGV到達(dá)剩余各任務(wù)的執(zhí)行時(shí)間與各任務(wù)的緊急程度進(jìn)行加權(quán)，選擇加權(quán)值最小的任務(wù)，約束條件如下，其中k∈K，v∈V。

式（1）表示AGV v在時(shí)刻t的各剩余任務(wù)加權(quán)值的最小值;式（2）表示AGV v在時(shí)刻t的各剩余任務(wù)的加權(quán)值;式（3）表示AGV v在時(shí)刻t選擇加權(quán)值最小的任務(wù)k作為待執(zhí)行任務(wù)，其中S1（x）為0-1函數(shù)（若x≥0則取1，否則取0）。

2.3 考慮充電特性和等待時(shí)間的AGV調(diào)度模型

在任務(wù)選擇模型的基礎(chǔ)上，設(shè)定以下函數(shù)變量：

S2（x）為0-1函數(shù)，若x>0則取1，否則取0;S3（x）為 0-1函數(shù)，若x=0則取1，否則取0;Avk（t）為0-1變量，若wv（t）=k且電量滿足任務(wù)k則取1，否則取0;Mv（t）為0-1變量，若在時(shí)刻t AGV v不充電則取1，否則取0;Qv（t）為0-1變量，若在時(shí)刻t AGV v斷開(kāi)充電電源則取1，否則取0。

假設(shè)在完成已知任務(wù)期間無(wú)其他船進(jìn)港，不考慮緩存區(qū)容量限制、AGV在運(yùn)輸過(guò)程中和在堆場(chǎng)內(nèi)的等待時(shí)間和AGV到達(dá)充電站進(jìn)行充電的操作時(shí)間。以完成任務(wù)總時(shí)間最短為目標(biāo)，建立自動(dòng)化集裝箱碼頭AGV調(diào)度模型，模型的目標(biāo)函數(shù)和約束條件如下，其中k∈K，v∈V。

式（4）表示完成任務(wù)總時(shí)間最短;式（5）限定在時(shí)刻t需要充電的AGV數(shù)量不大于充電樁的數(shù)量;式（6）限定每個(gè)任務(wù)只能被完成一次且都要被完成;式（7）限定AGV在充電期間不能被分配任務(wù);式（8）限定當(dāng)在時(shí)刻t AGV v需執(zhí)行任務(wù)k，且電量滿足AGV v能完成任務(wù)k且能返回充電站l時(shí)，AGV v前去執(zhí)行任務(wù)k;式（9）表示若有AGV前往充電站充電，則在充電的AGV電量達(dá)到PU后可結(jié)束充電進(jìn)入工作狀態(tài);式（10）表示若AGV在時(shí)刻t能夠完成目標(biāo)任務(wù)則無(wú)須充電，否則必須前往充電站充電;式（11）為任務(wù)k結(jié)束時(shí)間。

3 算例分析

在求解模型時(shí)，根據(jù)港口的實(shí)際工作狀態(tài)設(shè)定AGV的重載和空載運(yùn)行速度分別為20、25 km/h，在該工作區(qū)域有2個(gè)岸橋、6個(gè)場(chǎng)橋、8輛可用AGV和1 000 TEU集裝箱卸船任務(wù)，其中2個(gè)岸橋各500 TEU集裝箱卸船任務(wù)。在AGV進(jìn)行任務(wù)選擇時(shí)，對(duì)各AGV到達(dá)各剩余任務(wù)起點(diǎn)的執(zhí)行時(shí)間與各任務(wù)的緊急程度進(jìn)行加權(quán)。由于港口實(shí)際作業(yè)過(guò)程中優(yōu)先考慮任務(wù)的緊急程度，且分析得出在α、β取值不同的情況下AGV充電限制對(duì)完成任務(wù)總時(shí)間的影響相同，因此設(shè)定α=0.4、β=0.6。在實(shí)際操作過(guò)程中，AGV必須預(yù)留能夠返回充電站的電量，參考文獻(xiàn)[2]設(shè)定AGV在完成一項(xiàng)任務(wù)時(shí)至少要保留10%的最低電量使其能夠返回充電站。岸橋與場(chǎng)橋之間的距離見(jiàn)表1，岸橋與場(chǎng)橋之間的任務(wù)數(shù)量見(jiàn)表2，可用的8輛AGV初始電量見(jiàn)表3。

在求解時(shí)將Java作為編程語(yǔ)言，基于Java編程語(yǔ)言面向?qū)ο蟮奶匦裕瑢⒛Ｐ椭械腁GV、場(chǎng)橋、岸橋、充電站和任務(wù)抽象為實(shí)體對(duì)象，并以工廠模式創(chuàng)建不同的工廠生產(chǎn)不同的對(duì)象實(shí)例。在生產(chǎn)實(shí)例時(shí)以讀取配置文件的方式為不同的實(shí)例賦值。AGV實(shí)例創(chuàng)建完后以模型中的算法進(jìn)行任務(wù)接受、執(zhí)行、完成和充電。在任務(wù)執(zhí)行期間記錄每輛AGV的任務(wù)執(zhí)行時(shí)間，當(dāng)所有AGV都完成任務(wù)后再計(jì)算用時(shí)最長(zhǎng)的一輛AGV的用時(shí)，即得到完成所有任務(wù)所需的時(shí)間。

最終得到的完成任務(wù)總時(shí)間和總充電次數(shù)見(jiàn)表4，不同PU值對(duì)應(yīng)的完成任務(wù)總時(shí)間的具體變化見(jiàn)圖3。從圖3可以看出，改變PU能夠影響AGV完成所有任務(wù)的時(shí)間：當(dāng)PU在50%～60%范圍內(nèi)取值時(shí)，由于總充電次數(shù)均為12次，因此當(dāng)PU取值不斷增大時(shí)，每輛AGV的充電時(shí)間增加，使得完成任務(wù)總時(shí)間不斷增加;當(dāng)PU在67%～88%范圍內(nèi)取值時(shí)，完成任務(wù)總時(shí)間較短，且在PU為71%時(shí)完成任務(wù)總時(shí)間最短，比AGV到達(dá)充電站一直充至滿電再進(jìn)入工作狀態(tài)的充電方式耗時(shí)少，因此可采用多頻次充電的方法對(duì)AGV進(jìn)行合理的充電設(shè)置。

上述結(jié)果是在α=0.4、β=0.6時(shí)計(jì)算得出的。改變?chǔ)?、β的值，得到如圖6所示的結(jié)果：隨著AGV到達(dá)各任務(wù)起點(diǎn)的執(zhí)行時(shí)間的權(quán)重α的增加（即優(yōu)先考慮執(zhí)行近距離任務(wù)），完成任務(wù)總時(shí)間會(huì)減少，但對(duì)任務(wù)的緊急程度滿足度較低。此處是在完成1 000 TEU集裝箱卸船任務(wù)的情況下進(jìn)行分析的，在港口實(shí)際工作中可根據(jù)實(shí)際情況設(shè)定任務(wù)選擇原則。

本文在為AGV選擇任務(wù)時(shí)，既考慮AGV到達(dá)各任務(wù)起點(diǎn)的執(zhí)行時(shí)間又考慮各任務(wù)的緊急程度，綜合選擇最佳的任務(wù)分配方案，避免一味追求時(shí)間效率而忽略任務(wù)緊急程度的情況，也避免只注重任務(wù)優(yōu)先級(jí)而造成AGV效率過(guò)低、時(shí)間成本費(fèi)用增加的情況。

對(duì)AGV的充電電量設(shè)定不同的限制值進(jìn)行比較，結(jié)果表明PU=71%為最佳限制值，可避免AGV在充電站等待時(shí)間過(guò)長(zhǎng)，也使完成任務(wù)總時(shí)間最短。

4 結(jié)束語(yǔ)

自動(dòng)化集裝箱碼頭自動(dòng)導(dǎo)引小車（AGV）調(diào)度問(wèn)題是影響碼頭作業(yè)效率的重要因素，本文在自動(dòng)化集裝箱碼頭AGV的調(diào)度過(guò)程中考慮了AGV的電量續(xù)航能力和重空載耗電差異，同時(shí)考慮任務(wù)的緊急情況和完成任務(wù)總時(shí)間，比較貼近實(shí)際，具有現(xiàn)實(shí)意義。運(yùn)用Java進(jìn)行案例分析，結(jié)果表明：采用多頻次充電的方法對(duì)AGV充電電量設(shè)定合理的限制值，既可以減少完成任務(wù)總時(shí)間又可以提高AGV利用率，并使耗電量減少。然而，本文未考慮AGV運(yùn)輸過(guò)程中的路徑?jīng)_突問(wèn)題和充電站的數(shù)量問(wèn)題，且只考慮了完成卸船任務(wù)未考慮邊裝邊卸情況，接下來(lái)會(huì)對(duì)此做進(jìn)一步研究。

參考文獻(xiàn)：

[1]謝旦嵐， 俞海宏， 陳靖， 等. 自動(dòng)化物流設(shè)備充電模式的仿真優(yōu)化研究[J]. 系統(tǒng)仿真學(xué)報(bào)， 2017， 29（9）： 2213-2220.

[2]傅正堂， 胡志華， 宗康. 集裝箱碼頭AGV電量非飽和狀態(tài)下的調(diào)度優(yōu)化[J]. 大連海事大學(xué)學(xué)報(bào)， 2017， 43（3）： 58-62. DOI： 10.16411/j.cnki.issn1006-7736.2017.03.010.

[3]荀燕琴. 基于群體智能優(yōu)化的AGV路徑規(guī)劃算法研究[D]. 長(zhǎng)春： 吉林大學(xué)， 2017.

[4]LI Guangqiang， LIU Qi， YANG Yawei， et al. An improved differential evolution based artificial fish swarm algorithm and its application to AGV path planning problems[C]//Proceedings of the 36th Chinese Control Conference， Dalian： IEEE Computer Society， 2017： 2556-2561.