考慮電池包數(shù)量的自動(dòng)化集裝箱碼頭多AGV調(diào)度優(yōu)化

收稿日期：2022-03-08；修回日期：2022-04-25" 基金項(xiàng)目：國家自然科學(xué)基金面上項(xiàng)目（71972128）；國家重點(diǎn)研發(fā)計(jì)劃資助項(xiàng)目（2019YFB170164）

作者簡介：許彭錦（1998-），男，江西九江人，碩士研究生，主要研究方向?yàn)樽詣?dòng)化集裝箱碼頭AGV的充電優(yōu)化（x3522423643@sina.com）；梁承姬（1970-），女，教授，博士，主要研究方向?yàn)槲锪飨到y(tǒng)運(yùn)作計(jì)劃與優(yōu)化口岸物流流程模擬與重組、港口布局優(yōu)化與模擬、港口安全工程等.

摘 要：

針對自動(dòng)化集裝箱碼頭自動(dòng)引導(dǎo)小車（automated guided vehicle，AGV）的實(shí)際換電特性，為了降低AGV的總?cè)蝿?wù)完成時(shí)間和換電總時(shí)間，合理規(guī)劃換電站內(nèi)的電池包數(shù)量，建立了雙層規(guī)劃模型。首先考慮AGV的電池續(xù)航、空/重載SOC變化特性和不同剩余電量與速度變化，以降低AGV的總?cè)蝿?wù)完成時(shí)間為目標(biāo)，構(gòu)建考慮換電的多AGV集裝箱任務(wù)調(diào)度上層模型。在此基礎(chǔ)上，為了合理規(guī)劃換電站內(nèi)的電池包數(shù)量，考慮自動(dòng)化碼頭中換電站的實(shí)際電池包選取原則和換電流程，對換電站和電池包的選擇進(jìn)行決策，以降低換電總時(shí)間為目標(biāo)，構(gòu)建換電電池包配置下層模型。最后通過遺傳算法分別對小規(guī)模和大規(guī)模算例進(jìn)行求解。算例結(jié)果表明，此雙層規(guī)劃模型能夠有效地減少總?cè)蝿?wù)完成時(shí)間和換電總時(shí)間，提高了6.46%的AGV利用率，減少了23.1%的換電站電池包數(shù)量。

關(guān)鍵詞：自動(dòng)化集裝箱碼頭；自動(dòng)牽引車；遺傳算法；電池包數(shù)量

中圖分類號：U691.3"" 文獻(xiàn)標(biāo)志碼：A"" 文章編號：1001-3695（2022）09-014-2653-07

doi： 10.19734/j.issn.1001-3695.2022.03.0085

Research on multi-AGV scheduling optimization of automated container terminal considering number of battery packs

Xu Pengjin， Liang Chengji

（Logistics Research Center， Shanghai Maritime University， Shanghai 201306， China）

Abstract：According to the actual power exchange characteristics of AGV in automated container terminal， this paper built a two-level programming model to reduce the total task completion time and power exchange time of the AGV，and reasonably planed the number of battery packs in the power exchange station. Firstly，considering the battery life，air and heavy load SOC variation characteristics and different residual power and speed changes of AGV，in order to reduce the total task completion time of AGV， it built an upper-level model for multi-AGV container task scheduling considering power exchange. On this basis，in order to reasonably plan the number of battery packs in the power exchange station，considered the actual battery pack selection principle and power exchange process of the power exchange station in the automatic wharf，made decisions on the selection of power exchange station and battery pack，and built the lower level model of power exchange battery pack configuration with the goal of reducing the total power exchange time. Finally，it solved small-scale and large-scale examples by genetic algorithm. The example results show that the two-level programming model can effectively reduce the total task completion time and the total power exchange time，improve the utilization rate of AGV by 6.46% and reduce the number of battery packs in the power exchange station by 23.1%.

Key words：automated container terminal; automated guided vehicle; genetic algorithm; number of battery packs

0 引言

