考慮充電策略的自動化碼頭AGV調度

陳琿 韓曉龍

摘要：針對自動化碼頭自動導引車（automated guided vehicle， AGV）在作業調度中的充電問題，以最小化所有任務完成時間為目標，建立考慮充電策略的AGV調度模型。對比求解器（Gurobi）與遺傳算法的算例求解結果，驗證遺傳算法的高效性。設計4種充電方式并對其優劣性進行對比，分析AGV數量和續航能力對作業時間和充電利用率的影響。得出結論：按需充電的方式可以有效減少不必要的充電時間，合理的AGV數量配置可以有效提高作業效率和充電利用率。

關鍵詞：

自動化碼頭; 自動導引車（AGV）調度; 充電策略; 遺傳算法

中圖分類號：? U691+.3

文獻標志碼：? A

AGV scheduling of automated terminals considering charging strategy

CHEN Hui， HAN Xiaolong

（

Institute of Logistics Science & Engineering， Shanghai Maritime University， Shanghai 201306， China）

Abstract：

For the charging issue of automated guided vehicles （AGVs） in operation scheduling of automated terminals， aiming at minimizing the completion time of all tasks， an AGV scheduling model considering charging strategy is established. The results of the solver （Gurobi） and the genetic algorithm are compared through examples， and the efficiency of the genetic algorithm is verified. The four charging schemes are designed， and their advantages and disadvantages are compared. The influence of the number of AGV and the endurance on the working time and the charging utilization rate is analyzed. It is concluded that the on-demand charging scheme can effectively reduce the excess charging time， and the appropriate AGV quantity configuration can effectively improve the operation efficiency and the charging utilization rate.

Key words：

automated terminal; automated guided vehicle （AGV） scheduling; charging strategy; genetic algorithm

收稿日期： 2020-06-30

修回日期： 2020-11-26

基金項目：

上海市科學技術委員會工程中心能力提升項目（ 14DZ2280200）

作者簡介： 陳琿（1995—），男，江蘇南通人，碩士研究生，研究方向為港口運營與管理，（E-mail）1226191601@qq.com;

韓曉龍（1978—），男，山東濰坊人，副教授，博士，研究方向為物流與供應鏈管理，（E-mail）superhxl@163.com

0 引 言

隨著經濟全球化的發展，國際貿易活動越發頻繁，港口集裝箱吞吐量也逐漸增加。為更好地滿足港口作業需求，需要進一步提高港口作業效率。純電力驅動的自動導引車（automated guided vehicle，AGV）正逐漸成為新一代港口海側運輸作業的主要設備。

國外AGV調度的研究大多集中在作業分配和路徑優化方面。CHANG等[1]提出一種基于遺傳算法（genetic algorithm， GA）的仿真優化算法，采用響應面分析法優化GA參數，以提高AGV的作業效率。GELAREH等[2]設計了一種新型的智能車輛，通過靈活的作業分配縮短作業路徑。WU等[3]用一種基于模糊邏輯控制的車輛路徑規劃方法提高AGV作業路徑的安全性。針對多AGV路徑規劃問題，HAN等[4]提出三交換啟發式算法，用來縮短單AGV作業路徑和多AGV作業總路徑。針對港口的協同調度問題，YANG等[5]以最小化作業時間為目標，建立雙層規劃模型，并利用滾動視距法和雙層GA進行求解。

少部分學者考慮了充電對AGV調度的影響。MCHANEY[6]提出電池的使用

對AGV的作業調度有很大影響，但這種影響

在AGV仿真中常常被忽視。MOUSAVI等[7]以最小化AGV數量為目標，建立了考慮充電的AGV作業調度模型，并采用混合GA進行求解。ZHAN等[8]使用鋰離子電池，采用雙充電站的充電模式，建立了AGV調度模型，并通過實際案例證明該方法能有效提高AGV的作業效率。

與國外相比，國內自動化碼頭建設還處于初期，對AGV的作業調度還需要進一步研究。康凱等[9]分析了干散貨港口裝卸作業調度之間的聯系，構建了作業系統集成調度模型，并采用GA進行求解。韓曉龍等[10]建立了岸橋、AGV、場橋和堆場的仿真模型，設計了不同的AGV調度策略，根據實驗結果給出了AGV調度和數量優化的相關建議。劉高強等[11]通過改進GA的變異算子提高種群的收斂速度，獲得了更優路徑。張亞琦等[12]以最小化AGV作業時間為目標建立模型，并用GA進行求解，雖然考慮了AGV的充電過程，但對具體的充電決策研究不足。針對AGV的路徑規劃問題，趙大興等[13]提出一種基于高適應度值的GA，仿真結果表明該調度策略合理高效。孟沖等[14]以最小化AGV作業時間為目標，將GA引入雙階段路徑規劃中，實驗結果表明該策略提高了AGV調度系統的效率和魯棒性。仲美穌等[15]采用“模型+實例+仿真”的方法研究自動化碼頭AGV路徑優化問題，提出交通虛擬環島策略，仿真結果證明了該策略的高效性。

