薛海蓉，韓曉龍

基于改進(jìn)NSGA-Ⅱ的考慮自動引導(dǎo)車充電策略的集成調(diào)度

薛海蓉*，韓曉龍

（上海海事大學(xué) 物流科學(xué)與工程研究院，上海 201306）（?通信作者電子郵箱xuehr1998@163.com）

針對自動引導(dǎo)車（AGV）在自動化集裝箱碼頭（ACT）執(zhí)行任務(wù)過程中的電量問題，提出基于改進(jìn)的非支配排序遺傳算法-Ⅱ（NSGA-Ⅱ）的考慮AGV充電策略的集成調(diào)度。首先，在岸橋、場橋和AGV集成調(diào)度模式下，考慮AGV在不同作業(yè)狀態(tài)下的耗電量，并建立以最小化作業(yè)完工時間和總耗電量為目標(biāo)的多目標(biāo)混合規(guī)劃模型；其次，為提高傳統(tǒng)NSGA-Ⅱ的性能，設(shè)計自適應(yīng)NSGA-Ⅱ，并將所提算法與CPLEX求解器、NSGA-Ⅱ和多目標(biāo)粒子群優(yōu)化（MOPSO）算法進(jìn)行性能對比；最后，設(shè)計AGV不同充電策略并對設(shè)備數(shù)量配比進(jìn)行實驗研究。算法對比實驗結(jié)果表明：相較于傳統(tǒng)NSGA-Ⅱ算法，自適應(yīng)NSGA-Ⅱ?qū)﹄p目標(biāo)的優(yōu)化分別提升了2.8%和2.63%。利用自適應(yīng)NSGA-Ⅱ進(jìn)行的充電策略和設(shè)備數(shù)量配比實驗的結(jié)果表明：增加AGV充電次數(shù)能夠減少AGV的充電時間，且調(diào)整設(shè)備數(shù)量配比至3∶3∶9和3∶7∶3時，場橋和AGV的時間利用率分別達(dá)到最高。可見，AGV充電策略及設(shè)備數(shù)量配比對碼頭多設(shè)備集成調(diào)度有一定影響。

自動化集裝箱碼頭；自動引導(dǎo)車；充電策略；碼頭集成調(diào)度；自適應(yīng)非支配排序遺傳算法-Ⅱ；耗電量

0 引言

隨著經(jīng)濟(jì)全球化進(jìn)程不斷推進(jìn)，各經(jīng)濟(jì)體間的跨國貿(mào)易量迅猛增加。自動化集裝箱碼頭（Automated Container Terminal， ACT）為提高自身競爭力，需要不斷提高裝卸效率。自動引導(dǎo)車（Automated Guided Vehicle， AGV）因綠色、安全和效率高等特點(diǎn)成為ACT常見的水平運(yùn)輸設(shè)備。與傳統(tǒng)的水平運(yùn)輸設(shè)備相比，AGV作為一種蓄電池供電的設(shè)備，在運(yùn)輸過程中隨時間變化不間斷地消耗電量；因此，在進(jìn)行多設(shè)備協(xié)調(diào)調(diào)度時，需要考慮AGV的充電過程以保證設(shè)備有足夠的電量完成運(yùn)輸任務(wù)，避免在運(yùn)輸過程中出現(xiàn)AGV停車、擁堵碼頭等情況。

隨著AGV在ACT的廣泛使用，學(xué)者們加深了對AGV與其他水平設(shè)備集成調(diào)度的研究。Liu等［1］分析了卸載模式下AGV排隊行為對岸橋和AGV集成調(diào)度的影響，指出岸橋數(shù)與AGV能耗成正比，與AGV平均排隊時間成反比；范厚明等［2］基于AGV續(xù)航時間、雙小車岸橋中轉(zhuǎn)平臺容量和堆場緩沖支架容量等約束條件，研究雙小車岸橋與AGV聯(lián)合調(diào)度下岸橋和AGV的最優(yōu)配置；Zhao等［3］研究自動化岸橋（Automated Quay Crane， AQC）和AGV的協(xié)同調(diào)度，考慮AGV轉(zhuǎn)運(yùn)平臺的容量限制，設(shè)計了兩階段禁忌算法進(jìn)行求解；周玉清等［4］研究雙循環(huán)策略下跨運(yùn)車和岸橋的聯(lián)合調(diào)度，考慮岸橋緩存區(qū)容量、安全時間等約束，設(shè)計了基于貪婪算法的響應(yīng)性禁忌搜索算法，并對設(shè)備配比進(jìn)行了實驗分析。Yang等［5］研究岸橋、AGV和軌道式龍門起重機(jī)（Automated Rail-Mounted Gantry， ARMG）這3種運(yùn)輸工具的集成調(diào)度，提出基于防止路徑擁堵的Bi-level遺傳算法，能夠有效地緩解AGV的路徑擁堵問題并減少船舶在港裝卸時間；Jonker等［6］研究裝卸同步作業(yè)模式下岸橋、場橋和AGV綜合調(diào)度問題，分別采用提出的改進(jìn)模擬退火算法和分支定界算法進(jìn)行求解，獲得了更好的集成調(diào)度方案；Zhang等［7］提出AGV在雙循環(huán)模式下與場橋、岸橋的聯(lián)合調(diào)度，以最小化AGV等待時間為目標(biāo)，設(shè)計帶懲罰函數(shù)的混合粒子群算法進(jìn)行求解，并證明了該調(diào)度模式的有效性；陳崢嶸［8］建立岸橋、AGV和自動堆垛機(jī)（Automatic Stacking Crane， ASC）的集成調(diào)度與AGV路徑規(guī)劃優(yōu)化問題的雙層規(guī)劃模型，以降低作業(yè)產(chǎn)生的成本、減小能耗。