在連接海—陸物流運(yùn)輸?shù)恼麄€(gè)過程中，集裝箱碼頭起到至關(guān)重要的作用。隨著全球經(jīng)濟(jì)一體化的全面發(fā)展，“地球村”概念深入落實(shí)，傳統(tǒng)集裝箱碼頭的運(yùn)輸效率高、安全性好等優(yōu)勢已經(jīng)無法滿足全球經(jīng)濟(jì)發(fā)展的需要。而自動(dòng)化集裝箱碼頭相比于傳統(tǒng)的集裝箱碼頭，其最大特點(diǎn)就是實(shí)現(xiàn)了集裝箱的裝卸作業(yè)、堆場的裝卸作業(yè)和水平運(yùn)輸?shù)淖詣?dòng)化智能化操作。在整個(gè)碼頭和堆場的作業(yè)區(qū)域中不再有人的參與，而是通過由電力驅(qū)動(dòng)的AGV小車來對集裝箱進(jìn)行裝卸搬運(yùn)作業(yè)，因此，純電力驅(qū)動(dòng)的AGV的作業(yè)效率很大程度上決定著整個(gè)集裝箱碼頭的運(yùn)作效率。AGV的電量狀態(tài)可用SOC（state of charge）來描述，即電池使用一段時(shí)間或長期擱置不用后的剩余可放電電量與其完全充電狀態(tài)的電量的比值，常用百分?jǐn)?shù)表示。Kim等人［1］對于AGV的調(diào)度問題采用了一種時(shí)間事件發(fā)生的方法，以最小AGV工作時(shí)間和最小船舶延誤時(shí)間為目標(biāo)來對AGV進(jìn)行任務(wù)分配。Schneider等人［2］建立一個(gè)電池交換站網(wǎng)絡(luò)，提出了一個(gè)動(dòng)態(tài)規(guī)劃模型來輔助最優(yōu)收費(fèi)決策，模型的結(jié)果能夠有效地根據(jù)動(dòng)態(tài)的電價(jià)來決策是否給電池充電。Xiang等人［3］提出了一種考慮電池管理的自動(dòng)化集裝箱碼頭性能評估的嵌套半開放排隊(duì)網(wǎng)絡(luò)模型，在模型近似解的基礎(chǔ)上進(jìn)一步優(yōu)化了系統(tǒng)的資源分配和布局設(shè)計(jì)。石楠路等人［4］為了降低AGV的換電過程對其調(diào)度的影響并提高AGV的工作效率，構(gòu)建了考慮AGV換電過程的混合整數(shù)調(diào)度模型。周小凡等人［5］考慮了AGV電池的續(xù)航能力和重/空載的耗電差異等約束，建立以最小化AGV任務(wù)完成時(shí)間為目標(biāo)的AGV調(diào)度模型。張亞綺等人［6］根據(jù)電力驅(qū)動(dòng)的AGV的充電需求和運(yùn)輸特性，考慮垂直堆場布局和AGV充電過程對實(shí)際作業(yè)的影響，以最大化AGV充電利用率、最小化最末任務(wù)完成時(shí)間以及最小化AGV空載時(shí)間為目標(biāo)，建立AGV的作業(yè)調(diào)度模型。吳洪明等人［7］為了提高自動(dòng)化集裝箱碼頭AGV的作業(yè)效率，考慮AGV的空/重載耗電特性以及充電的非線性特征，建立以總?cè)蝿?wù)完成時(shí)間最短為目標(biāo)的AGV調(diào)度模型。丁一等人［8］為解決多載AGV的動(dòng)態(tài)調(diào)度問題，考慮AGV的裝載能力和充電后的續(xù)航能力，采用周期與事件混合驅(qū)動(dòng)的滾動(dòng)時(shí)域的優(yōu)化策略，構(gòu)建AGV動(dòng)態(tài)作業(yè)調(diào)度的混合整數(shù)規(guī)劃模型。鄭亞紅等人［9］為了減少AGV在換電站中的排隊(duì)等待時(shí)間，構(gòu)建AGV作業(yè)與換電的協(xié)同調(diào)度優(yōu)化模型，并設(shè)計(jì)遺傳算法求解模型。傅正堂等人［10］對AGV電量在非飽和狀態(tài)下的放電特性進(jìn)行研究，對該問題建立數(shù)學(xué)模型并用CPLEX求解器求解。范厚明等人［11］采用兩階段建模方法，分別建立數(shù)學(xué)模型，設(shè)計(jì)枚舉法和遺傳算法來對雙小車岸橋和AGV進(jìn)行聯(lián)合配置。宋紹京等人［12］為解決合理規(guī)劃AGV數(shù)量，以AGV工作效率最大化為目標(biāo)，結(jié)合車間大小和AGV自身特性等因素建立數(shù)學(xué)模型，通過實(shí)際應(yīng)用場景，驗(yàn)證了模型的有效性。黃宇超［13］從換電站的布局設(shè)計(jì)、換電站內(nèi)的設(shè)備設(shè)施布局以及AGV的調(diào)度系統(tǒng)等方面進(jìn)行分析，設(shè)計(jì)新的布局方案，通過對比分析，驗(yàn)證了方案的有效性。樊陸彬等人［14］從不確定性的角度出發(fā)，分別建立集卡分派子模型和集卡配置子模型，并將完工時(shí)刻和集卡數(shù)量作為公用設(shè)計(jì)變量連接兩個(gè)子模型，通過算例求解該耦合模型，使得延誤成本和集卡數(shù)量得到有效減少，驗(yàn)證了模型的有效性。陳香玲等人［15］為了提高AGV在物流中心的工作效率，考慮AGV在搬運(yùn)工作過程中的電量消耗和其充電特性，提出以AGV剩余電量和包裹時(shí)間窗等約束條件和最小化分揀作業(yè)周期為目標(biāo)的混合整數(shù)規(guī)劃（MIP）模型和約束規(guī)劃（CP）模型，通過實(shí)例分析，驗(yàn)證了模型性能的有效性。

綜上可知，在對自動(dòng)化集裝箱碼頭AGV調(diào)度的研究中，大多數(shù)是針對AGV的換電模式和策略，對影響AGV換電的因素考慮還不夠全面。因此，本文在已有研究基礎(chǔ)上，首先考慮AGV的電池續(xù)航及空/重載SOC變化特性和不同剩余電量下的空/重載速度變化，提高電池包利用率，以降低AGV的總?cè)蝿?wù)完成時(shí)間為目標(biāo)，構(gòu)建考慮換電因素的AGV集裝箱任務(wù)調(diào)度的上層模型。為了對集裝箱任務(wù)調(diào)度過程中產(chǎn)生的換電任務(wù)進(jìn)行調(diào)度，且合理規(guī)劃換電站內(nèi)的電池包數(shù)量，本文考慮自動(dòng)化碼頭中換電站的實(shí)際電池包選取原則和換電流程，對換電站和電池包的選擇進(jìn)行決策，以降低換電總時(shí)間為目標(biāo)，構(gòu)建換電電池包配置下層模型，與上層模型構(gòu)成解決集裝箱任務(wù)調(diào)度和換電任務(wù)調(diào)度的雙層模型。

1 問題描述

