陳琿 韓曉龍

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

關(guān)鍵詞：

自動(dòng)化碼頭; 自動(dòng)導(dǎo)引車（AGV）調(diào)度; 充電策略; 遺傳算法

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

文獻(xiàn)標(biāo)志碼：? 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

基金項(xiàng)目：

上海市科學(xué)技術(shù)委員會(huì)工程中心能力提升項(xiàng)目（ 14DZ2280200）

作者簡(jiǎn)介： 陳琿（1995—），男，江蘇南通人，碩士研究生，研究方向?yàn)楦劭谶\(yùn)營(yíng)與管理，（E-mail）1226191601@qq.com;

韓曉龍（1978—），男，山東濰坊人，副教授，博士，研究方向?yàn)槲锪髋c供應(yīng)鏈管理，（E-mail）superhxl@163.com

0 引 言

隨著經(jīng)濟(jì)全球化的發(fā)展，國(guó)際貿(mào)易活動(dòng)越發(fā)頻繁，港口集裝箱吞吐量也逐漸增加。為更好地滿足港口作業(yè)需求，需要進(jìn)一步提高港口作業(yè)效率。純電力驅(qū)動(dòng)的自動(dòng)導(dǎo)引車（automated guided vehicle，AGV）正逐漸成為新一代港口海側(cè)運(yùn)輸作業(yè)的主要設(shè)備。

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

少部分學(xué)者考慮了充電對(duì)AGV調(diào)度的影響。MCHANEY[6]提出電池的使用

對(duì)AGV的作業(yè)調(diào)度有很大影響，但這種影響

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

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

國(guó)內(nèi)外學(xué)者對(duì)實(shí)際作業(yè)中的充電問(wèn)題研究較少，而充電策略對(duì)AGV的作業(yè)調(diào)度有很大的影響：充電站和作業(yè)點(diǎn)的位置關(guān)系會(huì)影響作業(yè)順序;一旦AGV由于電量不足停在某個(gè)任務(wù)的路徑中，會(huì)大幅降低作業(yè)效率。本文考慮AGV在實(shí)際作業(yè)中的充電問(wèn)題，對(duì)具體路徑優(yōu)化中的充電策略展開(kāi)研究，以縮短作業(yè)時(shí)間，提高充電利用率。

1 問(wèn)題描述

自動(dòng)化碼頭的AGV與電動(dòng)汽車一樣，不僅充滿電所需的時(shí)間較長(zhǎng)，而且續(xù)航能力有限。在實(shí)際作業(yè)中，AGV每完成一個(gè)任務(wù)后都需要計(jì)算當(dāng)前的剩余電量，只有當(dāng)剩余電量足夠時(shí)才會(huì)進(jìn)行下一個(gè)任務(wù)。

考慮充電策略的AGV調(diào)度問(wèn)題相對(duì)復(fù)雜，一方面要滿足AGV電量的及時(shí)補(bǔ)給需求，另一方面AGV充電受其剩余電量的影響。為方便計(jì)算，假定AGV的電量消耗與行駛路程成正比。

圖1是集裝箱堆場(chǎng)的俯視圖。在日常作業(yè)中，AGV收到任務(wù)后，立即去相應(yīng)的作業(yè)點(diǎn)執(zhí)行任務(wù);當(dāng)電量不足時(shí)，AGV會(huì)發(fā)送充電請(qǐng)求，系統(tǒng)收到后會(huì)給該AGV分配充電任務(wù);AGV收到充電任務(wù)后，回到充電站進(jìn)行充電;AGV充電完成后再次進(jìn)入作業(yè)狀態(tài)。

AGV執(zhí)行任意兩個(gè)相鄰任務(wù)的流程如下：AGV在任