隨著調(diào)度研究的不斷深入，AGV在運(yùn)輸過程中的電量約束變得不可忽略，國內(nèi)外學(xué)者開始研究AGV充電約束。吳洪明等［9］考慮AGV空重載的電量消耗差異和非線性充電的特點(diǎn)，確定在機(jī)會充電的模式下AGV的最佳機(jī)會充電區(qū)間；Sweda等［10］考慮充電次數(shù)和充電電量范圍對電池壽命的影響，通過對比不同充電站設(shè)立規(guī)則，建立兩階段啟發(fā)式算法求解問題；周小凡等［11］只考慮卸船作業(yè)，設(shè)置不同的AGV任務(wù)初始電量和充電結(jié)束條件，采用多頻次充電的方式減少AGV在充電站排隊等待充電的時間和任務(wù)完工時間；張亞琦等［12］在垂岸式堆場布局下，以AGV電池續(xù)航能力為約束考慮AGV充電過程對AGV實際作業(yè)的影響；趙濤等［13］在固定換電閾值情況下，綜合考慮AGV換電站數(shù)和容量的限制，建立AGV的調(diào)度和充電的雙層耦合模型；陳琿等［14］提出AGV的充電策略會極大程度影響設(shè)備完工時間；傅正堂等［15］在AGV電量非飽和狀態(tài)下，優(yōu)化裝卸同步模式下的AGV作業(yè)調(diào)度；謝旦嵐等［16］提出以離線充電為主在線充電為輔的充電策略，通過優(yōu)化AGV數(shù)量配比提高AGV工作效率。

綜上所述，現(xiàn)階段較少深入研究多設(shè)備調(diào)度與AGV充電過程之間的關(guān)系，在考慮集成調(diào)度時忽略AGV需要充電的要求，或者在已知作業(yè)順序的情況下研究AGV充電過程，少部分研究在實驗時考慮了AGV空重載耗電不同和充電閾值等因素；因此在研究過程中通常忽略AGV充電過程，而無法進(jìn)一步優(yōu)化調(diào)度。因此，本文分析設(shè)備集成調(diào)度和AGV充電過程的內(nèi)在關(guān)聯(lián)，建立同時考慮AGV調(diào)度和充電的模型，研究AGV充電策略、設(shè)備數(shù)量配比對耗電量、設(shè)備利用率和設(shè)備完工時間的影響，并優(yōu)化AGV充電策略。

本文以岸橋、場橋和AGV的集成調(diào)度為研究對象，在岸橋和場橋作業(yè)分配已知但作業(yè)順序未知的情況下，考慮AGV的電量約束，首先，以最小化AGV最大完工時間和總耗電量為目標(biāo)，建立考慮AGV充電過程的設(shè)備集成調(diào)度的多目標(biāo)混合規(guī)劃模型。其次，設(shè)計自適應(yīng)非支配排序遺傳算法-Ⅱ（Non-dominated Sorting Genetic Algorithm-Ⅱ， NSGA-Ⅱ），通過算例對比分析驗證算法和模型的可行性。最后，通過算例數(shù)值分析，討論AGV充電范圍、AGV數(shù)、岸橋數(shù)對集成調(diào)度的影響。

1 問題描述

ACT的實際布局如圖1所示。碼頭作業(yè)區(qū)域可以劃分為岸橋作業(yè)區(qū)、AGV作業(yè)區(qū)和堆場作業(yè)區(qū)這3個部分：岸橋作業(yè)區(qū)進(jìn)行岸橋的裝卸載集裝箱作業(yè)和AGV與岸橋的交接箱作業(yè)；AGV在AGV作業(yè)區(qū)進(jìn)行集裝箱的運(yùn)輸和充電作業(yè)；在堆場作業(yè)區(qū)場橋進(jìn)行集裝箱的堆垛作業(yè)和AGV與場橋的交接箱作業(yè)。

對于出口箱作業(yè)，場橋從堆場抓取出口箱后在交換區(qū)與AGV交接，AGV將出口箱運(yùn)送至相應(yīng)的岸橋位置并等待岸橋作業(yè)，直至岸橋抓取箱任務(wù)后AGV執(zhí)行下一任務(wù)；對于進(jìn)口箱作業(yè)，岸橋?qū)⑦M(jìn)口箱從船舶放至AGV，AGV裝載進(jìn)口箱運(yùn)輸至交換區(qū)，等待場橋作業(yè)，直至場橋抓取箱任務(wù)AGV執(zhí)行下一任務(wù)。

由于本文研究裝卸同步的情況，因此需要考慮前后任務(wù)性質(zhì)不同時設(shè)備的作業(yè)時間，避免出現(xiàn)各設(shè)備的作業(yè)時間沖突問題。以岸橋為例，若兩個任務(wù)的作業(yè)性質(zhì)相反，如先裝后卸，需要往返于靠陸側(cè)和靠海側(cè)執(zhí)行任務(wù)，因此需要計算兩任務(wù)之間岸橋的移動時間；相似地，場橋在執(zhí)行兩個性質(zhì)相同的任務(wù)時移動時間也需要計算。