圖1為垂直式自動(dòng)化集裝箱碼頭的實(shí)際布局示意圖，整個(gè)自動(dòng)化碼頭可分為自動(dòng)化堆場、AGV工作區(qū)域和岸橋工作區(qū)域三個(gè)區(qū)域，而換電站以及換電站配套設(shè)施需要較大的占地面積，一般會(huì)布局在AGV行車主干道的盡頭兩側(cè)。在自動(dòng)化集裝箱碼頭中，通過利用純電驅(qū)動(dòng)的AGV來對集裝箱進(jìn)行裝卸搬運(yùn)作業(yè)，即將不同的集裝箱搬運(yùn)至相應(yīng)的堆場緩存區(qū)和岸橋緩存區(qū)。

如圖1所示，在混合裝卸作業(yè)模式下，AGV小車此次的出口集裝箱任務(wù)的起點(diǎn)在堆場3，AGV行駛至堆場3處的交互區(qū)，從緩沖支架上取得出口集裝箱后，根據(jù)既定路線通過行車主干道，將此集裝箱運(yùn)送至對應(yīng)的岸橋門架小車處進(jìn)行集裝箱交接。若下一個(gè)進(jìn)口集裝箱的起點(diǎn)不在此岸橋的中轉(zhuǎn)平臺(tái)上，則空車行駛至進(jìn)口集裝箱所在中轉(zhuǎn)平臺(tái)的岸橋處，取得此進(jìn)口集裝箱后，將其運(yùn)送至對應(yīng)的終點(diǎn)堆場1處。

在完成一個(gè)集裝箱任務(wù)后，需要判斷AGV的剩余電量是否低于閾值，或者是否能夠完成下一個(gè)集裝箱任務(wù)。如果不能，則需要去換電站進(jìn)行換電任務(wù)作業(yè)；如果滿足，則繼續(xù)執(zhí)行集裝箱任務(wù)作業(yè)。此時(shí)還需要根據(jù)AGV自身的剩余電量來選擇不同的運(yùn)行速度，當(dāng)剩余電量較低時(shí)，為了提高電池的利用率，AGV的運(yùn)行速度將有所降低。

在實(shí)際換電站中，換電站的硬件設(shè)備主要是由換電機(jī)器人、充電機(jī)組和電池倉組成，電池包的更換流程為：當(dāng)需要換電的AGV駛向目標(biāo)換電站，從換電站的一端入口駛?cè)氲竭_(dá)指定的換電工位后，由換電機(jī)器人從電池倉中選取符合換電要求的電池包，對AGV進(jìn)行電池包更換，在目前洋山港四期自動(dòng)化碼頭中，換電站進(jìn)行一次更換電池包的平均操作時(shí)間為300 s；與此同時(shí)，充電機(jī)組將會(huì)對從AGV上更換下來的乏電電池包進(jìn)行充電；當(dāng)AGV更換好電池包后，從換電站的另一端駛出換電站，駛向下一任務(wù)的發(fā)箱位置，繼續(xù)搬運(yùn)執(zhí)行任務(wù)。

在圖2中，當(dāng)AGV產(chǎn)生換電需求時(shí)，首先會(huì)根據(jù)這一次去不同換電站換電的總時(shí)間判斷是去大換電站還是小換電站，緊接著執(zhí)行換電任務(wù)。當(dāng)AGV到達(dá)某換電站的換電工位時(shí)，換電機(jī)器人需要對電池包的選取作出決策，將滿電狀態(tài)和電池倉內(nèi)SOC最高的電池作為優(yōu)先選擇，由于換電站內(nèi)是采取邊換邊充的模式，即換電機(jī)器人選取電池包進(jìn)行換電的同時(shí)，充電機(jī)組會(huì)對換電站內(nèi)的電量不足的電池包進(jìn)行充電，這會(huì)存在一個(gè)最低允許換電電量Pv，即當(dāng)電池倉內(nèi)的所有電池SOC均小于Pv，則AGV需要等待有電池包充電至Pv，然后更換此電池包再駛出換電站，并且在換電機(jī)器人選擇SOC最高的電池包進(jìn)行換電作業(yè)時(shí)，如果可選擇的電池包有多個(gè)，則選取使用次數(shù)較多的那一個(gè)電池包進(jìn)行換電作業(yè)。

2 模型建立

2.1 上層AGV集裝箱任務(wù)調(diào)度模型

模型假設(shè)如下：

a）AGV初始電量為100%；

b）在作業(yè)過程中，不考慮設(shè)備故障以及碰撞等突發(fā)因素；

c）岸橋、場橋的每個(gè)裝卸任務(wù)的操作順序和操作時(shí)間已知；

d）所有集裝箱大小均為40英尺，一輛AGV一次裝載一個(gè)集裝箱。

本文上層模型使用的符號如表1所示。

xkij決策變量，若第k臺(tái)AGV在執(zhí)行任務(wù)i之后執(zhí)行任務(wù)j，則xkij=1，否則為0

模型建立如下：

min F（1）

s.t. F≥Zki" k∈K，i∈V（2）

∑i∈V0xkij=1" j∈V，k∈K（3）

∑j∈V′0xkij=1" j∈V，k∈K（4）

∑k∈K ∑i∈Vtxkij=1" j∈V（5）

∑k∈K ∑j∈Vtxkij=1" i∈V（6）

∑i∈Vxkih=∑j∈Vxkhj" h∈Vb∪Vt，k∈K（7）

edki=∑j∈VxkjiDji" k∈K，i∈V（8）

wki=qej-xkij·（zki+edki/s1）" k∈K， j∈Vt，i∈V

WWki k∈K，i∈Vk （9）

zkj=zki+xkij·（wkj+edkj/s1+fdkj/s2+ty+tq） k∈K， j∈Vt，i∈V

zki+xkij·（wki+afix+edki/s2） k∈K， j∈Vk，i∈Vt （10）

bkj=bbki+M（1-xkij）" k∈K，i∈V，j∈Vt（11）

bkj≤MC" k∈K， j∈Vb（12）

