趙 濤， 梁 承 姬， 胡 筱 淵， 王 鈺

( 上海海事大學(xué) 物流科學(xué)與工程研究院， 上海 201306 )

0 引 言

為建設(shè)綠色港口，降低碳排放，大部分自動化集裝箱碼頭采用純電力驅(qū)動的自動導(dǎo)引車(automated guided vehicle，AGV)承擔(dān)集裝箱在碼頭內(nèi)部的水平運輸任務(wù)，連接岸邊作業(yè)系統(tǒng)與堆場作業(yè)系統(tǒng)．電力驅(qū)動AGV是特殊工作環(huán)境下的電動汽車．當(dāng)AGV可用電量低于換電閾值(安全電量)時，必須充電，否則隨時有可能停止運行，從而影響集裝箱碼頭正常作業(yè)．因此，AGV充電是自動化集裝箱碼頭不可忽略的重要問題．

自動化集裝箱碼頭投產(chǎn)以來，AGV調(diào)度問題備受學(xué)者青睞．Confessore等[1]利用最小流模型分析了AGV調(diào)度問題；王聰?shù)萚2]建立了雙層規(guī)劃模型研究AGV作業(yè)效率和能源消耗；Choe等[3]提出了在線學(xué)習(xí)算法對AGV進行實時調(diào)度；霍凱歌等[4]以最小化作業(yè)總費用為規(guī)劃目標(biāo)研究了多載AGV的調(diào)度問題．大部分學(xué)者在研究AGV調(diào)度問題時，往往忽略了電量約束．隨著AGV充電問題的重要性日趨顯現(xiàn)，部分學(xué)者開始關(guān)注AGV充電問題．如劉廣紅等[5]分析了上海港洋山四期自動化碼頭的總體布局，以及換電站的分布和容量設(shè)置；傅正堂等[6]考慮AGV耗電差異，研究了AGV電量非飽和狀態(tài)下的調(diào)度優(yōu)化；石楠路等[7]構(gòu)建了混合整數(shù)優(yōu)化調(diào)度模型，提出了AGV作業(yè)順序和換電站時間窗協(xié)同的換電策略，并用遺傳算法求解驗證了模型的有效性；丁一等[8]考慮AGV裝載能力和充電后續(xù)航能力約束，構(gòu)建了多載AGV動態(tài)作業(yè)調(diào)度的混合整數(shù)規(guī)劃模型．但現(xiàn)有AGV換電問題的研究成果仍沒有關(guān)于深入分析AGV調(diào)度和換電關(guān)系的內(nèi)容．

充電問題是電池驅(qū)動工具無可避免的問題，并且充電問題和調(diào)度問題在電動汽車和無人機領(lǐng)域已有較多研究成果．如Barco等[9]綜合考慮電池包退化、充電過程等因素，研究了電動汽車路線問題；Shao等[10]綜合考慮電動汽車的電量消耗、充電站數(shù)量和車輛負(fù)載，研究了電動汽車的路線問題；袁泉等[11]分析了電動汽車路網(wǎng)交通信息和電網(wǎng)運行狀態(tài)的交互影響，并提出了路網(wǎng)-電網(wǎng)耦合原則以調(diào)節(jié)輸電線路阻塞問題；Thibbotuwawa等[12]以最大程度降低能耗為目標(biāo)研究了電量、無人機重復(fù)調(diào)用和有效荷載約束下的無人機調(diào)度問題；Liu等[13]考慮UAV充電時間和能耗的共同優(yōu)化，建立了無線充電下無人機最小能耗優(yōu)化模型．

綜上所述，大部分AGV調(diào)度相關(guān)文獻(xiàn)中沒有考慮電量約束和充電過程，少部分文獻(xiàn)考慮電量約束，但沒有考慮換電站的數(shù)量和容量限制等因素．本文針對有多個換電站的自動化集裝箱碼頭，綜合考慮AGV重、空載耗電差異和換電站的數(shù)量、容量限制等約束，分析AGV調(diào)度和換電之間相互影響的內(nèi)在關(guān)系，建立AGV調(diào)度和換電的雙層耦合模型，生成AGV調(diào)度和換電方案．

1 問題描述