務(wù)i的裝載點(diǎn)裝貨后，到任務(wù)i的交付點(diǎn)卸貨;完成任務(wù)i后根據(jù)剩余電量判斷是否需要充電，若不需要?jiǎng)t直接執(zhí)行任務(wù)j，否則去充電站充電后再執(zhí)行任務(wù)j。從開(kāi)始執(zhí)行任務(wù)到返回充電站充電，稱為一個(gè)作業(yè)循環(huán)。

2 考慮充電策略的AGV調(diào)度模型

2.1 模型假設(shè)

每輛AGV每次只能運(yùn)輸一個(gè)集裝箱;岸橋和場(chǎng)橋的單位集裝箱裝卸時(shí)間是固定的;AGV勻速行駛;AGV從初始位置出發(fā)，各自作業(yè)，相互獨(dú)立;充電站內(nèi)有足夠多的充電接口，AGV到達(dá)充電站后均能立即充電;不考慮作業(yè)過(guò)程中的突發(fā)狀況，

AGV均能正常完成任務(wù);AGV開(kāi)始作業(yè)時(shí)刻為0。

2.2 符號(hào)說(shuō)明

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

2.3 建立模型

以最小化所有任務(wù)完成時(shí)間為目標(biāo)函數(shù)（見(jiàn)式（1））建立模型如下，其中下標(biāo)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）分別表示虛擬開(kāi)始任務(wù)之前和虛擬結(jié)束任務(wù)之后AGV沒(méi)有任務(wù)執(zhí)行;式（4）表示最后一個(gè)任務(wù)完成時(shí)刻與各任務(wù)完成時(shí)刻的關(guān)系;式（5）表示各AGV完成單方向的作業(yè)序列，即不允許重復(fù)同一個(gè)作業(yè);式（6）表示每個(gè)任務(wù)必須由一輛AGV單獨(dú)完成;式（7）和（8）表示連續(xù)兩個(gè)任務(wù)開(kāi)始時(shí)刻的關(guān)系;式（9）和（10）表示連續(xù)兩個(gè)任務(wù)開(kāi)始時(shí)剩余電量的關(guān)系;式（11）表示執(zhí)行任務(wù)之前AGV處于充滿電狀態(tài);式（12）表示AGV執(zhí)行連續(xù)兩個(gè)任務(wù)的累計(jì)行駛路程之間的關(guān)系;式（13）表示充電過(guò)程中AGV停止不動(dòng);式（14）表示連續(xù)任務(wù)之間的流約束。

3 GA

3.1 編碼

本文根據(jù)AGV的任務(wù)分配進(jìn)行編碼。任務(wù)i對(duì)應(yīng)AGV k，表示任務(wù)i由AGV k完成。先隨機(jī)生成N個(gè)位于（0， |K|）區(qū)間內(nèi)的隨機(jī)數(shù)，然后給這些隨機(jī)數(shù)按順序標(biāo)上任務(wù)編號(hào)，并將這些隨機(jī)數(shù)分別去尾取整后加1，得到任務(wù)對(duì)應(yīng)的AGV編號(hào)（如對(duì)1.23處理后得到的AGV編號(hào)為2）。圖2是一個(gè)由3輛AGV進(jìn)行12個(gè)任務(wù)作業(yè)的染色體編碼。

3.2 解碼

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

染色體的解碼過(guò)程如圖3所示，其中：m表示任務(wù)N-4之前的任務(wù)編號(hào)。每輛AGV的任務(wù)及其

順序確定后，結(jié)合模型得到其執(zhí)行完任務(wù)后的累計(jì)

行駛路程以及執(zhí)行每個(gè)任務(wù)的開(kāi)始時(shí)刻，根據(jù)式（7）和（8），得到所有任務(wù)完成時(shí)間。

3.3 適應(yīng)度函數(shù)

本文適應(yīng)度函數(shù)為min f，即最小化所有任務(wù)完成時(shí)間，以此來(lái)判斷每個(gè)可行解的優(yōu)劣程度。

3.4 選擇

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

3.5 交叉

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

步驟1 令2條較優(yōu)的染色體分

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

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

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