bbki=100%"""""""""" k∈K， i∈V0∪Vb

bki-r1edki/s1-r2fdi/s2-r3wki k∈K，i∈Vt （13）

∑iVkxkij=0 k∈K， j∈V（14）

∑i∈Vxkij≤s" k∈K， j∈Vk（15）

∑h∈Vtxkhi－∑h′∈Vtxkh′j≤0" k∈K;i， j∈Vk； j≤i（16）

s1ki=s1" 0lt;bki≤ps1

s1′ ps1lt;bki≤ps2

s1″ ps2lt;bki≤100%" k∈K，i∈Vt（17）

s2ki=s2" 0lt;bki≤ps1

s2′ ps1lt;bki≤ps2s2″ ps2lt;bki≤100% k∈K，i∈Vt（18）

xkij∈{0，1}" k∈K;i， j∈V（19）

Zkigt;0，fgt;0，bbkigt;0，bkigt;0，wki≥0，edki≥0" k∈K，i∈V（20）

式（1）為目標(biāo)函數(shù)，表示最小化最大完工時(shí)間；式（2）表示最終任務(wù)完成時(shí)間不小于任意任務(wù)的完成時(shí)間；式（3）（4）表示每臺(tái)AGV必須完成虛擬開始和虛擬結(jié)束任務(wù)；式（5）（6）表示每個(gè)任務(wù)僅有一個(gè)緊前和后繼任務(wù)；式（7）表示中間任務(wù)必須運(yùn)輸平衡，即輸入等于輸出；式（8）表示AGV執(zhí)行任務(wù)時(shí)的空駛距離；式（9）表示普通任務(wù)和換電任務(wù)等待時(shí)間的計(jì)算；式（10）表示普通任務(wù)和換電任務(wù)完成時(shí)間的計(jì)算；式（11）表示搬運(yùn)任務(wù)開始時(shí)AGV的剩余電量更新；式（12）表示換電任務(wù)開始時(shí)，AGV剩余電量不大于換電閾值；式（13）表示AGV普通任務(wù)和換電任務(wù)完成時(shí)的剩余電量更新，換電任務(wù)完成時(shí)電量為100%；式（14）表示AGV只能執(zhí)行屬于自己的n個(gè)虛擬換電任務(wù)；式（15）為一臺(tái)AGV的換電次數(shù)之和，不允許超過最多換電次數(shù)s；式（16）表示一臺(tái)AGV若換電i次，只能完成前i個(gè)換電任務(wù)；式（17）（18）為不同剩余電量區(qū)間下，AGV空重載的速度差異；式（19）（20）為變量的約束。

2.2 下層電池包配置模型

模型假設(shè)如下：

a）不考慮換電工位維護(hù)等因素；

b）每個(gè)換電站遵循先到先服務(wù)的原則；

c）電池倉內(nèi)電池初始電量均為100%；

d）每個(gè)換電工位同一時(shí)刻僅為一臺(tái)AGV更換電池包；

e）不考慮電池包使用壽命和成本的影響。

本文下層模型使用的符號如表2所示。

模型建立如下：

min F′（21）

s.t. F′=∑k∈K ∑u∈U（Ftuk－Stuk）（22）

∑t∈Tpukt=1" k∈K，u∈Uk（23）

∑k∈K ∑t∈T ∑u∈Uqtuzk=1" z∈Z（24）

Ftuk=（Lukt+DDukt/s2）·pukt" u∈Uk，k∈K，t∈T（25）

Atukt=Stuk+pukt·DDukt/s2" u∈Uk，t∈T，k∈K（26）

lltuzk=qtuzk·ldcctuz if ltuzk≥EC

qtuzk·EC if ltuzklt;EC" u∈Uk，t∈T，k∈K，z∈Z（27）

lldcctuz=qtuzkltuzk" u∈Uk，t∈T，k∈K，z∈Z（28）

ldcctuz=max{100%，（Ctu′ktz－Ltuktz）·ve} u∈Uk，t∈T，k∈K，z∈Z（29）

WWuktz≤max（0，Ltu′k′t－Atukt）"""""""""" if ltuzk≥EC

max（0，Ltu′k′t－Atukt）+qtuzk·（EC-ltuzk）/ve if ltuzklt;EC

t∈T，k，k′∈K，u∈Uk′，u′∈Uk′，z∈Z（30）

N+n≤M（31）

Ctuktz=pukt·qtuzk（Aukt+Wuktz） u∈Uk，t∈T，k∈K，z∈Z（32）

Ltuktz=Ctuktz+afix" u∈Uk，t∈T，k∈K，z∈Z（33）

pukt∈{0，1}" t∈T，k∈K，u∈Uk，（34）

qtuzk∈{0，1}" t∈T，k，∈K，u∈UK，z∈Z（35）

式（21）為目標(biāo)函數(shù)，表示最小化AGV總換電時(shí)間；式（22）表示AGV換電總時(shí)間的計(jì)算；式（23）表示一臺(tái)AGV一次換電只能選擇一個(gè)換電站；式（24）表示每一塊電池包每次換電任務(wù)只能服務(wù)一臺(tái)AGV；式（25）表示換電完成后到達(dá)后繼任務(wù)起點(diǎn)位置的時(shí)刻；式（26）表示到達(dá)換電站時(shí)刻，即本次換電指令產(chǎn)生時(shí)刻與駛向換電站空駛時(shí)間之和；式（27）表示換電后AGV電池包電量更新，即所選電池電量需大于最低允許換電電量EC；式（28）表示每次換電任務(wù)結(jié)束后，電池倉內(nèi)本次被用過的電池包電量的更新，更新為從AGV上換下來的電量不足的電池包電量；式（29）表示每次換電任務(wù)開始時(shí)，電池倉內(nèi)電池包的電量更新，即本次換電開始時(shí)間和上一次換電結(jié)束時(shí)間之差與充電機(jī)組充電速率的乘積；式（30）表示換電站等待時(shí)長的計(jì)算，若到達(dá)換電站時(shí)前一臺(tái)AGV尚未完成換電則排隊(duì)等待，若所選換電電池包電量低于最低換電電量時(shí)，則充電等待；式（31）表示大小換電站的電池初始總數(shù)量不得多于換電總次數(shù)；式（32）表示換電工位開始操作時(shí)刻的計(jì)算，即到達(dá)換電站時(shí)刻與排隊(duì)時(shí)長之和；式（33）表示電池包更換完成時(shí)刻，即換電開始時(shí)刻加上換電的操作時(shí)長；式（34）（35）為變量的約束。