自動化集裝箱碼頭純電動AGV的充電方式可分為樁式充電、非接觸式充電和換電式．樁式充電必須建設(shè)專用場地．非接觸式充電方式如圖1(a)所示，無須專用場地，AGV在堆場交互區(qū)工作間隙補充電量，實現(xiàn)了車輛非停車充電，但充電率有限；換電式如圖1(b)所示，必須建設(shè)專用換電站，待換電AGV空載駛向換電站，換電機器人為AGV更換電池包．本文研究的自動化集裝箱碼頭AGV充電問題均為換電式的AGV充電問題．

自動化集裝箱碼頭的布局方式主要分為平行式和垂直式，具體細(xì)分為5類：雙車道平行式、單車道平行式、兩端車道垂直式、兩側(cè)車道垂直式和U形車道垂直式[14-15]．研究表明，垂直式布局比平行式布局更利于發(fā)揮自動化設(shè)備的作業(yè)性能，且垂直式布局使用廣泛，如澳大利亞布魯斯班碼頭、荷蘭鹿特丹ECT碼頭、英國倫敦Gateway碼頭、德國漢堡CTA碼頭等[16-17]．

本文以上海港洋山四期自動化碼頭實際布局為基礎(chǔ)(圖2)，研究兩端車道垂直式自動化集裝箱碼頭布局．該碼頭劃分為岸橋作業(yè)區(qū)、AGV作業(yè)區(qū)和自動化堆場作業(yè)區(qū)，共建設(shè)A、B兩座換電站，并分布在碼頭兩端．換電站A為小換電站，配置1個換電工位；換電站B為大換電站，配置2個換電工位，即可以同時為2臺AGV更換電池包，每個換電工位完成1次電池包更換平均花費300 s．

(a) 非接觸式充電

(b) 換電式

從AGV電量消耗的角度考慮，將AGV劃分為3種狀態(tài)(表1)，每種狀態(tài)下耗電量和行駛速度均不同：在停車狀態(tài)下，耗電量最小，僅維持AGV導(dǎo)航、通信等系統(tǒng)的正常運行；在重載狀態(tài)下，耗電量最大，AGV運載集裝箱由發(fā)箱位置到收箱位置；在空載狀態(tài)下，耗電量適中，AGV正?？振偅?種狀態(tài)下的AGV分別對應(yīng)8種不同工作場景，見圖2．場景a為AGV在AGV等待區(qū)，等待接收指令；場景b為AGV等待岸橋完成作業(yè)；場景c為AGV等待場橋完成操作；場景d為AGV在換電站排隊等待更換電池包；場景e為裝船作業(yè)，AGV在堆場裝箱行駛至岸邊卸箱；場景f為卸船作業(yè)，AGV在岸邊裝箱行駛至堆場卸箱；場景g為AGV由收箱位置行駛至發(fā)箱位置；場景h為AGV駛向換電站和駛離換電站．

圖2 洋山四期自動化碼頭Fig.2 Yangshan Phase Ⅳ automated terminal

表1 AGV狀態(tài)劃分Tab.1 AGV status division

每臺AGV的作業(yè)狀態(tài)均在8種場景中不斷地變換，電量在不停地更新．為了盡量減少因AGV斷電停止作業(yè)帶來的損失，結(jié)合實地調(diào)研結(jié)果，本文采用固定閾值換電策略，具體如下：每臺AGV初始電量均為100%，在接收作業(yè)指令時，判斷AGV剩余電量是否大于換電閾值，當(dāng)且僅當(dāng)AGV剩余電量不大于換電閾值時，不再接收任何作業(yè)指令，前往換電站更換電池包．AGV在更換完電池包之后再次投入使用，直至全部作業(yè)任務(wù)完成．AGV換電總時間為各臺AGV駛向和駛離換電站的時間、換電站排隊時間以及電池包更換操作時間總和，具體換電過程分析如圖3所示．

圖3 AGV換電過程分析Fig.3 Analysis of AGV battery exchange process

AGV調(diào)度決定了AGV何時換電，AGV換電過程決定了AGV何時再次投入使用，彼此相互聯(lián)系，從而影響AGV任務(wù)的最終完工時間．本文根據(jù)AGV調(diào)度和換電之間的關(guān)系，建立AGV調(diào)度和換電的雙層耦合模型，如圖4所示．在圖中，上層模型為AGV調(diào)度模型，以最終完工時間最小化為目標(biāo)，決策AGV調(diào)度；下層模型為AGV換電模型，以換電總時間最小化為目標(biāo)，決策每臺AGV每次選擇的換電站．