2 模型建立

2.1　模型假設(shè)

1）不考慮AGV在碼頭運(yùn)行過程中出現(xiàn)的路徑?jīng)_突情況。

2）空重載不同情況下AGV行駛速度相同但耗電量不同，不考慮AGV等待時消耗的電量。

3）碼頭充電站數(shù)為1且不考慮AGV在充電站的排隊行為。

2.2　符號定義和模型建立

集合和參數(shù)、變量說明如表1、2所示。

表1參數(shù)說明

Tab.1　Parameters description

表2變量說明

Tab.2　Variable description

目標(biāo)函數(shù)式（1）（2）分別表示本文的兩個目標(biāo)函數(shù)——最小化AGV最大完工時間和最小化AGV總耗電量：

式（3）～（8）表示岸橋、場橋和AGV執(zhí)行集裝箱作業(yè)時，每個任務(wù)能且僅能被執(zhí)行一次。特別地，當(dāng)AGV執(zhí)行完作業(yè)任務(wù)后執(zhí)行充電任務(wù)，則充電任務(wù)為確定的任務(wù)。

式（9）（10）表示AGV、岸橋和場橋有且僅有一個開始任務(wù)和結(jié)束任務(wù)。

式（11）～（14）對岸橋、場橋和AGV的任務(wù)流進(jìn)行約束。

式（15）表示每個任務(wù)有且僅由一輛AGV執(zhí)行，式（16）表示AGV不能連續(xù)執(zhí)行兩個充電任務(wù)。

式（17）（18）表示岸橋或場橋開始執(zhí)行任務(wù)的時刻不早于AGV到達(dá)設(shè)備指定位置的時刻；式（19）（20）表示對岸橋和場橋執(zhí)行任務(wù)的起始時間進(jìn)行約束。

式（21）表示AGV執(zhí)行裝載任務(wù)時，到達(dá)岸橋時刻應(yīng)不早于它離開場橋時刻與它在任務(wù)節(jié)點(diǎn)間運(yùn)輸集裝箱時間之和；式（22）表示AGV執(zhí)行卸載任務(wù)時，到達(dá)場橋時刻應(yīng)不早于它離開岸橋時刻與它在任務(wù)節(jié)點(diǎn)間運(yùn)輸集裝箱時間之和；式（23）（24）表示如果岸橋或場橋連續(xù)執(zhí)行任務(wù)和，那么岸橋或場橋開始執(zhí)行任務(wù)的時刻不早于岸橋或場橋結(jié)束執(zhí)行任務(wù)的時刻加上設(shè)備在兩任務(wù)執(zhí)行位置之間的移動時間。

式（25）表示AGV在結(jié)束充電任務(wù)后執(zhí)行作業(yè)任務(wù)且作業(yè)任務(wù)為進(jìn)口箱任務(wù)時，AGV到達(dá)岸橋時刻與AGV到達(dá)充電站時刻之間的關(guān)系；反之，式（26）表示若后繼作業(yè)任務(wù)為出口箱任務(wù)，AGV到達(dá)場橋時刻與AGV到達(dá)充電站時刻之間的關(guān)系。

式（27）（28）表示由同一AGV執(zhí)行的兩個相鄰作業(yè)任務(wù)之間開始工作時間約束。

AGV電量約束 式（29）表示AGV完成作業(yè)任務(wù)時的剩余電量大于安全閾值，反之前往充電；式（30）～（31）表示兩個任務(wù)之間的開始電量的約束。

式（32）表示若AGV在完成任務(wù)后前往充電站充電，則到達(dá)充電站的時刻不早于AGV完成任務(wù)的時刻加上AGV移動至充電站的時間。

總耗電量約束 式（33）（34）表示兩個相連任務(wù)之間的總耗電量約束。

3 算法設(shè)計

NSGA-Ⅱ是由Deb等［17］提出用于求解多目標(biāo)優(yōu)化問題的算法。該算法是在傳統(tǒng)遺傳算法的基礎(chǔ)上增加快速非支配排序、擁擠度計算等環(huán)節(jié)，對初始化種群進(jìn)行非支配排序和遺傳操作產(chǎn)生下一代種群，并采用精英保留策略，將父代和生成的子代混合后形成新種群進(jìn)行計算，重復(fù)以上操作直至循環(huán)結(jié)束。但由于交叉概率和變異概率是固定的，可能會破壞優(yōu)良個體或潛在優(yōu)良個體，降低了下一代個體的質(zhì)量，從而降低了算法結(jié)果質(zhì)量。在操作過程中引入自適應(yīng)函數(shù)，隨著個體適應(yīng)度值的變化，能夠動態(tài)的調(diào)整算子大小，更大概率地保留優(yōu)良個體。

3.1　染色體編碼和解碼

3.1.1編碼

由于考慮作業(yè)的工作順序和AGV車輛調(diào)度，每個個體設(shè)置4條染色體，染色體編碼如圖2所示。染色體的長度表示任務(wù)數(shù)。

圖2　染色體編碼

3.1.2解碼