3 遺傳算法

考慮換電過程和電池包數(shù)量的自動(dòng)化集裝箱碼頭的多AGV調(diào)度問題，在本質(zhì)上與多循環(huán)的VRP問題是相似的，也屬于NP-hard問題，此類問題的特點(diǎn)就是多循環(huán)、高度并發(fā)性以及容易陷入局部最優(yōu)，而遺傳算法恰好是一種能夠?qū)崿F(xiàn)高度并發(fā)以及全局搜索的全局優(yōu)化算法，具有很好的收斂性和魯棒性，并且遺傳算法還有靈活的編碼方式，可以實(shí)現(xiàn)實(shí)數(shù)編碼和二進(jìn)制編碼等，簡單有效的編碼規(guī)則能夠使其遺傳操作和種群更新的過程中產(chǎn)生更少的非法解，因此，本文采用遺傳算法來求解研究的問題，以獲得其近似最優(yōu)解。

3.1 染色體編碼

本文的遺傳算法編碼方式采用的是實(shí)數(shù)編碼，實(shí)數(shù)編碼能夠很直觀地用染色體來表達(dá)實(shí)際問題，圖3為上層AGV集裝箱任務(wù)調(diào)度模型的一條染色體編碼。可以看出整個(gè)染色體分為兩段，每段染色體上都有n個(gè)基因，n表示集裝箱任務(wù)的數(shù)量，前n個(gè)基因表示n個(gè)集裝箱任務(wù)的序號，后n個(gè)基因表示執(zhí)行這n個(gè)集裝箱任務(wù)對應(yīng)的AGV序號，即在2n個(gè)基因中，第i（i≤n）個(gè)基因表示的集裝箱任務(wù)序號是由第i+n個(gè)基因表示的AGV序號進(jìn)行作業(yè)的。

下層AGV換電調(diào)度模型的染色體編碼原理同上層模型。在圖4中，整個(gè)染色體分為前后兩段，前段染色體的基因值1表示小換電站，2表示大換電站。前后兩段染色體的長度為在上層調(diào)度模型中所有AGV產(chǎn)生的換電次數(shù)，后半段染色體的基因值表示換電站中的電池編號，圖4染色體中前后段的第一個(gè)基因值表示的是：在AGV產(chǎn)生的所有換電需求中，第一次執(zhí)行換電任務(wù)去小換電站，且在小換電站中換電機(jī)器人選擇2號電池包進(jìn)行換電作業(yè)。

3.2 遺傳操作

1）選擇

本文的雙層模型中，均采用的是輪盤賭選擇算子，具體的選擇步驟如下：

a）計(jì)算每個(gè)個(gè)體的適應(yīng)度值Fm；

b）計(jì)算每個(gè)個(gè)體遺傳到下一代的概率Pm；

c）計(jì)算出每個(gè)個(gè)體的累計(jì)概率Cm；

d）產(chǎn)生一個(gè)隨機(jī)數(shù)s∈（0，1］，如果Cm-1≤s≤Cm ，則第m個(gè)個(gè)體被選擇；

e）重復(fù)步驟d），直到種群數(shù)量等于初始種群數(shù)量。

2）交叉與變異

在上層模型中，采用的是兩點(diǎn)交叉和兩點(diǎn)變異的遺傳操作。

交叉過程為：選取兩條父代染色體M1和M2，在兩條父代染色體上隨機(jī)選取兩個(gè)交叉點(diǎn)r1、r2，將M1上兩個(gè)交叉點(diǎn)之間的染色體片段p1與M2上兩個(gè)交叉點(diǎn)之間的染色體片段p2進(jìn)行交叉互換，進(jìn)而得到兩條子代染色體m1和m2。但是，由于染色體前后兩段的基因值表示的實(shí)際意義不同，所以在交叉的時(shí)候不能跨段交叉，并且由于一個(gè)集裝箱只能被一臺(tái)AGV搬運(yùn)約束，所以在p1與p2交叉互換過后，片段中與染色體中重復(fù)的基因值需要更新為整條染色體缺少的基因值。具體的交叉過程如圖5所示。

兩點(diǎn)變異的具體過程為：在一條父代染色體上的前后兩段染色體中，分別隨機(jī)選取一個(gè)變異基因位置q1、q2，由于前段染色體表示集裝箱任務(wù)編號，后段染色體表示相對應(yīng)的AGV編號，且一臺(tái)AGV一次只能搬運(yùn)一個(gè)集裝箱，所以分別對在前后段兩個(gè)變異位置上的基因進(jìn)行集裝箱任務(wù)編號變異和AGV序號變異，從而得到兩條子代染色體。具體的變異過程如圖6所示。

下層模型的交叉變異的方式和上層模型中的基本相同，由于下層模型的染色體基因個(gè)數(shù)沒有上層模型的規(guī)模大，所以為了不破壞染色體的遺傳特性，下層模型的交叉和變異采取單點(diǎn)交叉和單點(diǎn)變異的遺傳操作。

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