具體如下：AGV調(diào)度模型中考慮換電電量約束，設(shè)定每臺AGV最大允許換電次數(shù)和換電任務(wù)，每次任務(wù)結(jié)束時判斷剩余電量是否低于換電閾值，若是則執(zhí)行換電任務(wù)即前往指定換電站編號，否則接收并執(zhí)行下一任務(wù)，直至全部任務(wù)完成，以最終完工時間最小化為目標(biāo)決策制定AGV調(diào)度方案和AGV換電需求，即每臺AGV任務(wù)作業(yè)順序、每次換電時間、換電緊前任務(wù)、換電后繼任務(wù)和換電時刻剩余電量，為AGV換電模型提供輸入數(shù)據(jù)．

圖4 雙層耦合模型框架Fig.4 Two-layer coupling model frame

AGV換電模型中考慮AGV換電需求、換電站位置、換電站工位數(shù)量和先到先服務(wù)原則等約束，以換電總時間最小化為目標(biāo)決策制定AGV換電方案，即每臺AGV每次換電所選換電站編號和相應(yīng)的排隊時間，對應(yīng)調(diào)度模型中換電任務(wù)編號和等待時間．以換電需求和換電方案連接兩個子模型，并通過迭代不斷更新公共設(shè)計變量，形成兩個模型的雙層耦合關(guān)系．

2 模型建立

2.1 AGV調(diào)度模型(上層模型)

2.1.1 模型假設(shè) AGV初始電量均為100%；在作業(yè)過程中，AGV不會晚于計劃時間到達(dá)指定位置；在作業(yè)過程中，不考慮設(shè)備故障以及碰撞；岸橋、場橋的每個裝卸任務(wù)的操作順序和操作時間已知；所有集裝箱大小均為12.192 m，1輛AGV 1次裝載1個集裝箱；不考慮碼頭突發(fā)狀況和AGV沖突因素．

2.1.2 符號說明

(1)集合

V0：V0={v0}，虛擬開始任務(wù)集合；

V′0：V′0={v′0}，虛擬結(jié)束任務(wù)集合；

Vt：Vt={1，2，…，t}，裝卸任務(wù)集合；

K：K={1，2，…，k}，AGV集合；

Vk：Vk={1，2，…，n}，第k臺AGV對應(yīng)的換電任務(wù)；

Vb：Vb=V1∪V2∪…∪Vk，全部換電任務(wù)集合；

V：V=V0∪V′0∪Vb∪Vt，任務(wù)集合．

(2)參數(shù)

s1、s2：AGV空載和重載速度；

r1、r2、r3：AGV空載、重載和停車每秒耗電率；

C：換電閾值(安全電量)；

y：岸橋的平均操作時間；

q：場橋的平均操作時間；

M：一個無窮大的正數(shù)；

afix：一次更換電池包的操作時間；

Wki：第k臺AGV執(zhí)行換電任務(wù)i的排隊時間；

di：任務(wù)i發(fā)箱位置與收箱位置的距離；

ei：任務(wù)i的最早允許作業(yè)時間；

Dij：任務(wù)i收箱位置與任務(wù)j發(fā)箱位置的距離，換電任務(wù)收箱位置和發(fā)箱位置均轉(zhuǎn)化為換電站位置；

dki：第k臺AGV執(zhí)行任務(wù)i的空駛距離，從緊前任務(wù)收箱位置到任務(wù)i發(fā)箱位置的距離；

zki：第k臺AGV執(zhí)行任務(wù)i的完成時間；

wki：第k臺AGV執(zhí)行任務(wù)i的岸邊等待時間；

bki：第k臺AGV開始任務(wù)i的電池包剩余電量；

Bki：第k臺AGV完成任務(wù)i的電池包剩余電量．

(3)決策變量

xkij為0-1變量，若第k臺AGV在執(zhí)行任務(wù)i之后緊接著執(zhí)行任務(wù)j，則xkij=1，否則xkij=0．