國內外學者對實際作業中的充電問題研究較少，而充電策略對AGV的作業調度有很大的影響：充電站和作業點的位置關系會影響作業順序;一旦AGV由于電量不足停在某個任務的路徑中，會大幅降低作業效率。本文考慮AGV在實際作業中的充電問題，對具體路徑優化中的充電策略展開研究，以縮短作業時間，提高充電利用率。

1 問題描述

自動化碼頭的AGV與電動汽車一樣，不僅充滿電所需的時間較長，而且續航能力有限。在實際作業中，AGV每完成一個任務后都需要計算當前的剩余電量，只有當剩余電量足夠時才會進行下一個任務。

考慮充電策略的AGV調度問題相對復雜，一方面要滿足AGV電量的及時補給需求，另一方面AGV充電受其剩余電量的影響。為方便計算，假定AGV的電量消耗與行駛路程成正比。

圖1是集裝箱堆場的俯視圖。在日常作業中，AGV收到任務后，立即去相應的作業點執行任務;當電量不足時，AGV會發送充電請求，系統收到后會給該AGV分配充電任務;AGV收到充電任務后，回到充電站進行充電;AGV充電完成后再次進入作業狀態。

AGV執行任意兩個相鄰任務的流程如下：AGV在任

務i的裝載點裝貨后，到任務i的交付點卸貨;完成任務i后根據剩余電量判斷是否需要充電，若不需要則直接執行任務j，否則去充電站充電后再執行任務j。從開始執行任務到返回充電站充電，稱為一個作業循環。

2 考慮充電策略的AGV調度模型

2.1 模型假設

每輛AGV每次只能運輸一個集裝箱;岸橋和場橋的單位集裝箱裝卸時間是固定的;AGV勻速行駛;AGV從初始位置出發，各自作業，相互獨立;充電站內有足夠多的充電接口，AGV到達充電站后均能立即充電;不考慮作業過程中的突發狀況，

AGV均能正常完成任務;AGV開始作業時刻為0。

2.2 符號說明