假設(shè)現(xiàn)有裝卸作業(yè)任務(wù)10個、2臺岸橋、3輛AGV和2臺場橋，岸橋和場橋的作業(yè)分配已知。初始化種群如圖2所示，則岸橋和場橋的初始作業(yè)順序如下：

岸橋①：7→4→0→8→9 岸橋②：6→3→5→2→1

場橋①：9→7→1→5→3 場橋②：2→6→8→4→0

如圖2所示，第3行中的任務(wù)對應(yīng)第4行中的，則表示任務(wù)由第臺AGV執(zhí)行，如第3行中任務(wù)8對應(yīng)第4行中的2，則任務(wù)8由第2臺AGV執(zhí)行，且根據(jù)第4行得知任務(wù)8為第2臺AGV的第一個任務(wù)，AGV的初始作業(yè)分配和順序如下所示：

AGV0：0→4→6→9

AGV1：1→2→5

AGV2：8→3→7

3.2　染色體修復(fù)

遺傳過程在解碼之前，需要對染色體進(jìn)行修復(fù)操作。一是因為在初始化染色體種群時，沒有對各編碼位置進(jìn)行約束，可能存在非可行個體；二是在經(jīng)過交叉、變異等遺傳操作后，也可能產(chǎn)生非可行個體，因此對染色體進(jìn)行修復(fù)是十分必要的。修復(fù)染色體的偽代碼如算法1所示。

算法1 染色體修復(fù)流程。

輸入 個體；

輸出 修復(fù)后個體。

1） 對染色體進(jìn)行解碼并獲得任務(wù)在每個設(shè)備上的工作序列agv，qc，yc

2） Forinagv：

3） Forinagv：

4） 獲得任務(wù)和任務(wù)在岸橋、場橋和AGV的執(zhí)行順序0，1，2和0，1，2

5） 基于agv的工作調(diào)度，判斷任務(wù)和任務(wù)在岸橋的工作順序是否需要修復(fù)

6） If （1-1）（0-0）<0或（2-2）（0-0）<0：

7） 基于agv的工作序列修復(fù)qc，yc

8） 更新染色體

3.3　自適應(yīng)交叉、變異概率

本文基于Srinivas等［18］提出的自適應(yīng)遺傳算法，對自適應(yīng)函數(shù)進(jìn)行改進(jìn)使它能夠優(yōu)化多目標(biāo)算法，自適應(yīng)如式（35）（36）所示：

3.4　交叉操作

為了避免在對工作序列進(jìn)行交叉操作后出現(xiàn)個別任務(wù)重復(fù)和缺失的情況，對表示工作序列的染色體采用順序交叉的方式，對表示任務(wù)分配的染色體采用兩點(diǎn)交叉的方式。

3.4.1順序交叉

以岸橋作業(yè)順序為例，根據(jù)自適應(yīng)交叉概率選中兩個染色體父代1、父代2，在兩條染色體上隨機(jī)生成不相鄰的兩個交叉點(diǎn)，以父代1為例，首先生成子代1，子代1被選中的基因的位置與父代1相同；其次，找到父代2中基因所在位置，再將其余基因按順序放入子代1中，子代2同理可得，如圖3所示。

圖3　染色體順序交叉

3.4.2兩點(diǎn)交叉

對于表達(dá)AGV作業(yè)分配的染色體，采用兩點(diǎn)交叉方式。先得到隨機(jī)生成的兩個交叉點(diǎn)，再交叉父代1和父代2兩點(diǎn)之間的基因片段生成子代1和子代2，其中子代1產(chǎn)生過程如圖4所示。

圖4　染色體兩點(diǎn)交叉

3.5　變異操作

變異操作與交叉操作相似，首先，根據(jù)自適應(yīng)變異概率選中父代染色體；其次，隨機(jī)生成兩個變異點(diǎn)；最后交叉兩個變異點(diǎn)位置對應(yīng)的基因，如圖5所示。

圖5　染色體變異

3.6　算法流程

自適應(yīng)NSGA-Ⅱ的具體流程如圖6所示，其中表示當(dāng)前種群迭代次數(shù)，表示最大迭代次數(shù)。

圖6　自適應(yīng)NSGA-Ⅱ的流程

4 算例分析

4.1　算例設(shè)計

本文以ACT實際布局為參考，對岸橋、場橋和充電站的位置進(jìn)行適當(dāng)修改，在Windows 64系統(tǒng)中使用Python 3.8檢驗?zāi)Ｐ秃退惴ǖ目尚行浴?/p>

已知岸橋和場橋的作業(yè)分配、作業(yè)裝卸性質(zhì)采用均勻分布隨機(jī)生成，且裝卸比和設(shè)備任務(wù)比保持在1∶1。岸橋數(shù)為3，堆場數(shù)為5，充電站數(shù)為1，AGV的最大電池容量參考文獻(xiàn)［19］中設(shè)為200 Ah。

本文設(shè)計以下3個實驗：實驗1對比CPLEX求解模型得出的精確解與NSGA-Ⅱ［17］、自適應(yīng)NSGA-Ⅱ［18］、多目標(biāo)粒子群優(yōu)化（Multi-Objective Particle Swarm Optimization， MOPSO）算法［20］得出的近似解，驗證模型的有效性；實驗2利用自適應(yīng)NSGA-Ⅱ，對不同充電策略下AGV最大完工時間、總耗電量和充電時間進(jìn)行對比并分析不同參數(shù)下各充電策略的優(yōu)劣；實驗3研究場橋和AGV數(shù)量配比變化對設(shè)備時間利用率的影響。