2.1.3 AGV調(diào)度模型建立 在本模型中，根據(jù)裝卸任務(wù)量、每個任務(wù)的最早允許作業(yè)時間、每臺AGV最多允許換電次數(shù)和AGV數(shù)量，建立以AGV最終完工時間最小化為目標(biāo)的AGV調(diào)度模型．

目標(biāo)函數(shù)：

minF

約束條件：

F≥zki；?k∈K，i∈V

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

wkj≥ej-zki-dki/s1+(xkij-1)M；

?k∈K，j∈Vt，i∈V

(9)

zkj≥zki+wkj+dkj/s1+dkj/s2+y+q-

(1-xkij)M； ?k∈K，j∈Vt，i∈V

(10)

zkj≥zki+wki+afix+dki/s2+(1-xkij)M；

?k∈K，j∈Vk，i∈Vt

(11)

bkj=Bki+(1-xkij)M；

?k∈K，i∈V，j∈Vt

(12)

bkj≤C；?k∈K，j∈Vb

(13)

Bki=100；?k∈K，i∈V0∪Vb

(14)

Bki=bki-r1dki/s1-r2di/s2-r3wki；

?k∈K，i∈Vt

(15)

(16)

(17)

?k∈K，i，j∈Vk，j≤i

(18)

zki>0，Bki>0，wki≥0，dki≥0；

?k∈K，i∈V

(19)

目標(biāo)函數(shù)：最終完工時間最小化．

完工時間約束：式(1)任務(wù)完成時間不小于任意任務(wù)的完成時間．

任務(wù)約束：式(2)、(3)為每臺AGV必須完成虛擬開始和虛擬結(jié)束任務(wù)；式(4)、(5)為每個任務(wù)僅有一個緊前和后繼任務(wù)，且允許換電任務(wù)不必全部完成，即無須每臺AGV都發(fā)生n次換電；式(6)為平衡約束，中間任務(wù)必須運輸平衡，即輸入等于輸出．

距離約束：式(7)為AGV執(zhí)行任務(wù)空駛距離．

時間約束：式(8)、(9)為等待時間，虛擬等待時間為0，換電任務(wù)等待時間為換電時間，普通任務(wù)等待時間由到達(dá)發(fā)箱位置的時間和最早允許作業(yè)時間計算得到；式(10)、(11)為任務(wù)完成時間，普通任務(wù)完成時間由緊前任務(wù)完成時間、等待時間、岸橋操作時間、場橋操作時間、空駛時間和重駛時間求和得到，換電任務(wù)完成時間由緊前任務(wù)完成時間、換電操作時間、空載駛向換電站時間、等待時間求和得到．

電量約束：式(12)為接受任務(wù)時AGV剩余電量，接受普通作業(yè)任務(wù)時即緊前任務(wù)完成時剩余電量；式(13)為接受換電任務(wù)時，AGV剩余電量不大于換電閾值；式(14)、(15)為AGV完成任務(wù)時剩余電量，普通任務(wù)計算方式為接收任務(wù)時電量、重載耗電量、空載耗電量計算而得，換電任務(wù)完成時電量為100%，即AGV更換新電池包．

換電任務(wù)約束：式(16)表示AGV只能執(zhí)行獨自所屬n個虛擬換電任務(wù)；式(17)為1臺AGV的換電次數(shù)之和，不允許超過最多換電次數(shù)n；式(18)為1臺AGV的換電任務(wù)只能按照所屬換電任務(wù)編號從小到大依次執(zhí)行，即若換電i次，只能完成前i個換電任務(wù)，不能完成多余的換電任務(wù)．

變量約束：式(19)為變量的約束條件．

2.2 AGV換電模型(下層模型)

2.2.1 模型假設(shè) 每個換電站內(nèi)可用電池包的數(shù)量充足；每個換電站遵循先到先服務(wù)規(guī)則；不考慮換電工位維護等不確定性因素；每個換電工位同一時刻僅為1臺AGV更換電池包；每個換電站配置1個換電工位．

2.2.2 符號說明

(1)集合

T：T={1，2，…，m}，換電站集合；

Uk：換電需求集合，由調(diào)度模型可得，u∈U，U=U1∪U2∪…∪Uk．

(2)參數(shù)

Buk：第k臺AGV第u次換電指令產(chǎn)生時的剩余電量；

Suk：第k臺AGV第u次換電指令產(chǎn)生時間；

