基于改進NSGA-Ⅱ的考慮自動引導車充電策略的集成調度

薛海蓉，韓曉龍

基于改進NSGA-Ⅱ的考慮自動引導車充電策略的集成調度

薛海蓉*，韓曉龍

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

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

自動化集裝箱碼頭；自動引導車；充電策略；碼頭集成調度；自適應非支配排序遺傳算法-Ⅱ；耗電量

0 引言

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

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

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

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

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

1 問題描述

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

對于出口箱作業，場橋從堆場抓取出口箱后在交換區與AGV交接，AGV將出口箱運送至相應的岸橋位置并等待岸橋作業，直至岸橋抓取箱任務后AGV執行下一任務；對于進口箱作業，岸橋將進口箱從船舶放至AGV，AGV裝載進口箱運輸至交換區，等待場橋作業，直至場橋抓取箱任務AGV執行下一任務。

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

2 模型建立

2.1　模型假設

1）不考慮AGV在碼頭運行過程中出現的路徑沖突情況。

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

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

2.2　符號定義和模型建立

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

表1參數說明

Tab.1　Parameters description

表2變量說明

Tab.2　Variable description

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

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

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

式（11）～（14）對岸橋、場橋和AGV的任務流進行約束。

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

式（17）（18）表示岸橋或場橋開始執行任務的時刻不早于AGV到達設備指定位置的時刻；式（19）（20）表示對岸橋和場橋執行任務的起始時間進行約束。

式（21）表示AGV執行裝載任務時，到達岸橋時刻應不早于它離開場橋時刻與它在任務節點間運輸集裝箱時間之和；式（22）表示AGV執行卸載任務時，到達場橋時刻應不早于它離開岸橋時刻與它在任務節點間運輸集裝箱時間之和；式（23）（24）表示如果岸橋或場橋連續執行任務和，那么岸橋或場橋開始執行任務的時刻不早于岸橋或場橋結束執行任務的時刻加上設備在兩任務執行位置之間的移動時間。

式（25）表示AGV在結束充電任務后執行作業任務且作業任務為進口箱任務時，AGV到達岸橋時刻與AGV到達充電站時刻之間的關系；反之，式（26）表示若后繼作業任務為出口箱任務，AGV到達場橋時刻與AGV到達充電站時刻之間的關系。

式（27）（28）表示由同一AGV執行的兩個相鄰作業任務之間開始工作時間約束。

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

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

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

3 算法設計

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

3.1　染色體編碼和解碼

3.1.1編碼

由于考慮作業的工作順序和AGV車輛調度，每個個體設置4條染色體，染色體編碼如圖2所示。染色體的長度表示任務數。

圖2　染色體編碼

3.1.2解碼

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

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

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

如圖2所示，第3行中的任務對應第4行中的，則表示任務由第臺AGV執行，如第3行中任務8對應第4行中的2，則任務8由第2臺AGV執行，且根據第4行得知任務8為第2臺AGV的第一個任務，AGV的初始作業分配和順序如下所示：

AGV0：0→4→6→9

AGV1：1→2→5

AGV2：8→3→7

3.2　染色體修復

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

算法1 染色體修復流程。

輸入 個體；

輸出 修復后個體。

1） 對染色體進行解碼并獲得任務在每個設備上的工作序列agv，qc，yc

2） Forinagv：

3） Forinagv：

4） 獲得任務和任務在岸橋、場橋和AGV的執行順序0，1，2和0，1，2

5） 基于agv的工作調度，判斷任務和任務在岸橋的工作順序是否需要修復

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

7） 基于agv的工作序列修復qc，yc

8） 更新染色體

3.3　自適應交叉、變異概率

本文基于Srinivas等［18］提出的自適應遺傳算法，對自適應函數進行改進使它能夠優化多目標算法，自適應如式（35）（36）所示：

3.4　交叉操作

為了避免在對工作序列進行交叉操作后出現個別任務重復和缺失的情況，對表示工作序列的染色體采用順序交叉的方式，對表示任務分配的染色體采用兩點交叉的方式。

3.4.1順序交叉

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

圖3　染色體順序交叉

3.4.2兩點交叉

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

圖4　染色體兩點交叉

3.5　變異操作

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

圖5　染色體變異

3.6　算法流程

自適應NSGA-Ⅱ的具體流程如圖6所示，其中表示當前種群迭代次數，表示最大迭代次數。

圖6　自適應NSGA-Ⅱ的流程

4 算例分析

4.1　算例設計

本文以ACT實際布局為參考，對岸橋、場橋和充電站的位置進行適當修改，在Windows 64系統中使用Python 3.8檢驗模型和算法的可行性。

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

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

4.2　性能分析

為使AGV在小規模實驗中執行充電任務，在此實驗中對參數進行適當調整，以驗證模型的可行性，設備參數源于文獻［21-22］，表3為相關參數設置。

表3相關參數

Tab.3　Related parameters

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

表4算法求解目標值及運行時間結果

Tab.4　Objective solution results and running time of algorithms

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

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

表5算法求解目標值差距對比

Tab.5　Comparison of difference between algorithm results

注：基礎數據由任務數/AGV數組成。

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

圖7　3種算法運行實驗5某次得出的帕累托最優解集

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

4.3　實驗研究

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

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

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

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

圖8　AGV耗電量變化

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

圖9　Changes of AGV charging time proportion

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

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

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

實驗二 設備數量配比影響分析。

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

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

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

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

如圖13（a）所示，隨著AGV數的增加，岸橋利用率增加。這是因為當AGV數增加時，岸橋等待AGV運輸集裝箱任務的時間縮短，岸橋實際操作時間增加，又因為總完工時間變化不大，則岸橋時間利用率提高，而場橋數的增加對岸橋的時間利用率的影響較小。

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

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

圖13　設備時間利用率變化

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

5 結語

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

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

[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] 范厚明，岳麗君，李蕩，等.考慮路徑沖突的AGV配置與調度優化［J］.運籌與管理，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] 周玉清，韓曉龍. 雙循環策略下岸橋與跨運車的聯合調度［J］.計算機應用： 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無沖突路徑規劃的自動化集裝箱碼頭集成調度［D］.北京：北京交通大學， 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調度［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調度［J］. 上海海事大學學報， 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充電與作業的集成調度研究［J］. 計算機工程與應用， 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調度與換電雙層模型求解［J］. 大連理工大學學報， 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調度［J］. 上海海事大學學報， 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電量非飽和狀態下的調度優化［J］. 大連海事大學學報， 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］. 系統仿真學報， 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—），女，浙江溫州人，碩士研究生，主要研究方向：港口運營與管理；韓曉龍（1978—），男，山東濰坊人，副教授，博士，主要研究方向：物流與供應鏈管理。

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.