4.2　性能分析

為使AGV在小規(guī)模實驗中執(zhí)行充電任務(wù)，在此實驗中對參數(shù)進(jìn)行適當(dāng)調(diào)整，以驗證模型的可行性，設(shè)備參數(shù)源于文獻(xiàn)［21-22］，表3為相關(guān)參數(shù)設(shè)置。

表3相關(guān)參數(shù)

Tab.3　Related parameters

本文設(shè)置6組實驗，任務(wù)數(shù)設(shè)置為10、15、20，AGV數(shù)設(shè)置3、4、6。由于CPLEX無法求解多目標(biāo)問題，因此在利用CPLEX求解時以AGV最大完工時間為目標(biāo)。表4為CPLEX、自適應(yīng)NSGA-Ⅱ、NSGA-Ⅱ和MOPSO算法運(yùn)行10次的平均求解結(jié)果，其中f1和f2分別表示最大完工時間和AGV耗電量的平均值，time表示4種求解方法的平均運(yùn)行時間。表5為4種算法在目標(biāo)值上的差距絕對值對比表，其中GAP1、GAP3和GAP5分別表示自適應(yīng)NSGA-Ⅱ與CPLEX、NSGA-Ⅱ和MOPSO算法在f1目標(biāo)值上的差距絕對值，GAP2、GAP4和GAP6分別表示它們在f2目標(biāo)值上的差距絕對值。

表4算法求解目標(biāo)值及運(yùn)行時間結(jié)果

Tab.4　Objective solution results and running time of algorithms

注：*表示運(yùn)行時間為3 600 s時CPLEX得出的一個可行解。

首先對運(yùn)行時間和結(jié)果進(jìn)行分析。如表4、5所示，當(dāng)任務(wù)數(shù)較少時，自適應(yīng)NSGA-Ⅱ的結(jié)果最優(yōu)，CPLEX的求解結(jié)果較差于NSGA-Ⅱ的結(jié)果，當(dāng)任務(wù)數(shù)增大時，NSGA-Ⅱ得出的f1和f2值逐漸低于CPLEX求解器得出的值，而自適應(yīng)NSGA-Ⅱ仍然優(yōu)于前二者，且自適應(yīng)NSGA-Ⅱ與NSGA-Ⅱ之間的差距變大。當(dāng)任務(wù)數(shù)從10增長到20時，MOPSO算法的實驗結(jié)果始終最差。實驗結(jié)果表明，自適應(yīng)NSGA-Ⅱ求解得出的f1目標(biāo)值分別優(yōu)于NSGA-Ⅱ和MOPSO算法2.80%和24.03%；而自適應(yīng)NSGA-Ⅱ?qū)2目標(biāo)值相較于NSGA-Ⅱ和MOPSO算法提升較小，分別為2.63%和14.46%。從運(yùn)行時間看，CPLEX的運(yùn)算時間隨任務(wù)數(shù)的增加呈倍數(shù)增長。當(dāng)任務(wù)數(shù)從10增加到15時，CPLEX的運(yùn)算時間增加了723.9 s，當(dāng)任務(wù)數(shù)為20時，在3 600 s內(nèi)CPLEX無法得出最優(yōu)解；而自適應(yīng)NSGA-Ⅱ運(yùn)算時間隨著任務(wù)數(shù)的增加變化幅度較小，且運(yùn)算時間最少。

表5算法求解目標(biāo)值差距對比

Tab.5　Comparison of difference between algorithm results

注：基礎(chǔ)數(shù)據(jù)由任務(wù)數(shù)/AGV數(shù)組成。

其次對多目標(biāo)算法的帕累托最優(yōu)解集進(jìn)行分析。圖7為NSGA-Ⅱ、自適應(yīng)NSGA-Ⅱ和MOPSO這3種算法某次運(yùn)行實驗5得出的帕累托最優(yōu)解。如圖7所示，可以看出自適應(yīng)NSGA-Ⅱ的帕累托前沿更靠近原點(diǎn)且解更優(yōu)，其次是NSGA-Ⅱ，最優(yōu)解集最差的是MOPSO算法。根據(jù)解的聚集情況，自適應(yīng)NSGA-Ⅱ的解更密集，而NSGA-Ⅱ和MOPSO算法得出的最優(yōu)解較分散。

圖7　3種算法運(yùn)行實驗5某次得出的帕累托最優(yōu)解集

綜上所述，與NSGA-Ⅱ、CPLEX求解器和MOPSO算法相比，自適應(yīng)NSGA-Ⅱ在運(yùn)算時間、計算結(jié)果和帕累托最優(yōu)解集等方面在解決本文問題上具有較大的優(yōu)勢。

4.3　實驗研究

AGV作為一種電池供電的運(yùn)輸設(shè)備，在執(zhí)行任務(wù)的過程中需要及時進(jìn)行充電以避免出現(xiàn)擁堵現(xiàn)象，因此AGV充電策略至關(guān)重要。對AGV充電策略進(jìn)行研究時，充電和結(jié)束充電時間點(diǎn)是最重要的兩個特征，合理的充電策略能夠提高AGV工作效率，降低能耗。為研究AGV充電范圍和設(shè)備數(shù)量配置對集裝箱整個作業(yè)過程的影響，設(shè)置兩組實驗。