步驟4 重復(fù)前面3個(gè)步驟，直到新的個(gè)體數(shù)量滿足種群要求。

3.6 變異

在染色體中隨機(jī)選擇2個(gè)基因位b1、b2進(jìn)行調(diào)換，得到新的染色體，如圖5所示。

4 數(shù)據(jù)實(shí)驗(yàn)

在以上模型和算法的基礎(chǔ)上，使用Python 3.7進(jìn)行代碼編寫(xiě)和數(shù)據(jù)實(shí)驗(yàn)，實(shí)驗(yàn)設(shè)置見(jiàn)表1。實(shí)驗(yàn)1對(duì)比了GA與混合整數(shù)線性規(guī)劃（mixed integer

linear planning， MILP）算法的求解結(jié)果（調(diào)用求解器Gurobi）;實(shí)驗(yàn)2對(duì)比了不同充電方案的作業(yè)時(shí)間（用GA計(jì)算）;實(shí)驗(yàn)3研究了AGV數(shù)量和續(xù)航能力對(duì)作業(yè)時(shí)間和充電利用率的影響（用GA計(jì)算）。

4.1 不同算法的求解結(jié)果（實(shí)驗(yàn)1）

當(dāng)任務(wù)數(shù)分別為8、9、10、11、12、16、20時(shí)，不同算法的求解結(jié)果見(jiàn)表2。

由表2可知：GA的計(jì)算結(jié)果與精確解的誤差較小;當(dāng)任務(wù)數(shù)超過(guò)11時(shí)，MILP算法的計(jì)算時(shí)間顯著增加，而GA的計(jì)算時(shí)間很短且解的質(zhì)量較優(yōu)。實(shí)際問(wèn)題中任務(wù)較多且求解要求較高，因此用GA求解實(shí)際問(wèn)題更為合適。

解的平均偏差率計(jì)算公式為

D=Ww=1fw-fminfmin

W×100%

（15）

式中：W表示實(shí)驗(yàn)次數(shù);fw表示第w次實(shí)驗(yàn)得到的作業(yè)時(shí)間;fmin表示所有實(shí)驗(yàn)中的最短作業(yè)時(shí)間。

為驗(yàn)證GA求解結(jié)果的穩(wěn)定性，通過(guò)反復(fù)實(shí)驗(yàn)找到最優(yōu)的交叉與變異概率組合，再用GA求解任務(wù)數(shù)為1 000的作業(yè)時(shí)間，重復(fù)實(shí)驗(yàn)40次，得到最短的作業(yè)時(shí)間為28 631 s。根據(jù)式（15）得到解的平均偏差率D僅為0.44%，說(shuō)明采用GA給出的方案是可靠的。

4.2 充電方案對(duì)比（實(shí)驗(yàn)2）

在研究AGV的充電策略時(shí)，要考慮充電時(shí)機(jī)和每次目標(biāo)充電量這兩個(gè)問(wèn)題。

充電時(shí)機(jī)會(huì)影響AGV完成相同任務(wù)所需的充電次數(shù)，較多的充電次數(shù)會(huì)增加無(wú)效的空載時(shí)間。因此，在現(xiàn)有的續(xù)航能力約束下要盡量減少充電次數(shù)。針對(duì)該問(wèn)題，有2種策略：剩余電量不足10%時(shí)充電;當(dāng)利用剩余電量無(wú)法完成下一個(gè)任務(wù)時(shí)，或完成下一個(gè)任務(wù)后無(wú)法前往充電站時(shí)充電。

針對(duì)每次目標(biāo)充電量問(wèn)題，也有2種策略：每一次都充滿;根據(jù)下一作業(yè)循環(huán)的實(shí)際需求充電。綜合以上4種策略，設(shè)計(jì)4種充電方案，見(jiàn)表3。

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

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

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

4.3 AGV數(shù)量和續(xù)航能力對(duì)作業(yè)時(shí)間和充電利用率的影響（實(shí)驗(yàn)3）