本文構(gòu)建的雙層模型的目標(biāo)函數(shù)分別是最小化最大完工時(shí)間和最小化總換電時(shí)間，通過解碼染色體，最后一個(gè)集裝箱任務(wù)被完成的時(shí)間即為最大完工時(shí)間，換電完成時(shí)刻與換電需求產(chǎn)生時(shí)刻的差為一臺(tái)AGV的換電總時(shí)間，即換電總時(shí)間為駛向換電站的時(shí)間、等待換電的排隊(duì)時(shí)間、等待電池包充電的時(shí)間與駛出換電站到達(dá)后繼任務(wù)始點(diǎn)的時(shí)間之和。取兩者的倒數(shù)，分別作為上下層遺傳算法中的適應(yīng)度函數(shù)。

4 算例分析

4.1 參數(shù)設(shè)置

為了評估本文所建立的雙層模型的有效性，利用MATLAB軟件對以下算例進(jìn)行求解分析。設(shè)計(jì)100個(gè)集裝箱，五臺(tái)AGV的算例，對于每一個(gè)集裝箱任務(wù)的最早開始時(shí)間、起始位置和終止位置等屬性，如表3所示。設(shè)置種群規(guī)模NP=50，最大迭代次數(shù)M=100，在雙層遺傳算法中，上層交叉概率和變異概率分別為pc=0.7、pm=0.01，下層交叉概率和變異概率分別為PC=0.5、PM=0.01。設(shè)置AGV的換電SOC閾值為30%，當(dāng)AGV的SOC在（0，30%］，其空載運(yùn)行速度為2.5 m/s；當(dāng)AGV的SOC在［30%，60%］，其空載和重載兩種狀態(tài)的速度分別為3 m/s、2.5 m/s；當(dāng)SOC在［60%，100%］，其空/重載的速度分別為4 m/s、3 m/s，空載和重載狀態(tài)下每米耗電速率分別為0.01%、0.025%，當(dāng)AGV停車等待時(shí)，其每秒耗電速率為0.005%，且一共有兩個(gè)換電站，一大一小，分別位于AGV行車道的盡頭兩端，每個(gè)換電站設(shè)置一個(gè)換電工位，換電站—場橋—岸橋的距離如表4所示。場橋和岸橋執(zhí)行一次任務(wù)分別花費(fèi)90 s和120 s，每個(gè)換電站的換電機(jī)器人換電速率為300 s/次，大換電站中電池倉內(nèi)的初始電池包數(shù)量是30個(gè)，小換電站內(nèi)有15個(gè)，換電站內(nèi)采取的換電策略是邊換電，充電機(jī)邊充電，最低可換電電量Pv=60%，且參考對電動(dòng)公交車的研究，設(shè)置充電機(jī)的充電速率為：每充電1 min，電池包獲得8 min的續(xù)航時(shí)間。

4.2 小規(guī)模雙層模型結(jié)果分析

基于上述參數(shù)設(shè)置，將此規(guī)模的算例和相關(guān)參數(shù)代入遺傳算法進(jìn)行求解，上層模型的適應(yīng)度函數(shù)收斂過程如圖7所示，求解結(jié)果如表5所示。從得到近似最優(yōu)解中可知，此規(guī)模的算例中，上層模型的結(jié)果為：最大完工時(shí)間157 min，且期間只進(jìn)行了1次換電，此次換電發(fā)生在3號AGV的作業(yè)過程中。繼續(xù)運(yùn)行下層模型的代碼，得下層模型的結(jié)果為：此次換電去的是小換電站，換的是4號電池包，換電總時(shí)間為10.416 7 min。第3輛AGV的任務(wù)作業(yè)順序及時(shí)間甘特圖如圖8所示，可知3號AGV一共執(zhí)行了18個(gè)集裝箱任務(wù)，執(zhí)行了1個(gè)換電任務(wù)。

小規(guī)模算例驗(yàn)證了雙層模型的有效性后，將算例規(guī)模擴(kuò)大至集裝箱數(shù)量n=500，AGV的數(shù)量a=10，對雙層模型進(jìn)行遺傳算法求解可知，上層模型輸出的結(jié)果為：AGV最大完工時(shí)間為632.6 min，10臺(tái)AGV共進(jìn)行13次換電，且以3號AGV為例，其作業(yè)順序如表6所示，可知其在執(zhí)行第77和1號集裝箱任務(wù)后產(chǎn)生換電需求。

繼續(xù)運(yùn)行得出下層模型的運(yùn)行結(jié)果，其中，下層模型的適應(yīng)度函數(shù)進(jìn)化結(jié)果如圖9所示。下層模型中輸出的結(jié)果為：AGV換電總時(shí)間167.85 min，且每臺(tái)AGV的換電次數(shù)、換電需求產(chǎn)生時(shí)的時(shí)間、剩余電量、換電場所、換電電池包編號如表7所示。

在集裝箱數(shù)量n=500，AGV數(shù)量a=10的規(guī)模算例中，一共產(chǎn)生了13次換電需求。優(yōu)化前，13次換電需求需要13個(gè)電池包來滿足，而決策和約束電池包的選擇后，13次換電任務(wù)中，每次換電任務(wù)中換電機(jī)器人選擇的電池包編號以及大小換電站中的所有電池包的使用次數(shù)記錄如表8所示。

在表8中，AGV一共在小換電站進(jìn)行了8次換電，大換電站進(jìn)行了5次換電，其中1、2、6、20、22、38號電池包使用了1次，7號電池包使用了2次，3號電池包使用了3次。因此，在集裝箱數(shù)量為500個(gè)，AGV數(shù)量為10臺(tái)的規(guī)模算例中，一共產(chǎn)生了13次換電需求，優(yōu)化后，一共用到了10塊電池包，相比于優(yōu)化前需要的13塊電池包，電池包的數(shù)量減少了23.1%。

