自動化集裝箱碼頭AGV換電管理與調度優化*

鄭亞紅 徐玖龍 謝 淳

(武漢理工大學交通學院 武漢 430063)

0 引 言

自動導引運輸車(automated guided vehicle，AGV)純電力驅動，采用無人駕駛技術，同集卡相比，具有節能減排、智能行駛、降低人工勞動強度等顯著優勢.如今設備的自動控制技術已經日趨成熟，整個碼頭的效率瓶頸主要集中AGV的調度優化層面.近年來國內外學者對自動化碼頭AGV作業的相關研究大多數仍集中在傳統的調度問題，很少考慮其充電/換電過程.Vis[2]將AGV運輸系統調度問題分為調度問題(dispatching problem)和調度及路徑問題(dispatching and routing problem)，前者是基于作業任務對AGV進行分派并制定其作業時間表，后者同時進行調度和路徑選擇的決策.而大部分研究中的調度問題其實包含了路徑問題，可以稱之為一種廣義的調度問題.目前關于這類調度問題的研究主要有兩個方向：①對問題或模型的擴展，從文獻[3]基于將所有的AGV分派到同一岸橋的假設的簡單問題，發展到現在研究的多岸橋、考慮AGV行駛時間和岸橋作業時間延遲[4]、不同策略下的AGV自適應調度[5]、減少AGV的空載行駛以實現減排[6]等更切于實際的復雜問題，此外在決策變量類型、車輛性能、目標函數、約束條件、調度規則等方面有所區別；②對這類NP難問題的求解方法的探索，目前主要應用的方法有啟發式算法、智能學習方法、神經網絡學習、對混合整數規劃模型的約束松弛、基于時間Petri網的建模等，還有的借鑒了FMS(柔性制造系統)中的研究方法.

AGV續航有充電和更換整體電池包(簡稱換電)兩種不同方式，本研究基于前期對洋山四期自動化碼頭的調研展開，著重探討換電這種方式.石楠路等[7]的研究，考慮了AGV的換電過程，以提高AGV作業效率為優化目標構建了AGV作業調度混合整數優化模型，并通過遺傳算法求解.從研究結論看，雖然減少AGV換電排隊時間，但是大大降低了AGV電池利用率，因為為了錯開AGV換電時間，有的AGV在電量消耗很少的時候就前往換電站換電，從資源利用的角度看實際上產生了較大的浪費.張亞琦等[8]的研究，關注了AGV的充電過程，將AGV充電后的續航能力約束條件考慮進調度模型中，進行AGV充電與作業的聯合優化.

文中在對洋山四期自動化碼頭的調研和國內外現有研究特別是文獻[8]的基礎上，結合自動化集裝箱碼頭AGV實際生產作業流程和換電需求特性，以優化AGV換電模式為切入點進行換電管理優化，同時將AGV換電和作業進行協同，建立二者協同的調度模型，減少AGV在換電站的排隊等待時間，兼顧考慮提高AGV電池利用率，最終實現提高AGV作業效率.

1 問題描述

AGV換電站及其配套設施占地面積較大，一般建設在AGV運行車道的盡頭，見圖1.AGV調度同傳統碼頭中集卡調度的主要區別就是需要保證AGV的續航能力，杜絕AGV電量耗盡帶來的系列問題.由于現有的AGV路徑規劃系統和AGV無人駕駛技術不夠成熟，易出現由于一臺AGV未能及時更換電池包導致沒有足夠電量返回換電站而停在車道的情況.更嚴重地，可能造成其他工作的AGV因為車道被占用為防止發生碰撞而觸發車輛死鎖現象，進而導致越來越多的AGV堵塞在行車道上，引發碼頭上的交通癱瘓.實際上一旦出現AGV電量不足而導致停工的情況，中控室將指派維修員對AGV進行臨時充電，甚至需要重新規劃調度系統，無疑會增加碼頭的人力成本和時間成本.因此，AGV正常運行的前提條件是，必須確保AGV有充足的電量使其在電量耗盡之前到達換電站.

圖1 自動化集裝箱碼頭AGV作業區域示意圖

