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

薛海蓉，韓曉龍

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

薛海蓉*，韓曉龍

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

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

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

0 引言

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

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

隨著調(diào)度研究的不斷深入，AGV在運(yùn)輸過程中的電量約束變得不可忽略，國(guó)內(nèi)外學(xué)者開始研究AGV充電約束。吳洪明等［9］考慮AGV空重載的電量消耗差異和非線性充電的特點(diǎn)，確定在機(jī)會(huì)充電的模式下AGV的最佳機(jī)會(huì)充電區(qū)間；Sweda等［10］考慮充電次數(shù)和充電電量范圍對(duì)電池壽命的影響，通過對(duì)比不同充電站設(shè)立規(guī)則，建立兩階段啟發(fā)式算法求解問題；周小凡等［11］只考慮卸船作業(yè)，設(shè)置不同的AGV任務(wù)初始電量和充電結(jié)束條件，采用多頻次充電的方式減少AGV在充電站排隊(duì)等待充電的時(shí)間和任務(wù)完工時(shí)間；張亞琦等［12］在垂岸式堆場(chǎng)布局下，以AGV電池續(xù)航能力為約束考慮AGV充電過程對(duì)AGV實(shí)際作業(yè)的影響；趙濤等［13］在固定換電閾值情況下，綜合考慮AGV換電站數(shù)和容量的限制，建立AGV的調(diào)度和充電的雙層耦合模型；陳琿等［14］提出AGV的充電策略會(huì)極大程度影響設(shè)備完工時(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)度時(shí)忽略AGV需要充電的要求，或者在已知作業(yè)順序的情況下研究AGV充電過程，少部分研究在實(shí)驗(yàn)時(shí)考慮了AGV空重載耗電不同和充電閾值等因素；因此在研究過程中通常忽略AGV充電過程，而無法進(jìn)一步優(yōu)化調(diào)度。因此，本文分析設(shè)備集成調(diào)度和AGV充電過程的內(nèi)在關(guān)聯(lián)，建立同時(shí)考慮AGV調(diào)度和充電的模型，研究AGV充電策略、設(shè)備數(shù)量配比對(duì)耗電量、設(shè)備利用率和設(shè)備完工時(shí)間的影響，并優(yōu)化AGV充電策略。

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

1 問題描述

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

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

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

2 模型建立

2.1　模型假設(shè)

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

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

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

2.2　符號(hào)定義和模型建立

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

表1參數(shù)說明

Tab.1　Parameters description

表2變量說明

Tab.2　Variable description

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

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

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

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

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

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

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

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

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

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

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

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

3 算法設(shè)計(jì)

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

3.1　染色體編碼和解碼

3.1.1編碼

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

圖2　染色體編碼

3.1.2解碼

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

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

場(chǎng)橋①：9→7→1→5→3 場(chǎng)橋②：2→6→8→4→0

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

AGV0：0→4→6→9

AGV1：1→2→5

AGV2：8→3→7

3.2　染色體修復(fù)

遺傳過程在解碼之前，需要對(duì)染色體進(jìn)行修復(fù)操作。一是因?yàn)樵诔跏蓟旧w種群時(shí)，沒有對(duì)各編碼位置進(jìn)行約束，可能存在非可行個(gè)體；二是在經(jīng)過交叉、變異等遺傳操作后，也可能產(chǎn)生非可行個(gè)體，因此對(duì)染色體進(jìn)行修復(fù)是十分必要的。修復(fù)染色體的偽代碼如算法1所示。

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

輸入 個(gè)體；

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

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

2） Forinagv：

3） Forinagv：

4） 獲得任務(wù)和任務(wù)在岸橋、場(chǎng)橋和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)遺傳算法，對(duì)自適應(yīng)函數(shù)進(jìn)行改進(jìn)使它能夠優(yōu)化多目標(biāo)算法，自適應(yīng)如式（35）（36）所示：

3.4　交叉操作

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

3.4.1順序交叉

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

圖3　染色體順序交叉

3.4.2兩點(diǎn)交叉

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

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

3.5　變異操作

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

圖5　染色體變異