在上層模型中，通過考慮AGV空/重載耗電差異和不同剩余電量區(qū)間的空/重載速度差異來提高電池包的利用率，通過輸出的數(shù)據(jù)統(tǒng)計(jì)結(jié)果，優(yōu)化前后的換電需求產(chǎn)生時(shí)的電池利用率如圖10所示。可知優(yōu)化前產(chǎn)生14次換電，優(yōu)化后產(chǎn)生13次換電，總換電次數(shù)減少1次，優(yōu)化后的電池平均利用率為61.34%，優(yōu)化后的電池平均利用率為67.80%，電池平均利用率提升6.46%。

4.4 交叉率靈敏度分析

算例規(guī)模變大會(huì)影響染色體的長度，在染色體進(jìn)行交叉算子操作的時(shí)候，交叉率的大小會(huì)對代碼運(yùn)行結(jié)果產(chǎn)生不同程度的影響，如圖11所示。在不同的上層模型交叉率pc下，上層模型的代碼結(jié)果即AGV最大完工時(shí)間會(huì)產(chǎn)生相應(yīng)的變化，可知，當(dāng)上層模型交叉率pc=0.6時(shí)，結(jié)果最為理想。

在圖12中，設(shè)置不同的上下層交叉率pc和PC，得到下層模型的代碼運(yùn)行結(jié)果即AGV總換電時(shí)間，可知當(dāng)pc=0.6，PC=0.5時(shí)，下層模型的結(jié)果最為理想，因此，在代碼運(yùn)行的參數(shù)設(shè)置中，將上層模型交叉率pc設(shè)置為0.6，下層模型交叉率PC設(shè)置為0.5。

4.5 不同剩余電量的AGV速度靈敏度分析

在AGV進(jìn)行裝卸搬運(yùn)的過程中，結(jié)合實(shí)際碼頭運(yùn)作情況，AGV在不同的剩余電量狀態(tài)下，其空/重載時(shí)的運(yùn)行速度也是不同的。根據(jù)已有研究可知，AGV根據(jù)荷電狀態(tài)（SOC）分為三個(gè)區(qū)間：強(qiáng)制充電區(qū)間（0，30%］，即只進(jìn)行換電任務(wù)，只有空載速度；機(jī)會(huì)充電區(qū)間［30%，60%］，即可執(zhí)行換電任務(wù)也可執(zhí)行集裝箱任務(wù)；正常工作區(qū)間［60%，100%］，即只進(jìn)行集裝箱搬運(yùn)任務(wù)，且此區(qū)間的空/重載運(yùn)行速度大于機(jī)會(huì)充電區(qū)間。V0和V1分別為空/重載速度，由于空/重載的速度隨著剩余電量的減少而降低，并且其大小會(huì)影響最終完工時(shí)間，并且不能設(shè)置太高的速度，設(shè)置過高，則會(huì)導(dǎo)致電量消耗較快，增加換電次數(shù)，這與優(yōu)化最終完工時(shí)間背道而馳。因此本文設(shè)置五種方案如表9所示，來對各剩余電量區(qū)間的空/重載速度進(jìn)行靈敏度分析，能夠有效提高電池包的利用率。

對每種方案進(jìn)行10次代碼運(yùn)行，取平均值，最后得出五種方案下的AGV最大完工時(shí)間如圖13所示。從曲線圖中可知，方案2的運(yùn)行結(jié)果在五種方案中最優(yōu)，因此，對AGV根據(jù)自身不同的SOC速度參數(shù)設(shè)置時(shí)，設(shè)置SOC在［0，30%］時(shí)，空載速度為2.5 m/s，SOC在［30%，60%］時(shí)，空載和重載速度分別為3 m/s、2.5 m/s；當(dāng)SOC在［60%，100%］時(shí)，空載和重載的速度分別為4 m/s、3 m/s。

5 結(jié)束語

自動(dòng)化集裝箱碼頭的工作效率在很大程度上受到AGV的影響，本文在前人研究的基礎(chǔ)上，針對AGV裝卸搬運(yùn)作業(yè)過程中，考慮AGV的電池續(xù)航時(shí)長、空/重載SOC的變化特性以及不同剩余電量的空重載運(yùn)行速度差異，對AGV在換電站進(jìn)行電池包更換的過程中，考慮AGV產(chǎn)生的換電需求以及換電站內(nèi)電池包的選取原則和流程，對每一次換電需求對應(yīng)的換電站和換電電池包的選擇進(jìn)行決策，建立AGV的集裝箱任務(wù)調(diào)度模型和換電電池包配置模型， 采用GA來對模型進(jìn)行編碼求解，以500個(gè)集裝箱10臺(tái)AGV為例進(jìn)行求解。結(jié)果表明，該雙層模型能夠有效地減少總?cè)蝿?wù)完成時(shí)間和換電總時(shí)間，提升了6.46%的AGV電池包利用率，并且能夠合理有效地規(guī)劃換電站的電池包儲(chǔ)備數(shù)量，降低了23.1%的電池包儲(chǔ)備數(shù)量。由此可見，該雙層模型的研究對提高自動(dòng)化集裝箱碼頭的運(yùn)作效率有一定的現(xiàn)實(shí)意義，為進(jìn)行自動(dòng)化碼頭換電站內(nèi)電池包數(shù)量的研究提供了一種思路。

參考文獻(xiàn)：

［1］Kim K H，Bae J W. A look-ahead dispatching method for automated guided vehicles in automated port container terminals ［J］. Transportation Science，2004，38（2）： 121-255.