實驗一 AGV充電策略影響分析。

實驗一對安全閾值（）和最大可充電池容量（）進(jìn)行參數(shù)設(shè)計并實驗，分別從最大電池容量的［10%，40%］、［70%，100%］組合設(shè)計16種充電策略進(jìn)行實驗，并對實驗結(jié)果從AGV時間利用率、AGV充電時間等幾個指標(biāo)進(jìn)行分析，計算公式如式（37）所示：

由圖8所示，AGV耗電量隨的增加而增加，隨的增加而減少。

圖8　AGV耗電量變化

如圖9（a）和圖10所示，當(dāng)從10%增加到40%時，AGV平均單次充電時間減少，使得AGV前往充電站的次數(shù)增加，充電時間占比在此情況下呈增加趨勢。如圖9（b）和圖11所示，當(dāng)從70%增加到100%時，AGV平均單次充電時間增加，AGV在充電站停留的時間增加，因此AGV能夠在單次充電后完成更多的集裝箱任務(wù)，從而降低了AGV的充電次數(shù)，使得充電時間占比減少。

圖9　Changes of AGV charging time proportion

圖10　充電時間和充電次數(shù)隨g變化的情況

圖11　充電時間和充電次數(shù)隨Pu變化的情況

綜上可以看出AGV充電時間占比與充電次數(shù)呈正比、與單次充電時間呈反比。相較于充電時間，充電次數(shù)對所研究問題下的AGV整體充電時間影響更大，降低AGV充電次數(shù)能夠減少AGV充電時間占比，提高AGV時間利用率。

實驗二 設(shè)備數(shù)量配比影響分析。

實驗二設(shè)置任務(wù)數(shù)為90，岸橋數(shù)為3，改變岸橋和AGV數(shù)，對岸橋、場橋和AGV數(shù)配置進(jìn)行研究。實驗的AGV數(shù)分別為3、6和9，場橋數(shù)從［3，7］依次分組。通過岸橋時間利用率、場橋時間利用率和AGV時間利用率分析對比，研究岸橋、場橋和AGV配比對集裝箱作業(yè)任務(wù)的影響，公式如式（38）所示：

其中：設(shè)備利用率表示各設(shè)備的時間利用率，工作時長和總等待時長分別表示設(shè)備工作總時長和設(shè)備總等待時長。實驗結(jié)果如圖12、13所示。

如圖12所示，最大完工時間隨著AGV數(shù)的增加而減少，但場橋數(shù)的變化對最大工時間的影響較小。在AGV總耗能方面：當(dāng)場橋數(shù)小于4時，場橋數(shù)的增加對AGV耗電量的影響不大；但當(dāng)場橋數(shù)大于4時，AGV耗電量增幅增大。這是因為隨著場橋數(shù)的增加，AGV執(zhí)行單位集裝箱任務(wù)時行駛的距離增加，耗電量增加。

圖12　完工時間和AGV耗電量變化

如圖13（a）所示，隨著AGV數(shù)的增加，岸橋利用率增加。這是因為當(dāng)AGV數(shù)增加時，岸橋等待AGV運(yùn)輸集裝箱任務(wù)的時間縮短，岸橋?qū)嶋H操作時間增加，又因為總完工時間變化不大，則岸橋時間利用率提高，而場橋數(shù)的增加對岸橋的時間利用率的影響較小。

如圖13（b）所示，隨著場橋數(shù)的增加，場橋等待時間增加，實際操作時間減少，場橋利用率降低。同時，AGV數(shù)的增加使得場橋的利用率增加，這是因為AGV增多后，岸橋的等待時間減少，從而提高了時間利用率。

如圖13（c）所示，AGV數(shù)的增加反而使得AGV利用率降低。這是因為當(dāng)任務(wù)數(shù)一定時，AGV數(shù)增加使得AGV在裝卸設(shè)備下等待的容易產(chǎn)生擁堵，從而增加了AGV的等待時間，使得AGV利用率降低。場橋數(shù)的增加使得相同的任務(wù)量下，AGV可以將集裝箱任務(wù)運(yùn)往其他場橋，從而減少AGV在裝卸設(shè)備的等待時間。

圖13　設(shè)備時間利用率變化

綜上所述，場橋利用率隨著AGV數(shù)的增加而增加，隨著場橋數(shù)的增加而降低；AGV利用率隨著AGV數(shù)的增加而降低，隨著岸橋數(shù)的增加而降低。岸橋、場橋和AGV的不同數(shù)量配比影響了設(shè)備的時間利用率，當(dāng)岸橋∶場橋∶AGV=3∶3∶9時，場橋的時間利用率最大，為40.69%；當(dāng)岸橋∶場橋∶AGV=3∶7∶3時AGV的時間利用率最大，為93.2%。

5 結(jié)語