3.6　算法流程

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

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

4 算例分析

4.1　算例設(shè)計(jì)

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

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

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

4.2　性能分析

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

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

Tab.3　Related parameters

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

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

Tab.4　Objective solution results and running time of algorithms

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

首先對(duì)運(yùn)行時(shí)間和結(jié)果進(jìn)行分析。如表4、5所示，當(dāng)任務(wù)數(shù)較少時(shí)，自適應(yīng)NSGA-Ⅱ的結(jié)果最優(yōu)，CPLEX的求解結(jié)果較差于NSGA-Ⅱ的結(jié)果，當(dāng)任務(wù)數(shù)增大時(shí)，NSGA-Ⅱ得出的f1和f2值逐漸低于CPLEX求解器得出的值，而自適應(yīng)NSGA-Ⅱ仍然優(yōu)于前二者，且自適應(yīng)NSGA-Ⅱ與NSGA-Ⅱ之間的差距變大。當(dāng)任務(wù)數(shù)從10增長(zhǎng)到20時(shí)，MOPSO算法的實(shí)驗(yàn)結(jié)果始終最差。實(shí)驗(yàn)結(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)行時(shí)間看，CPLEX的運(yùn)算時(shí)間隨任務(wù)數(shù)的增加呈倍數(shù)增長(zhǎng)。當(dāng)任務(wù)數(shù)從10增加到15時(shí)，CPLEX的運(yùn)算時(shí)間增加了723.9 s，當(dāng)任務(wù)數(shù)為20時(shí)，在3 600 s內(nèi)CPLEX無法得出最優(yōu)解；而自適應(yīng)NSGA-Ⅱ運(yùn)算時(shí)間隨著任務(wù)數(shù)的增加變化幅度較小，且運(yùn)算時(shí)間最少。

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

Tab.5　Comparison of difference between algorithm results

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

其次對(duì)多目標(biāo)算法的帕累托最優(yōu)解集進(jìn)行分析。圖7為NSGA-Ⅱ、自適應(yīng)NSGA-Ⅱ和MOPSO這3種算法某次運(yùn)行實(shí)驗(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)行實(shí)驗(yàn)5某次得出的帕累托最優(yōu)解集

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

4.3　實(shí)驗(yàn)研究

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

實(shí)驗(yàn)一 AGV充電策略影響分析。

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

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

圖8　AGV耗電量變化

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

圖9　Changes of AGV charging time proportion

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

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

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

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

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

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

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

圖12　完工時(shí)間和AGV耗電量變化

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

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

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

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

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

5 結(jié)語

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

然而，本文沒有考慮岸橋和場(chǎng)橋在船舶或堆場(chǎng)的翻箱問題；未考慮充電站數(shù)量配置、容量限制等問題對(duì)AGV充電及調(diào)度的影響，當(dāng)充電站數(shù)大于1時(shí)，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ì)算機(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ī)劃的自動(dòng)化集裝箱碼頭集成調(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] 吳洪明，鄒夢(mèng)艷. 考慮電池電量約束的自動(dòng)化碼頭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] 周小凡，萇道方，余芳，等. 考慮充電和等待時(shí)間的集裝箱碼頭AGV調(diào)度［J］. 上海海事大學(xué)學(xué)報(bào)， 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] 張亞琦，楊斌，胡志華，等.自動(dòng)化碼頭AGV充電與作業(yè)的集成調(diào)度研究［J］. 計(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] 趙濤，梁承姬，胡筱淵，等. 自動(dòng)化集裝箱碼頭AGV調(diào)度與換電雙層模型求解［J］. 大連理工大學(xué)學(xué)報(bào)， 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] 陳琿，韓曉龍. 考慮充電策略的自動(dòng)化碼頭AGV調(diào)度［J］. 上海海事大學(xué)學(xué)報(bào)， 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é)報(bào)， 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ì)媛，等.自動(dòng)化碼頭運(yùn)輸設(shè)備充電策略優(yōu)化的仿真研究［J］. 系統(tǒng)仿真學(xué)報(bào)， 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)營(yíng)與管理；韓曉龍（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.