［2］Schneider F，Thonemann U W，Klabjan D. Optimization of battery charging and purchasing at electric vehicle battery swap stations ［J］. Transportation Science，2018，52（5）： 1035-1296.

［3］Xiang Xi，Liu Changchun. Modeling and analysis for an automated container terminal considering battery management ［J］. Computers amp; Industrial Engineering，2021，156： 107258.

［4］石楠路，梁承姬. 考慮換電過程的自動(dòng)化碼頭AGV調(diào)度優(yōu)化 ［J］. 現(xiàn)代制造工程，2019 （2）： 6-11，139. （Shi Nanlu，Liang Chengji. Scheduling optimization of automated terminal AGV consi-dering power exchange process ［J］. Modern Manufacturing Engineering，2019 （2）： 6-11，139.）

［5］周小凡，萇道方，余芳，等. 考慮充電和等待時(shí)間的集裝箱碼頭AGV調(diào)度 ［J］. 上海海事大學(xué)學(xué)報(bào)，2019，40（3）： 1-5，13. （Zhou Xiaofan，Chang Daofang，Yu Fang，et al. AGV scheduling in container terminals considering charging and waiting time ［J］. Journal of Shanghai Maritime University，2019，40（3）： 1-5，13.）

［6］張亞琦，楊斌，胡志華，等. 自動(dòng)化碼頭AGV充電與作業(yè)的集成調(diào)度研究 ［J］. 計(jì)算機(jī)工程與應(yīng)用，2017，53（18）： 257-262，270. （Zhang Yaqi，Yang Bin，Hu Zhihua，et al. Research on integrated scheduling of AGV charging and operation in automated terminals ［J］. Computer Engineering and Applications，2017，53（18）： 257-262，270.）

［7］吳洪明，鄒夢艷. 考慮電池電量約束的自動(dòng)化碼頭AGV調(diào)度 ［J］. 起重運(yùn)輸機(jī)械，2021 （3）： 47-52. （Wu Hongming，Zou Mengyan. Automatic terminal AGV scheduling considering battery power constraints ［J］. Hoisting and Transportation Machinery，2021 （3）： 47-52.）

［8］丁一，陳婷. 基于滾動(dòng)時(shí)域優(yōu)化策略的多載AGV充電調(diào)度 ［J］. 中國航海，2020，43（2）： 80-85. （Ding Yi，Chen Ting. Multi-load AGV charging scheduling based on rolling time domain optimization strategy ［J］. China Navigation，2020，43（2）： 80-85.）

［9］鄭亞紅，徐玖龍，謝淳. 自動(dòng)化集裝箱碼頭AGV換電管理與調(diào)度優(yōu)化 ［J］. 武漢理工大學(xué)學(xué)報(bào)：交通科學(xué)與工程版，2021，45（1）： 1-6. （Zheng Yahong，Xu Jiulong，Xie Chun. AGV power exchange management and scheduling optimization in automated container terminals ［J］. Journal of Wuhan University of Technology：Transportation Science and Engineering Edition，2021，45（1）： 1-6.）

［10］傅正堂，胡志華，宗康. 集裝箱碼頭AGV電量非飽和狀態(tài)下的調(diào)度優(yōu)化 ［J］. 大連海事大學(xué)學(xué)報(bào)，2017，43（3）： 58-62. （Fu Zhengtang，Hu Zhihua，Zong Kang. Scheduling optimization of AGV in container terminal under non-saturated state of electricity ［J］. Journal of Dalian Maritime University，2017，43（3）： 58-62.）

［11］范厚明，郭振峰，岳麗君，等. 考慮能耗節(jié)約的集裝箱碼頭雙小車岸橋與AGV聯(lián)合配置及調(diào)度優(yōu)化 ［J］. 自動(dòng)化學(xué)報(bào)，2021，47（10）： 2412-2426. （Fan Houming，Guo Zhenfeng，Yue Lijun，et al. Combined configuration and scheduling optimization of dual-trolley quay cranes and AGV in container terminals considering energy sa-ving ［J］. Chinese Journal of Automation，2021，47（10）： 2412-2426.）

［12］宋紹京，羊銘雨，孫磊，等. AGV數(shù)量規(guī)劃及電池充電策略研究 ［J］. 長春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2019，42（6）： 73-77. （Song Shaojing，Yang Mingyu，Sun Lei，et al. Research on AGV quantity planning and battery charging strategy ［J］. Journal of Changchun University of Science and Technology：Natural Science Edition，2019，42（6）： 73-77.）

［13］黃宇超. 自動(dòng)化碼頭AGV換電站布局設(shè)計(jì) ［J］. 港口裝卸，2021 （4）： 61-65. （Huang Yuchao. Layout design of AGV swap station in automated wharf ［J］. Port Handling，2021 （4）： 61-65.）

［14］樊陸彬，梁承姬，佘文婧. 不確定環(huán)境下的岸橋—集卡協(xié)調(diào)調(diào)度耦合模型建立與求解 ［J］. 計(jì)算機(jī)應(yīng)用，2016，36（3）： 843-848. （Fan Lubin，Liang Chengji，She Wenjing. Establishment and solution of the coupled model of quay crane-truck coordination dispatch in uncertain environment ［J］. Journal of Computer Applications，2016，36（3）： 843-848.）

［15］陳香玲，郭鵬，溫昆，等. 考慮充電需求和時(shí)間窗的多AGV調(diào)度優(yōu)化建模 ［J］. 河北科技大學(xué)學(xué)報(bào)，2021，42（2）： 91-100. （Chen Xiangling，Guo Peng，Wen Kun，et al. Multi-AGV scheduling optimization modeling considering charging demand and time window ［J］. Journal of Hebei University of Science and Technology，2021，42（2）： 91-100.）