以卸船為例，自動化碼頭AGV工藝過程為：AGV 從AQC(自動化岸橋)接箱后，沿環形道路完成水平運輸，由ARMG(自動化龍門吊)提箱，然后AGV沿環形道路返回AQC下方執行下一任務.AGV運輸集裝箱過程實際上是一個循環過程，見圖2.假設AGV從換電站(或車場)出發時為滿電狀態，SOC(電量狀態)值為1，指派該AGV從岸橋1(位置O1)運輸集裝箱T1至箱區1(位置D1)，完成該任務T1后，AGV根據實時SOC值判斷是否能夠繼續完成別的任務，如果仍有足夠電量則接著去完成任務T2，因此指派該AGV行駛至岸橋2(位置O2)，將集裝箱T2運輸到箱區2(位置D2)；而如果AGV的電池剩余電量不足以使其完成其他任務，則指派該AGV前往換電站(終點)進行換電，直至其換電完成，表示該AGV的一個循環過程結束；其后，AGV從該換電站出發，執行新的循環過程直至AGV完成所有任務.同時需要考慮的是，由于AGV空車行駛、重車行駛以及等待狀態三種情況下耗電量有較大的差異，因此需要進行空駛行程、重載行程和排隊等待過程的區分，分別計算不同狀態下AGV的耗電量.

圖2 AGV運輸循環過程示意圖

根據前期對洋山四期自動化碼頭的調研，得知其現有的換電模式為.當AGV電池包SOC值低于40%時即前往換電站進行換電.現有模式的弊端，一方面在于換電SOC臨界值過大會引起電池電量利用率下降而提高電池使用成本，另一方面在于頻繁的換電可能會造成換電過程中出現AGV在換電站排隊等待的現象，從而進一步地造成AGV作業完工時間的延遲.因此，如何設計合理的換電模式、將換電模式同調度策略進行集成是建立調度模型的關鍵和難點.

2 模型構建

2.1 符號說明

2.2 數學模型

為減少AGV在換電站的排隊及等待時間，降低換電過程對AGV調度的影響以提高整體作業效率，建立AGV作業與換電過程協同調度優化模型.模型的目標函數與約束條件如下.

(1)

s.t.

(2)

?i≠j,v∈V

(3)

?i∈I,v∈V

(4)

?i≠j,v∈V

(5)

?i≠j,v∈V

(6)

(7)

∑j∈I+(〗i}xjiv=yivn,?i∈I,v∈V

(8)

(9)

xijv+xjiv≤1,?i,j∈I,i≠j,v∈V

(10)

∑i∈Ix0+1,i,v=1,?v∈V

(11)

∑i∈Ixi,O+2,v=1,?v∈V

(12)

xi,O+1,v=0,?i∈I+,v∈V

(13)

xO+2,j,v=0,?j∈I+,v∈V

(14)

?i,j∈I,v∈V

(15)

(16)

(17)

(18)

∑rvv′=1,?v≠v′

(19)

(20)

(21)

3 遺傳算法求解

3.1 染色體編碼過程

一條染色體即問題的一個可行解，表征AGV分配到的任務，為了保證整個迭代過程中解的可行性，換電過程不直接顯示在染色體中.2.1中總的集裝箱任務數為|I|，總的AGV數量為|V|.每一臺AGV完成多個循環運輸，一條染色體由|I|個1到|V|之間的正整數組成.圖3為15個任務、五臺AGV對應的問題的染色體編碼示意圖，AGV編號對應的任務編號即為分配給該AGV的運輸任務.例如，AGV2分配的任務列表task_AGV為{2 4 7 10}，對應的任務編號依次為2、4、7、10，因此AGV1執行任務的路徑route_AGV為：車場/換電站→任務2→任務4→任務7→任務10→車場/換電站.

圖3 染色體編碼示意圖

3.2 染色體解碼過程

染色體解碼過程即計算適應度值的過程.|V|臺AGV需要在若干循環內完成|I|個任務，因此在遺傳算法的解碼操作過程中，需要考慮到每一臺AGV在不同的任務循環周期內所分配到的任務.圖4為遺傳算法過程中染色體解碼流程圖.整個解碼過程主要包括兩個步驟，即生成初始AGV任務路徑和判斷是否進行換電兩個部分.

3.3 適應度函數

3.4 遺傳算子

3.4.1選擇算子

采用輪盤賭的方法，每一條染色體在輪盤上占有的面積根據適應度函數值按比例表示出來，即個體適應度值越大，被選擇的幾率越大.經過實驗對比，發現在其他算子不變的情況下采用謝菲爾德遺傳算法工具箱中的輪盤賭rws函數得出的結果較好，見表1.

表1 AGV1需完成的4個任務的屬性

3.4.2交叉算子