dukm：第k臺AGV第u次換電駛向換電站m的距離；

Dukm：第k臺AGV第u次換電選擇m號換電站與后繼任務(wù)發(fā)箱位置距離；

fuk：第k臺AGV完成第u次換電后，到達(dá)換電后繼任務(wù)發(fā)箱位置時間；

Aukm：第k臺AGV第u次換電選擇m號換電站的到達(dá)時間；

Cukm：第k臺AGV第u次換電選擇m號換電站的開始操作時間；

Wukm：第k臺AGV第u次換電選擇m號換電站的排隊時間；

Lukm：第k臺AGV第u次換電選擇m號換電站的完成時間．

(3)決策變量

ykk′m：0-1變量，第k臺AGV比第k′臺AGV提前到達(dá)m號換電站，則ykk′m=1，否則ykk′m=0；

pukm：0-1變量，若第k臺AGV第u次換電選擇m號換電站，則pukm=1，否則pukm=0．

2.2.3 AGV換電模型建立 在本模型中，考慮換電站的位置、排隊時間和電量消耗差異，建立以AGV換電總時間最小化為目標(biāo)的AGV換電模型．

目標(biāo)函數(shù)：

minF′

約束條件：

(20)

(21)

(22)

(23)

fuk≥Lukm+Dukm/s2+(pukm-1)M；

?u∈Uk，k∈K，m∈T

(24)

Aukm≥(pukm-1)M+Suk+dukm/s2；

?u∈Uk，m∈T，k∈K

(25)

?m∈T，k，k′∈K，u∈Uk′，u′∈Uk′

(26)

Cukm≤(1-pukm)M+Aukm+Wukm；

?u∈Uk，m∈T，k∈K

(27)

Lukm≤(1-pukm)M+Cukm+afix；

?u∈Uk，m∈T，k∈K

(28)

(1-pukm)M+Buk-r2dukm/s2-r3Wukm≥0；

?u∈Uk，k∈K，m∈T

(29)

(1-ykk′m)M+Aukm-Au′k′m≥0；

?m∈T，k，k′∈K，u∈Uk，u′∈Uk′

(30)

ykkm=0；?m∈T，k∈K

(31)

fuk>0，Wukm≥0； ?m∈T，k，k′∈K，u∈U

(32)

目標(biāo)函數(shù)：最小化AGV換電總時間．式(20)為AGV換電總時間的計算．

排隊約束：式(21)為1臺AGV每次換電只能選擇1個換電站；式(22)、(23)為AGV在換電時前后最多各有1臺AGV需要被服務(wù)；式(30)為2臺AGV存在前后排隊關(guān)系前提是前者比后者提前到達(dá)同1個換電站；式(31)排除不可能產(chǎn)生排隊現(xiàn)象，即連續(xù)被同1個換電站服務(wù)的AGV編號不可能相同．

時間約束：式(24)為到達(dá)后繼任務(wù)發(fā)箱位置時間，即該次換電的完成時間與空載駛離時間之和；式(25)為到達(dá)換電站時間，即該次換電指令產(chǎn)生時間與空載駛向換電站時間之和；式(26)為換電站排隊時間，若到達(dá)換電站時前1臺AGV尚未完成換電則等待，否則無須等待；式(27)為換電工位開始操作時間，即到達(dá)換電站時間與排隊時間之和；式(28)為更換電池操作完成時間，即操作開始時間加上換電操作時間．

電量約束：式(29)為電量必須足夠到達(dá)所選換電站．

變量約束：式(32)表示時間變量非負(fù)．

3 算法設(shè)計

3.1 循環(huán)迭代流程

依據(jù)上述建模思路，提出循環(huán)迭代求解算法，分別求解AGV調(diào)度模型(上層模型)和AGV換電模型(下層模型)．將調(diào)度模型和換電模型多次循環(huán)迭代計算，不斷更新公用變量的值，實現(xiàn)AGV調(diào)度方案的最優(yōu)，具體流程如圖5所示．

圖5 迭代計算流程Fig.5 Iterative calculation process