在裝卸同步的情況下，本文在岸橋、場橋和AGV的集成調(diào)度研究中考慮AGV的電量約束，研究了設(shè)備的作業(yè)序列和AGV調(diào)度問題，考慮AGV不同狀態(tài)下的耗電量、AGV安全閾值等因素，建立多目標(biāo)混合規(guī)劃模型最小化AGV最大完工時間和總耗電量。為了減小AGV充電過程對集成調(diào)度的影響，本文提出自適應(yīng)NSGA-Ⅱ，并設(shè)計實驗驗證了模型的可行性。其次，本文對安全閾值和最大電池容量分別組合設(shè)計實驗，研究AGV不同充電策略對總耗電量、AGV充電時間等的影響，得出了較優(yōu)的充電策略。最后，研究AGV和岸橋數(shù)變化對各設(shè)備實際利用率的影響。實驗結(jié)果表明：1）AGV充電時間受AGV充電次數(shù)的影響，可以通過減小安全閾值或增大最大電池容量減少AGV充電時間和耗電量；2）AGV數(shù)與岸橋數(shù)會影響設(shè)備的時間利用率，增加AGV數(shù)能夠提高場橋和岸橋的時間利用率，而場橋數(shù)的增加也能夠提高AGV的時間利用率。因此，AGV的數(shù)量配置和電池充電閾值能提高設(shè)備工作效率、降低耗電量。

然而，本文沒有考慮岸橋和場橋在船舶或堆場的翻箱問題；未考慮充電站數(shù)量配置、容量限制等問題對AGV充電及調(diào)度的影響，當(dāng)充電站數(shù)大于1時，AGV的充電策略都值得進(jìn)行進(jìn)一步研究。

[1] LIU D， GE Y-E. Modeling assignment of quay cranes using queueing theory for minimizing CO2emission at a container terminal ［J］. Transportation Research Part D： Transport and Environment， 2018， 61（A）： 140-151.

[2] 范厚明，岳麗君，李蕩，等.考慮路徑?jīng)_突的AGV配置與調(diào)度優(yōu)化［J］.運(yùn)籌與管理，2020，29（5）：43-51（FAN H M， YUE L J， LI D， et al. Optimization of AGV dispatching and configuration considering path conflict ［J］. Operations Research and Management Science， 2020， 29（5）： 43-51.）

[3] ZHAO Q R， JI S W， GUO D， et al. Research on cooperative scheduling of automated quayside cranes and automatic guided vehicles in automated container terminal ［J］. Mathematical Problems in Engineering， 2019， 2019： No. 6574582.

[4] 周玉清，韓曉龍. 雙循環(huán)策略下岸橋與跨運(yùn)車的聯(lián)合調(diào)度［J］.計算機(jī)應(yīng)用： 2023，43（2）：645-653.（ZHOU Y Q， HAN X L. Joint operation of quay crane and straddle carrier under double-cycle strategy ［J］.Journal of Computer Applications，2023，43（2）： 645-653.）

[5] YANG Y， ZHONG M， DESSOUKY Y， et al. An integrated scheduling method for AGV routing in automated container terminals ［J］. Computers & Industrial Engineering， 2018， 126： 482-493.

[6] JONKER T， DUINKERKEN M B， YORKE-SMITH N， et al. Coordinated optimization of equipment operations in a container terminal ［J］. Flexible Services and Manufacturing Journal， 2019， 33： 281-311.

[7] ZHANG H，QI L， LUAN W， et al. Double-cycling AGV scheduling considering uncertain crane operational time at container terminals［J］. Applied Sciences，2022，12： No.4820.

[8] 陳錚榮. 考慮AGV無沖突路徑規(guī)劃的自動化集裝箱碼頭集成調(diào)度［D］.北京：北京交通大學(xué)， 2020：5-7.（CHEN Z R .Integrated scheduling considering AGV conflict-free path planning in automated container terminal ［D］. Beijing： Beijing Jiaotong University， 2020：5-7.）

[9] 吳洪明，鄒夢艷. 考慮電池電量約束的自動化碼頭AGV調(diào)度［J］. 起重運(yùn)輸機(jī)械， 2021（3）： 47-52.（WU H M， ZOU M Y. AGV scheduling of automated terminal considering battery power constraints ［J］. Hoisting and Conveying Machinery， 2021（3）： 47-52.）

[10] SWEDA T M， DOLINSKAYA I S， KLABJAN D. Optimal recharging policies for electric vehicles ［J］. Transportation Science， 2017， 51（2）： 457-479.

[11] 周小凡，萇道方，余芳，等. 考慮充電和等待時間的集裝箱碼頭AGV調(diào)度［J］. 上海海事大學(xué)學(xué)報， 2019， 40（3）： 1-5，13.（ZHOU X F， CHANG D F， YU F， et al. Scheduling of AGV in container terminals considering charging and waiting time ［J］. Journal of Shanghai Maritime University， 2019， 40（3）： 1-5，13.）

[12] 張亞琦，楊斌，胡志華，等.自動化碼頭AGV充電與作業(yè)的集成調(diào)度研究［J］. 計算機(jī)工程與應(yīng)用， 2017， 53（18）： 257-262，270.（ZHANG Y Q，YANG B， HU Z H，et al. Research of AGV charging and job integrated scheduling at automated container terminal ［J］. Computer Engineering and Applications， 2017， 53（18）： 257-262，270.）