I為所有任務的集合，I={1，2，…，N};集合I+={1，2，…，N，N+1，N+2}，其中N+1和N+2分別為虛擬開始任務和虛擬結束任務;K為AGV集合，K={1，2，…，|K|}，k∈K;C為充電任務集合（未知），C={N+3，N+4，…};M是一個足夠大的數;Lij為從任務i的交付點到任務j的裝載點之間的距離;Li為從任務i的裝載點到任務i的交付點之間的距離;Tij為AGV從任務i的交付點到任務j的裝載點的時間;Ti為AGV從任務i的裝載點到任務i的交付點的時間;tik為AGV k針對任務i的裝卸作業時間;b為充電時間參數，為充電時間與充電電量的比值;a為[0，1）之間的常數，表示AGV最低剩余電量占電池充滿電時電量的比值;G為AGV續航能力;xijk為0-1變量，若AGV k完成任務i后緊接著去執行任務j則取1，否則取0;yik為0-1變量，若AGV k執行任務i則取1，否則取0;qik為AGV k到達任務i的裝載點時的剩余電量;Qi為充電任務i的目標電量;Q為電池充滿電時的電量;f為完成最后一個任務的時刻;Zi為任務i的開始時刻;dik為AGV k完成任務i的累計行駛路程;Rk為AGV k的實際行駛路程;Sk為AGV k的理論可行駛路程;r為AGV的充電利用率。

2.3 建立模型

以最小化所有任務完成時間為目標函數（見式（1））建立模型如下，其中下標k∈K。

min f

（1）

s.t.

xi，N+1，k=0， i∈I+

（2）

xN+2，i，k=0， i∈I+（3）

f≥Zi+Ti， i∈I+（4）

xijk+xjik≤1 （i，j∈I∪C;i≠j）（5）

kyik=1， i∈I（6）

Zj+（1-xijk）M≥Zi+tik+Ti+Tij

（i，j∈I;i≠j）（7）

Zj+（1-xijk）M≥Zi+tik+Tij，

tik=b（Qi-qik），Qi>qik

（i∈C; j∈I）（8）

aQ≤qjk≤qik-（Li+Lij）Qxijk/G+Q（1-xijk）

（i，j∈I;i≠j）（9）

aQ≤qjk≤Qi-LijQxijk/G

（i∈C; j∈I）（10）

qN+1，k=Q（11）

djk+（1-xijk）M≥dik+Lij+Lj

（i，j∈I+∪C;i≠j）（12）

Li=0 （i∈C）（13）

i∈I+＼{j，N+2}xijk=l∈I+＼{i，j，N+1}xjlk=yjk

（j∈I）（14）

式（2）和（3）分別表示虛擬開始任務之前和虛擬結束任務之后AGV沒有任務執行;式（4）表示最后一個任務完成時刻與各任務完成時刻的關系;式（5）表示各AGV完成單方向的作業序列，即不允許重復同一個作業;式（6）表示每個任務必須由一輛AGV單獨完成;式（7）和（8）表示連續兩個任務開始時刻的關系;式（9）和（10）表示連續兩個任務開始時剩余電量的關系;式（11）表示執行任務之前AGV處于充滿電狀態;式（12）表示AGV執行連續兩個任務的累計行駛路程之間的關系;式（13）表示充電過程中AGV停止不動;式（14）表示連續任務之間的流約束。

3 GA

3.1 編碼

本文根據AGV的任務分配進行編碼。任務i對應AGV k，表示任務i由AGV k完成。先隨機生成N個位于（0， |K|）區間內的隨機數，然后給這些隨機數按順序標上任務編號，并將這些隨機數分別去尾取整后加1，得到任務對應的AGV編號（如對1.23處理后得到的AGV編號為2）。圖2是一個由3輛AGV進行12個任務作業的染色體編碼。

3.2 解碼

先將N個任務分配給|K|輛AGV，然后按照每輛AGV獲得的任務進行解碼。各AGV在被分配任務后，對任務按任務編號由小到大排序，接著根據任務順序進行作業，這樣既滿足了任務的分配，也考慮了任務本身的順序。

染色體的解碼過程如圖3所示，其中：m表示任務N-4之前的任務編號。每輛AGV的任務及其

順序確定后，結合模型得到其執行完任務后的累計

行駛路程以及執行每個任務的開始時刻，根據式（7）和（8），得到所有任務完成時間。

3.3 適應度函數

本文適應度函數為min f，即最小化所有任務完成時間，以此來判斷每個可行解的優劣程度。

3.4 選擇

選擇的目的是將優秀的個體盡量遺傳下去，但為了避免種群收斂太快陷入局部最優解的情況，在選擇時也要考慮非優秀個體。本文采用隨機遍歷選擇法，使適應度值不同的個體被選擇的機會均等。任意選取4個個體，計算其適應度值，得到2個較優個體。

3.5 交叉

采用基于位置的交叉方法生成新的染色體，見圖4。

步驟1 令2條較優的染色體分

別為p1、p2，2條新染色體分別為c1、c2。

步驟2 把p1的前半部分的基因值賦值為c1的前半部分的基因值，然后把p1剩余的基因值賦值為c2的后半部分的基因值。

步驟3 把p2的前半部分的基因值賦值為c2的前半部分的基因值，然后把p2剩余的基因值賦值為c1的后半部分的基因值。

步驟4 重復前面3個步驟，直到新的個體數量滿足種群要求。

3.6 變異

在染色體中隨機選擇2個基因位b1、b2進行調換，得到新的染色體，如圖5所示。

4 數據實驗

在以上模型和算法的基礎上，使用Python 3.7進行代碼編寫和數據實驗，實驗設置見表1。實驗1對比了GA與混合整數線性規劃（mixed integer

linear planning， MILP）算法的求解結果（調用求解器Gurobi）;實驗2對比了不同充電方案的作業時間（用GA計算）;實驗3研究了AGV數量和續航能力對作業時間和充電利用率的影響（用GA計算）。

4.1 不同算法的求解結果（實驗1）

當任務數分別為8、9、10、11、12、16、20時，不同算法的求解結果見表2。

由表2可知：GA的計算結果與精確解的誤差較小;當任務數超過11時，MILP算法的計算時間顯著增加，而GA的計算時間很短且解的質量較優。實際問題中任務較多且求解要求較高，因此用GA求解實際問題更為合適。

解的平均偏差率計算公式為

D=Ww=1fw-fminfmin

W×100%

（15）

式中：W表示實驗次數;fw表示第w次實驗得到的作業時間;fmin表示所有實驗中的最短作業時間。

為驗證GA求解結果的穩定性，通過反復實驗找到最優的交叉與變異概率組合，再用GA求解任務數為1 000的作業時間，重復實驗40次，得到最短的作業時間為28 631 s。根據式（15）得到解的平均偏差率D僅為0.44%，說明采用GA給出的方案是可靠的。

4.2 充電方案對比（實驗2）

在研究AGV的充電策略時，要考慮充電時機和每次目標充電量這兩個問題。

充電時機會影響AGV完成相同任務所需的充電次數，較多的充電次數會增加無效的空載時間。因此，在現有的續航能力約束下要盡量減少充電次數。針對該問題，有2種策略：剩余電量不足10%時充電;當利用剩余電量無法完成下一個任務時，或完成下一個任務后無法前往充電站時充電。

針對每次目標充電量問題，也有2種策略：每一次都充滿;根據下一作業循環的實際需求充電。綜合以上4種策略，設計4種充電方案，見表3。

對這4種充電方案進行實驗。設置AGV數量為12輛，AGV的續航能力G為20 km;根據前述反復實驗結果，取交叉概率0.7，變異概率0.4;根據收斂情況，確定最大迭代次數為500。當任務數分別為1 000、1 100、1 200、1 400、1 600、1 800、2 000、2 400時，4種充電方案作業時間對比見表4。

由表4可知：方案3、4整體上優于方案1、2;雖然在任務數為1 200和1 400時，方案4略優于方案3，但是作業時間差距很小，方案3總體上最優。

為更好地說明方案3的優勢，分別記錄任務數為1 000和2 000時，12輛AGV在作業過程中每次充電后的電量，見圖6。當任務數為1 000時，每輛AGV只需充電1次即可完成任務;當任務數為2 000時，每輛AGV需要充電2次才能完成任務;每輛AGV每次充電量不同，這由下一作業循環所需電量決定。當所需電量較多時多充，反之則少充，滿足電量需求即可。這種靈活的充電方式，能夠有效減少不必要的充電時間，在提高充電利用率的同時，也采用方案3充電后電量縮短了總的作業時間。

4.3 AGV數量和續航能力對作業時間和充電利用率的影響（實驗3）

充電利用率r的計算公式如下：

r=kRkkSk

（16）

Rk=max{dik}， i∈I+，k∈K

（17）

Sk=i∈Ctikb+QGQ， k∈K

（18）

采取充電方案3，以最小化所有任務完成時間和最大化充電利用率為目標，取續航能力G為20 km，任務數為1 000，設置AGV數量為9～20輛進行實驗，結果如圖7a所示：隨著AGV數量的增加，作業時間逐漸減少;充電利用率在AGV數量不超過15輛時高達98%，在超過15輛時明顯下降。考慮配置AGV的成本以及充電利用率，當任務數較大時，給3臺岸橋配置15輛AGV進行作業比較合適。

取AGV數量為15輛，任務數為1 000，研究續航能力對作業時間和充電利用率的影響。從圖7b可以看出，隨著續航能力的增強，作業時間先是大幅度減少，而后趨于穩定。續航能力的增強，會使AGV的充電次數減少，從而使充電時間以及AGV往返充電站的空載時間減少。當續航能力達到足夠大（如G=25 km）時，AGV在作業過程中不需要進行充電，總的作業時間與充電無關，趨于穩定。另外，隨著充電次數的減少，AGV的累計行駛路徑長度也會減少。根據式（17）和（18）容易得到，任務數一定時，充電利用率會隨著續航能力的增強而不斷降低，這是由AGV完成任務后剩余電量較多造成的。

當任務數一定時，AGV數量的增加和續航能力的增強都會使每輛AGV在完成相應任務后剩余電量較多。前者是由每輛AGV執行的任務數減少且不需要充電導致的，后者是由電池總電量增大導致的，二者都會導致充電利用率降低。因此，為提高充電利用率，AGV數量不宜過多;在續航能力較強時，應當給AGV分配較多的任務。

5 結束語

本文從自動導引車（AGV）作業的實際情況出發，研究充電對作業調度的影響，建立了考慮充電策略的AGV調度模型，給出了不同的充電方案，并對比了它們的優劣。通過實驗得到以下結論：

（1）考慮充電策略的AGV調度問題屬于NP難問題，當任務較少時，可以用混合整數線性規劃（MILP）算法求得精確解;在任務較多時，求解器無法在短時間內求得結果，必須采用GA（GA）等智能搜索算法。實驗結果證明采用GA求解該問題是高效、可靠的。

（2）在AGV運輸速度、裝卸作業時間、任務安排一定的情況下，作業的完成時間很大程度上取決于AGV的充電策略。在利用剩余電量無法完成下一個任務時充電且按需充電是一種較好的充電方案，它能夠節省不必要的充電時間，提高充電利用率，進一步縮短作業時間。

（3）在任務數一定時，AGV數量的增加可以減少作業時間，但同時也會降低充電利用率，導致資源配置的不合理。因此，不能一味地增加AGV數量，需要尋找AGV數量與任務數的最佳配比。實驗結果表明，在任務數較大的情況下，給3臺岸橋安排15輛AGV較為合適。另外，提高續航能力能減少充電次數，提高作業效率，適合完成作業量較大的任務。

本文未考慮AGV滿載與空載時不同的電量消耗、充電站的容量配置等對AGV調度的影響，這方面還需要進一步研究。

參考文獻：

[1]CHANG Xiaokun， DONG Ming， YANG Dong. Multi-objective real-time dispatching for integrated delivery in a Fab using GA based simulation optimization[J]. Journal of Manufacturing Systems， 2013， 32（4）： 741-751. DOI： 10.1016/j.jmsy.2013.07.001.

[2]GELAREH S， MERZOUKI R， MCGINLEY K， et al. Scheduling of intelligent and autonomous vehicles under pairing/unpairing collaboration strategy in container terminals[J]. Transportation Research Part C， 2013， 33： 1-21. DOI： 10.1016/j.trc.2013.04.006.

[3]WU K H， CHEN C H， KO J M. Path planning and prototype design of an AGV[J]. Mathematical and Computer Modelling， 1999， 30（7/8）： 147-167. DOI： 10.1016/S0895-7177（99）00171-5.

[4]HAN Zengliang， WANG Dongqing， LIU Feng， et al. Multi-AGV path planning with double-path constraints by using an improved genetic algorithm[J].PLoS One， 2017， 12（7）： e0181747. DOI： 10.1371/journal.pone.0181747.

[5]YANG Yongsheng， ZHONG Meisu， DESSOUKY Y，et al.An integrated scheduling method for AGV routing in automated container terminals[J]. Computers & Industrial Engineering， 2018， 126： 482-493. DOI： 10.1016/j.cie.2018.10.007.

[6]MCHANEY R. Modelling battery constraints in discrete event automated guided vehicle simulations[J]. International Journal of Production Research， 1995， 33（11）： 3023-3040. DOI： 10.1080/00207549508904859.

[7]MOUSAVI M， YAP H J， MUSA S N， et al. A fuzzy hybrid GA-PSO algorithm for multi-objective AGV scheduling in FMS[J].International Journal of Simulation Modelling， 2017， 16（1）： 58-71. DOI： 10.2507/IJSIMM16（1）5.368.

[8]ZHAN Xiangnan， XU Liyun， ZHANG Jian， et al. Study on AGVs battery charging strategy for improving utilization[J].Procedia CIRP， 2019， 81： 558-563. DOI： 10.1016/j.procir.2019.03.155.

[9]康凱， 張敬， 張維存， 等.干散貨港口裝卸作業系統集成調度模型與算法研究[J].物流技術， 2014， 33（7）： 121-125， 188. DOI： 10.3969/j.issn.1005-152X.2014.04.040.

[10]韓曉龍， 樊加偉. 自動化港口AGV調度配置仿真分析[J].重慶交通大學學報（自然科學版）， 2016， 35（5）： 151-154， 164. DOI： 10.3969/j.issn.1674-0696.2016.05.29.

[11]劉高強， 劉利桁， 劉婷. 基于改進GA的多AGV調度優化[J].機電技術， 2017（5）： 44-46， 50. DOI： 10.19508/j.cnki.1672-4801.2017.05.014.

[12]張亞琦， 楊斌， 胡志華， 等.自動化碼頭AGV充電與作業的集成調度研究[J].計算機工程與應用， 2017， 53（18）： 257-262， 270. DOI： 10.3778/j.issn.1002-8331.1605-0003.

[13]趙大興， 余明進， 許萬. 基于高適應度值GA的AGV最優路徑規劃[J].計算機工程與設計， 2017， 38（6）： 1635-1641. DOI： 10.16208/j.issn.1000-7024.2017.06.043.

[14]孟沖， 任彧. 基于多種群GA的多AGV調度[J].電子科技， 2018， 31（11）： 47-50， 68.

[15]仲美穌， 楊勇生. 卸船作業模式下自動化碼頭AGV路徑仿真優化[J].水運工程， 2018（4）： 122-127.

（編輯 趙勉）