在圖5初始條件下，設(shè)定初始換電任務(wù)的位置(換電站編號)和換電排隊時間，通過AGV調(diào)度模型，可得AGV作業(yè)任務(wù)順序，即AGV調(diào)度方案．同時，可得換電任務(wù)的緊前任務(wù)、后繼任務(wù)、相應(yīng)電量和接受任務(wù)時間，進而可知每臺AGV每次換電駛向和駛離各個換電站的距離、指令產(chǎn)生時間和剩余電量．將空駛距離矩陣、換電產(chǎn)生時間和剩余電量作為已知條件代入AGV換電模型，求解可得不同AGV換電時所選的不同換電站編號和排隊等待時間，依據(jù)換電方案更新AGV調(diào)度模型中的換電任務(wù)位置和等待時間，如此循環(huán)迭代求解，直至最終完工時間不發(fā)生變化或迭代到一定次數(shù)，輸出較優(yōu)的AGV調(diào)度方案和換電方案．

3.2 AGV調(diào)度模型(上層模型)遺傳算法設(shè)計

遺傳算法(GA)是求解NP-hard問題的經(jīng)典算法之一，其編碼規(guī)則簡單有效，具有高度并發(fā)性和全局搜索能力，因此廣泛用于求解AGV調(diào)度模型，以獲得其近似最優(yōu)解．

(1)染色體編碼：整數(shù)編碼方式，染色體長度為任務(wù)數(shù)和虛擬任務(wù)數(shù)之和，第i個位置的編號k表示第i個任務(wù)由第k臺AGV完成，如圖6所示．10個任務(wù)由3臺AGV分配完成，假設(shè)每臺AGV最多需要換電2次，任務(wù)11～16為虛擬換電任務(wù)；任務(wù)11和12對應(yīng)第1臺AGV所屬換電任務(wù)，任務(wù)13和14對應(yīng)第2臺AGV所屬換電任務(wù)，任務(wù)15和16對應(yīng)第3臺AGV所屬換電任務(wù)．虛擬換電任務(wù)不必一定執(zhí)行，若第1臺AGV僅換電1次，則虛擬換電任務(wù)僅完成任務(wù)11；若第1臺AGV換電2次，則必須完成任務(wù)11和12；若第1臺AGV無須換電，則任務(wù)11和12均無須完成．

圖6 上層模型染色體編碼Fig.6 Chromosome coding of the upper model

(2)適應(yīng)度函數(shù)：取AGV調(diào)度模型目標(biāo)函數(shù)的倒數(shù)作為適應(yīng)度值，即1/F．

(3)選擇：輪盤賭選擇．

(4)交叉：兩點交叉，設(shè)置交叉概率Pc1，將被交叉概率選中的染色體作為父代1和父代2，在任務(wù)編碼部分隨機生成兩個交叉點位，兩點之間的染色體部分即為交叉部分R1、R2，AGV換電任務(wù)部分保持不變．

(5)變異：交換變異，設(shè)置變異概率Pm1，在染色體的任務(wù)部分隨機選擇兩個基因值M1和M2進行交換，改變AGV作業(yè)順序，換電任務(wù)編號保持不變．

3.3 AGV換電模型(下層模型)遺傳算法設(shè)計

鑒于AGV換電模型中存在非線性約束關(guān)系，遺傳算法編碼規(guī)則簡單且遺傳操作比其他算法種群操作產(chǎn)生非法解的概率更低，因此采用遺傳算法求解AGV換電模型．

(1)染色體編碼：采用矩陣整數(shù)編碼方式，由AGV調(diào)度模型的結(jié)果可知每臺AGV執(zhí)行換電任務(wù)的次數(shù)，即每臺AGV換電次數(shù)，第k行第n列的位置表示第k臺AGV第n次換電選擇的換電站編號．如圖7所示，3臺AGV，每臺AGV最多需要換電2次，第1臺AGV需要換電2次，第1次換電選擇1號換電站，第2次換電選擇2號換電站；第2臺AGV僅換電1次，選擇1號換電站；第3臺AGV需要換電2次，每次都選擇2號換電站．

圖7 下層模型染色體編碼Fig.7 Chromosome coding of the lower model

(2)適應(yīng)度函數(shù)：取AGV換電模型目標(biāo)函數(shù)的倒數(shù)為適應(yīng)度值，即1/F′．

(3)選擇：輪盤賭選擇．

(4)交叉：設(shè)置交叉概率Pc2，隨機選擇兩行基因值p1和p2進行交換得到新的染色體．將被交叉概率選中的染色體作為父代1和父代2，隨機生成兩個交叉點位，交叉得到兩條新染色體．