[13] 趙濤，梁承姬，胡筱淵，等. 自動化集裝箱碼頭AGV調(diào)度與換電雙層模型求解［J］. 大連理工大學(xué)學(xué)報， 2021， 61（6）： 623-633.（ZHAO T， LIANG C J，HU X Y，et al. Solution of AGV scheduling and battery exchange two-layer model for automated container terminal ［J］. Journal of Dalian University of Technology， 2021， 61（6）： 623-633.）

[14] 陳琿，韓曉龍. 考慮充電策略的自動化碼頭AGV調(diào)度［J］. 上海海事大學(xué)學(xué)報， 2021， 42（2）： 20-25，74.（CHEN H，HAN X L. AGV scheduling of automated terminals considering charging strategy ［J］. Journal of Shanghai Maritime University， 2021， 42（2）： 20-25，74.）

[15] 傅正堂，胡志華，宗康. 集裝箱碼頭AGV電量非飽和狀態(tài)下的調(diào)度優(yōu)化［J］. 大連海事大學(xué)學(xué)報， 2017， 43（3）： 58-62.（FU Z T ，HU Z H，ZONG K. Scheduling optimization of container terminal AGV under electricity unsaturation condition ［J］. Journal of Dalian Maritime University， 2017， 43（3）： 58-62.）

[16] 謝旦嵐，郭笛，紀(jì)媛，等.自動化碼頭運(yùn)輸設(shè)備充電策略優(yōu)化的仿真研究［J］. 系統(tǒng)仿真學(xué)報， 2020， 32（10）： 1927-1935.（XIE D L，GUO D， JI Y，et al. Simulation research on optimization of AGV charging strategy for automated terminal ［J］. Journal of System Simulation， 2020， 32（10）： 1927-1935.）

[17] DEB K， PRATAP A， AGARWAL S， et al. A fast and elitist multiobjective genetic algorithm： NSGA?Ⅱ ［J］. IEEE Transactions on Evolutionary Computation， 2002， 6（2）： 182-197.

[18] SRINIVAS M， PATNAIK L M. Adaptive probabilities of crossover and mutation in genetic algorithms ［J］. IEEE Transactions on Systems， Man， and Cybernetics， 1994， 24（4）： 656-667.

[19] ZHAN X， XU L， ZHANG J， et al. Study on AGVs battery charging strategy for improving utilization ［J］. Procedia CIRP， 2019， 81： 558-563.

[20] COELLO C A C， PULIDO G T， LECHUGA M S. Handling multiple objectives with particle swarm optimization ［J］. IEEE Transactions on Evolutionary Computation， 2004，8（3）： 256-279.

[21] CHEN J C， CHEN T-L， TENG Y-C. Meta-model based simulation optimization for automated guided vehicle system under different charging mechanisms ［J］. Simulation Modelling Practice and Theory， 2021， 106： 102208.

[22] SCHNEIDER M， STENGER A， GOEKE D. The electric vehicle-routing problem with time windows and recharging stations ［J］. Transportation Science， 2014， 48（4）： 500-520.

Integrated scheduling considering automated guided vehicle charging strategy based on improved NSGA-Ⅱ

XUE Hairong*， HAN Xiaolong

（，，201306，）

Aiming at the power problem of Automated Guided Vehicle （AGV） in the process of performing tasks in Automated Container Terminal （ACT）， an integrated scheduling considering AGV charging strategy based on improved Non-dominated Sorting Genetic Algorithm-Ⅱ （NSGA-Ⅱ） was proposed. Firstly， considering the power consumption of AGV under different operating statuses in the integrated scheduling mode of quay crane， yard crane and AGV， a multi-objective mixed programming model with the goal of minimizing the completion time and total power consumption was established. Secondly， to improve the performance of the traditional NSGA-Ⅱ， an adaptive NSGA-Ⅱ was designed and compared with CPLEX solver and Multi-Objective Partical Swarm Optimization （MOPSO） algorithm on performance. Finally， different charging strategies and equipment number ratios of AGV were designed for experimental research. The experimental results of algorithm comparison show that the solution results of the adaptive NSGA-Ⅱ are improved by 2. 80% and 2. 63% respectively on the two objectives proposed compared with NSGA-Ⅱ. The experimental results of applying the adaptive NSGA-Ⅱ to study the ratio of charging strategies and equipment number ratios show that increasing AGV charging number can reduce AGV charging time， and adjusting the ratio of the equipment number to 3：3：9 and 3：7：3 lead to the highest time utilization of yard crane and AGV respectively. It can be seen that the AGV charging strategy and equipment number ratio can influence the terminal integrated scheduling with multiple equipment.

Automated Container Terminal (ACT); Automated Guided Vehicle (AGV); charging strategy; terminal integrated scheduling; adaptive Non-dominated Sorting Genetic Algorithm-Ⅱ (NSGA-Ⅱ); power consumption

TP301.6； TP391.9

A

1001-9081（2023）12-3848-08

10.11772/j.issn.1001-9081.2022121923

2023?01?04；

2023?03?21；

2023?03?22。

薛海蓉（1998—），女，浙江溫州人，碩士研究生，主要研究方向：港口運(yùn)營與管理；韓曉龍（1978—），男，山東濰坊人，副教授，博士，主要研究方向：物流與供應(yīng)鏈管理。

XUE Hairong， born in 1998， M. S. candidate. Her research interests include port operation and management.

HAN Xiaolong， born in 1978， Ph. D.， associate professor. His research interests include logistics and supply chain management.