充電利用率r的計(jì)算公式如下：

r=kRkkSk

（16）

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

（17）

Sk=i∈Ctikb+QGQ， k∈K

（18）

采取充電方案3，以最小化所有任務(wù)完成時(shí)間和最大化充電利用率為目標(biāo)，取續(xù)航能力G為20 km，任務(wù)數(shù)為1 000，設(shè)置AGV數(shù)量為9～20輛進(jìn)行實(shí)驗(yàn)，結(jié)果如圖7a所示：隨著AGV數(shù)量的增加，作業(yè)時(shí)間逐漸減少;充電利用率在AGV數(shù)量不超過(guò)15輛時(shí)高達(dá)98%，在超過(guò)15輛時(shí)明顯下降?？紤]配置AGV的成本以及充電利用率，當(dāng)任務(wù)數(shù)較大時(shí)，給3臺(tái)岸橋配置15輛AGV進(jìn)行作業(yè)比較合適。

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

當(dāng)任務(wù)數(shù)一定時(shí)，AGV數(shù)量的增加和續(xù)航能力的增強(qiáng)都會(huì)使每輛AGV在完成相應(yīng)任務(wù)后剩余電量較多。前者是由每輛AGV執(zhí)行的任務(wù)數(shù)減少且不需要充電導(dǎo)致的，后者是由電池總電量增大導(dǎo)致的，二者都會(huì)導(dǎo)致充電利用率降低。因此，為提高充電利用率，AGV數(shù)量不宜過(guò)多;在續(xù)航能力較強(qiáng)時(shí)，應(yīng)當(dāng)給AGV分配較多的任務(wù)。

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

本文從自動(dòng)導(dǎo)引車（AGV）作業(yè)的實(shí)際情況出發(fā)，研究充電對(duì)作業(yè)調(diào)度的影響，建立了考慮充電策略的AGV調(diào)度模型，給出了不同的充電方案，并對(duì)比了它們的優(yōu)劣。通過(guò)實(shí)驗(yàn)得到以下結(jié)論：

（1）考慮充電策略的AGV調(diào)度問(wèn)題屬于NP難問(wèn)題，當(dāng)任務(wù)較少時(shí)，可以用混合整數(shù)線性規(guī)劃（MILP）算法求得精確解;在任務(wù)較多時(shí)，求解器無(wú)法在短時(shí)間內(nèi)求得結(jié)果，必須采用GA（GA）等智能搜索算法。實(shí)驗(yàn)結(jié)果證明采用GA求解該問(wèn)題是高效、可靠的。

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

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

本文未考慮AGV滿載與空載時(shí)不同的電量消耗、充電站的容量配置等對(duì)AGV調(diào)度的影響，這方面還需要進(jìn)一步研究。

參考文獻(xiàn)：

[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]康凱， 張敬， 張維存， 等.干散貨港口裝卸作業(yè)系統(tǒng)集成調(diào)度模型與算法研究[J].物流技術(shù)， 2014， 33（7）： 121-125， 188. DOI： 10.3969/j.issn.1005-152X.2014.04.040.

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

[11]劉高強(qiáng)， 劉利桁， 劉婷. 基于改進(jìn)GA的多AGV調(diào)度優(yōu)化[J].機(jī)電技術(shù)， 2017（5）： 44-46， 50. DOI： 10.19508/j.cnki.1672-4801.2017.05.014.

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

[13]趙大興， 余明進(jìn)， 許萬(wàn). 基于高適應(yīng)度值GA的AGV最優(yōu)路徑規(guī)劃[J].計(jì)算機(jī)工程與設(shè)計(jì)， 2017， 38（6）： 1635-1641. DOI： 10.16208/j.issn.1000-7024.2017.06.043.

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

[15]仲美穌， 楊勇生. 卸船作業(yè)模式下自動(dòng)化碼頭AGV路徑仿真優(yōu)化[J].水運(yùn)工程， 2018（4）： 122-127.

（編輯 趙勉）