(5)變異：設(shè)置變異概率Pm2，每條染色體每行隨機選擇一個點位，重新生成基因值．

(6)染色體修復(fù)：在經(jīng)歷選擇、交叉、變異之后，種群中存在不符合條件的染色體，如圖8(a)所示，第2臺AGV必須換電1次，第3臺AGV必須換電2次，則進行染色體修復(fù)．將第2行第2列基因值賦值為0，第3行第1列賦值為1或2．

(a) 修復(fù)前(b) 修復(fù)后圖8 下層模型染色體修復(fù)Fig.8 Chromosome repair of the lower model

4 算例分析

4.1 參數(shù)與環(huán)境

本文針對以上所建立的模型和方法，設(shè)計了小規(guī)模算例和大規(guī)模算例．對于小規(guī)模算例，采用GAMS數(shù)學(xué)規(guī)劃軟件調(diào)用SBB求解器分別求得AGV調(diào)度模型和換電模型精確解，最終迭代得到雙層模型最優(yōu)解．之后對大規(guī)模算例采用遺傳算法進行循環(huán)迭代求解，并分析不同規(guī)模下算法的有效性和參數(shù)的影響．

以上海港洋山四期自動化碼頭實際布局為基礎(chǔ)，適當(dāng)修正換電站、岸橋和場橋之間的行駛距離，如表2所示．每臺岸橋執(zhí)行1次任務(wù)平均花費120 s；場橋內(nèi)每臺場橋執(zhí)行1次任務(wù)平均花費90 s；混合裝卸作業(yè)模式，1臺AGV完成1次電池包更換動作平均花費300 s．

表2 換電站-岸橋-場橋的距離矩陣Tab.2 Distance matrix of battery exchange station-quay crane-yard m

4.2 小規(guī)模算例

鑒于任務(wù)較少時，AGV無須換電，而任務(wù)較多時，求解器無法完成求解，為驗證模型的有效性，如表3所示，在碼頭實際參數(shù)基礎(chǔ)上縮小空載速度、重載速度和耗電率等參數(shù)，空載耗電率為0.1%/s，AGV重載耗電率為0.2%/s，AGV停車時耗電率為0.05%/s，共設(shè)2個換電站(各配1個換電工位)．

表3 小規(guī)模算例參數(shù)Tab.3 Small-scale calculation example parameters

設(shè)定最大循環(huán)次數(shù)為50，AGV調(diào)度部分，種群大小為20，交叉概率為0.8，變異概率為0.1；AGV換電部分，種群大小為10，交叉概率為0.7，變異概率為0.15，最長求解時間為1 h．

設(shè)置3組不同實驗，分別通過GAMS和GA迭代求解，結(jié)果見表4．第1組和第2組GAMS結(jié)果與GA上層目標(biāo)結(jié)果幾乎相同，說明了GA的有效性．當(dāng)任務(wù)數(shù)量增多時，GAMS無法在1 h內(nèi)得出結(jié)果，而GA仍可以求解，說明本文提出的算法在求解較多任務(wù)時存在一定的優(yōu)勢．

表4 小規(guī)模算例求解結(jié)果Tab.4 Small-scale calculation example solution results

以20個任務(wù)、4臺AGV為例，GA得到的AGV作業(yè)任務(wù)序列如圖9所示，說明其可以有效地決策AGV選擇換電站，合理控制換電總時間，且每臺AGV分配的任務(wù)數(shù)量較平均，對自動化集裝箱碼頭AGV調(diào)度有一定的應(yīng)用價值．

4.3 大規(guī)模算例

為驗證本文算法在碼頭實際作業(yè)情況下的表現(xiàn)效果，結(jié)合碼頭實際運營參數(shù)設(shè)立AGV空載耗電率為0.01%/s，AGV重載耗電率為0.02%/s，AGV停車時耗電率為0.005%/s，共設(shè)2個換電站，換電站A設(shè)置1個換電工位，換電站B設(shè)置2個換電工位，并將換電站B抽象為2個位置相同的換電站B1和B2，各配置1個換電工位，結(jié)合電池耗電特點建立AGV速度與電池剩余電量分段函數(shù)關(guān)系，見表5．

