自動化集裝箱碼頭AGV調度與換電雙層模型求解

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

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

0 引 言

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

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

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

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

1 問題描述

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

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

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

(a) 非接觸式充電

(b) 換電式

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

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

表1 AGV狀態劃分Tab.1 AGV status division

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

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

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

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

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

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

2 模型建立

2.1 AGV調度模型(上層模型)

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

2.1.2 符號說明

(1)集合

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

V′0：V′0={v′0}，虛擬結束任務集合；

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

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

Vk：Vk={1，2，…，n}，第k臺AGV對應的換電任務；

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

V：V=V0∪V′0∪Vb∪Vt，任務集合．

(2)參數

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

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

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

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

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

M：一個無窮大的正數；

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

Wki：第k臺AGV執行換電任務i的排隊時間；

di：任務i發箱位置與收箱位置的距離；

ei：任務i的最早允許作業時間；

Dij：任務i收箱位置與任務j發箱位置的距離，換電任務收箱位置和發箱位置均轉化為換電站位置；

dki：第k臺AGV執行任務i的空駛距離，從緊前任務收箱位置到任務i發箱位置的距離；

zki：第k臺AGV執行任務i的完成時間；

wki：第k臺AGV執行任務i的岸邊等待時間；

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

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

(3)決策變量

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

2.1.3 AGV調度模型建立 在本模型中，根據裝卸任務量、每個任務的最早允許作業時間、每臺AGV最多允許換電次數和AGV數量，建立以AGV最終完工時間最小化為目標的AGV調度模型．

目標函數：

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)

目標函數：最終完工時間最小化．

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

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

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

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

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

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

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

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

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

2.2.2 符號說明

(1)集合

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

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

(2)參數

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

Suk：第k臺AGV第u次換電指令產生時間；

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

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

fuk：第k臺AGV完成第u次換電后，到達換電后繼任務發箱位置時間；

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

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

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

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

(3)決策變量

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

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

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

目標函數：

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)

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

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

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

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

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

3 算法設計

3.1 循環迭代流程

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

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

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

3.2 AGV調度模型(上層模型)遺傳算法設計

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

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

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

(2)適應度函數：取AGV調度模型目標函數的倒數作為適應度值，即1/F．

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

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

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

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

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

(1)染色體編碼：采用矩陣整數編碼方式，由AGV調度模型的結果可知每臺AGV執行換電任務的次數，即每臺AGV換電次數，第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)適應度函數：取AGV換電模型目標函數的倒數為適應度值，即1/F′．

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

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

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

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

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

4 算例分析

4.1 參數與環境

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

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

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

4.2 小規模算例

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

表3 小規模算例參數Tab.3 Small-scale calculation example parameters

設定最大循環次數為50，AGV調度部分，種群大小為20，交叉概率為0.8，變異概率為0.1；AGV換電部分，種群大小為10，交叉概率為0.7，變異概率為0.15，最長求解時間為1 h．

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

表4 小規模算例求解結果Tab.4 Small-scale calculation example solution results

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

4.3 大規模算例

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

圖9 AGV調度甘特圖Fig.9 AGV scheduling Gantt chart

表5 大規模算例參數Tab.5 Large-scale calculation example parameters

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

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

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

表7 不同規模算例的結果Tab.7 Results of different scale examples

一味追求增加AGV數量從而縮短完工時間，必須綜合考慮數量增多導致可能出現的換電問題．

4.4 算法比較

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

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

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

5 結 語

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

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