對于排列式染色體，通常采用單點或兩點均勻交叉法，通過實驗發現兩者的差別不大，因此選擇更為簡單的單點交叉法：首先在種群中隨機選擇兩條父代染色體P1和P2，然后隨機選擇一處切點，在這兩條染色體中均復制從染色體的第一個基因到該切點間的染色體片段r1和r2，最后將r1和r2交換位置，得到兩條子代染色體C1和C2，染色體交叉過程見圖5.

圖5 染色體交叉過程

3.4.3變異算子

采取隨機改變1個基因位的基因的變異方法：在父代染色體P中隨機選擇1個基因位，將其替代為一個新的可行的基因，產生新的子代染色體.染色體變異過程見圖6.

圖6 染色體變異過程

4 數值實驗

4.1 實驗參數設置

為驗證所構建模型的有效性和遺傳算法的可行性，利用MATLAB軟件對以下數值例子進行分析計算.隨機產生100個集裝箱任務樣本，任務順序即按照編號順序，任務屬性見表2，存放于Excel表格中.

表2 集裝箱任務屬性

為方便程序計算，設置2個換電站、8個堆場箱區、3臺岸橋以及AGV停車場四類節點的坐標見表3.

共有15臺AGV可供使用，假設AGV重車平均行駛速度為3 m/s，空車平均行駛速度為4 m/s，AGV在空車行駛狀態下的耗電率為0.01%/m，重車耗電率為0.02%/m，因為考慮了等待時間，設置等待狀態下的耗電率為0.005%/s.使用兩個換電站，每個換電站同一時刻只允許一臺AGV進行換電工作，換電站的作業時間誤差不考慮，即每一個AGV換電時間相同，均為300 s/臺，換電站內的電池儲備充足.設置遺傳算法中種群大小N_pop=100，最大迭代次數MAXGEN=200.其他參數都相同，換電SOC值為60%時，通過對在不同的Pc和Pm值條件下進行10次實驗得到的平均makespan(最末完成任務時間)的對比，最終擇優選擇交叉概率Pc=0.7，變異概率Pm=0.05.

表3 節點坐標

4.2 實驗結果分析

換電SOC臨界值是換電模式的核心，也是模型中最重要的決策變量.依次設置SOC臨界值為60%，70%，80%，90%和100%，進行五組實驗對比，結果見表4.由表4可知，換電SOC值越大換電次數越少，最末任務完成時間并沒有隨著SOC值的增大而持續降低.在實際營運過程中，除了實現降低總的任務完成時間目標外，還需考慮AGV在前往換電站過程中以及在換電站的排隊等待過程中的能量消耗，那么，設置一定的冗余電量來應對一些不確定性是有必要的.因此，綜合來看，較優的方案為換電SOC臨界值取值70%.

表4 不同換電SOC值條件下的結果對比

利用Matlab R2016b軟件編程設計遺傳算法進行問題的求解，采用上述參數，并設置種群數為N_pop=200，迭代代數MAXGEN=500，遺傳算法迭代計算的收斂過程見圖7，得出的近似最優解對應的AGV作業甘特圖見圖8.由圖7可知，在170代的時候已收斂至近似最優解.圖8中灰色矩形表示AGV換電時間.由圖8可知，在該方案下有4臺AGV進行了換電，且AGV在換電站排隊等待時間較短.15臺AGV的最大最末任務完成時間為3 103.8 s，同表2中最末任務的最早可開始時間2 992 s相比時間間隔很小，即該方案所需要的所有任務完成時間同初始設置的AGV最末任務開始執行時間之間的增量較小，可以認為是合理可行的調度方案.

圖7 遺傳算法收斂過程

圖8 AGV作業甘特圖

5 結 束 語

針對實際運營中的自動化集裝箱碼頭AGV作業效率待提升的問題，從AGV換電管理優化和AGV換電與作業集成調度的視覺，構建調度模型并采用遺傳算法求解.模型中區分了AGV實際生產作業中不同狀態下AGV的耗電特性，模型決策變量除了集裝箱是否分配到某臺AGV之外，還包括AGV換電過程中的關鍵決策問題——換電SOC值.通過數值實驗分析得出結論：合理的換電SOC值同換電次數及總的任務完成時間相關，AGV換電與作業協同調度可以有效減少AGV在換電站的排隊等待時間，從而提高自動化集裝箱碼頭AGV的整體作業效率.

需要指出的是，由于關注重點是AGV的作業效率，故只考慮了AGV等待岸橋或龍門吊準備集裝箱的時間，沒有考慮岸橋或龍門吊等待AGV的時間.從提高碼頭總的裝卸效率的角度來看，設備之間的配合、協調，以及設備數量匹配等也都是非常值得研究的問題.