圖9 AGV調(diào)度甘特圖Fig.9 AGV scheduling Gantt chart

表5 大規(guī)模算例參數(shù)Tab.5 Large-scale calculation example parameters

首先，隨機生成500個任務(wù)，配置10臺AGV，換電閾值為35%，使用遺傳算法求解，設(shè)定最大循環(huán)次數(shù)為1 000．AGV調(diào)度部分，種群大小為100，交叉概率為0.7，變異概率為0.1，最大遺傳代數(shù)為300；AGV換電部分，種群大小為50，交叉概率為0.7，變異概率為0.15，最大遺傳代數(shù)為50．求得的AGV調(diào)度最終完工時間為14 819 s，換電總時間為8 056 s，換電總次數(shù)為10．具體AGV換電站信息見表6．分析500個任務(wù)下的換電站信息可知，每次AGV換電空駛距離差異顯著，AGV換電排隊時間均小于240 s，有效避免了換電站排隊擁堵現(xiàn)象，合理選擇了AGV換電站，進而提升AGV利用率．

其次，擴大算例規(guī)模，分析AGV數(shù)量對最終完工時間和換電總時間的影響．觀察不同規(guī)模下的算例結(jié)果(表7)可知，在同一任務(wù)數(shù)量下，AGV數(shù)量增多最終完工時間會明顯降低，AGV換電總次數(shù)不會發(fā)生較大變化，但換電總時間會隨之增加，即AGV空駛時間和換電排隊時間增加，碼頭的運營成本增加．為此，碼頭實際運營過程中不可

表6 大規(guī)模算例的換電站信息Tab.6 Battery exchange station information forlarge-scale calculation examples

表7 不同規(guī)模算例的結(jié)果Tab.7 Results of different scale examples

一味追求增加AGV數(shù)量從而縮短完工時間，必須綜合考慮數(shù)量增多導(dǎo)致可能出現(xiàn)的換電問題．

4.4 算法比較

本文在大規(guī)模算例下，設(shè)計6組實驗，每組實驗用GA與PSO算法進行求解，并對求解結(jié)果進行對比．表8為不同算例規(guī)模下GA和PSO的求解結(jié)果，每組實驗每個算法分別運算3次，取平均值為最終結(jié)果．

分析實驗1～4可知，當(dāng)AGV和任務(wù)數(shù)量較少時，GA結(jié)果略優(yōu)于PSO，GA運行時間優(yōu)于PSO．實驗5、6結(jié)果表明，隨著算例規(guī)模的增大，無論是完工時間還是運行時間，GA都明顯優(yōu)于PSO，由此驗證了GA在求解本文AGV調(diào)度與換電雙層耦合模型的算法優(yōu)勢．

表8 不同算法結(jié)果對比Tab.8 Result comparison of different algorithms

5 結(jié) 語

本文從自動化集裝箱碼頭實際換電站數(shù)量和位置出發(fā)，建立了AGV調(diào)度和換電的雙層耦合模型，分別采用GAMS求解器和遺傳算法循環(huán)迭代求解實際作業(yè)設(shè)計算例．在小規(guī)模算例下，GAMS求解器和遺傳算法的求解結(jié)果基本一致，證明了雙層耦合模型和遺傳算法的有效性．在大規(guī)模算例下，以500個任務(wù)10臺AGV為例，AGV換電站排隊最長時間小于240 s，平均排隊時間為90 s，證實該方案有效緩解了AGV換電站排隊擁擠情況，提升了AGV利用率．通過對比不同大規(guī)模算例可知，碼頭實際運營過程必須考慮AGV數(shù)量配置導(dǎo)致的可能出現(xiàn)的換電排隊問題．同時，遺傳算法和粒子群算法結(jié)果對比分析驗證了本文算法的優(yōu)勢．

本文所建立雙層耦合模型對于自動化集裝箱碼頭AGV換電具有指導(dǎo)意義，對于電動汽車和無人機的充換電問題有一定的參考意義．但是，本文尚未考慮換電站電池包數(shù)量、電池壽命等因素的影響，日后研究可逐步考慮此類因素．同時，可以繼續(xù)深入研究其他多種形式的自動化集裝箱碼頭布局、換電站選址優(yōu)化、換電站工位配置與AGV換電的關(guān)系．