周小凡 萇道方 余芳 高銀萍

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

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

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

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

1 問題描述

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

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

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

2 模型建立

2.1 符號定義

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

2.2 任務(wù)選擇模型

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

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

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

2.3 考慮充電特性和等待時間的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變量，若在時刻t AGV v不充電則取1，否則取0;Qv（t）為0-1變量，若在時刻t AGV v斷開充電電源則取1，否則取0。

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

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

3 算例分析

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

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

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

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

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

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3]荀燕琴. 基于群體智能優(yōu)化的AGV路徑規(guī)劃算法研究[D]. 長春： 吉林大學(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.