自動化集裝箱碼頭多層設備調度及仿真分析

王盼龍，梁承姬，王 鈺

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

隨著進出口貿易的不斷發(fā)展，我國貨物吞吐量持續(xù)攀升。2022年上半年，在疫情影響之下，全國港口仍完成貨物吞吐量89.2億t，同比增長0.1%；完成集裝箱吞吐量1.7 億TEU，同比增長4.2%[1]。碼頭作為貨物進出口的主要樞紐，如何提升其運作效率成了各港口及國內外學者關注的焦點。自動化碼頭因其節(jié)能減排、作業(yè)安全、裝卸效率高等特點，越來越受到各大港口青睞。2017年，先后有青島全自動化集裝箱碼頭和上海洋山全自動化集裝箱碼頭投入運營。自動化集裝箱碼頭引入了ARMG（自動化軌道吊，automated rail mounted gantry crane）、AGV（自動化導引小車，automated guided vehicle）、雙小車岸橋。以洋山港四期為例，截止2022年6月共擁有23 臺岸橋、114 臺軌道吊、125 臺AGV。2021 年洋山四期全年吞吐量達到了570萬之高，在如此龐大的體量之下，保證岸橋門架小車、岸橋主小車、AGV、軌道吊之間的緊密協(xié)同配合就顯得尤為重要。在傳統(tǒng)的調度作業(yè)中，往往將裝卸、水平運輸、堆存三個環(huán)節(jié)單獨考慮，造成實際操作中各個環(huán)節(jié)經(jīng)常需要互相等待，增加了設備的閑置時間，降低了碼頭的作業(yè)效率。對岸橋門架小車、岸橋主小車、AGV、場橋四層設備進行集成調度，將每個環(huán)節(jié)的優(yōu)化視為整體的一部分，能夠有效提高整個裝卸系統(tǒng)的作業(yè)效率，促進集裝箱碼頭各種運輸方式之間的無縫連接[2]。

國內外許多文獻研究了碼頭設備的協(xié)同調度問題，其中包括兩種設備的協(xié)同調度和三種設備的協(xié)同調度問題，這些研究中大多采用啟發(fā)式算法、群智能算法或兩者結合。對于兩種設備的協(xié)同調度問題，馬孫豫等[3]研究了雙小車岸橋與AGV 的協(xié)同調度問題，建立以卸船任務結束時間最小化為目標的混合整數(shù)規(guī)劃模型，采用多層編碼粒子群算法進行了求解。劉彪等[4]建立了以AGV的總行駛時間和岸橋的總延遲時間最小為目標的多目標優(yōu)化模型，提出改進遺傳算法進行了求解。湯鵬飛等[5]建立了以岸橋作業(yè)延遲時間、ALV總行駛時間及岸橋等待ALV的時間之和最小為目標的ALV調度混合整數(shù)規(guī)劃模型，采用遺傳算法進行求解。梁承姬等[6]研究了AGV 與雙小車岸橋的協(xié)同調度問題，考慮雙小車岸橋中轉平臺及其容量限制，設計啟發(fā)式算法進行了求解。Yue 等[7]對雙四十尺雙小車岸橋與AGV 的調度問題進行了研究，建立了兩階段雙目標混合整數(shù)規(guī)劃模型進行求解。Chen等[8]提出軌道吊和AGV兩組流平衡的多商品網(wǎng)絡流模型，引入了交替方向乘子法（ADMM）進行了相應計算。Zhang 等[9]研究了軌道吊和AGV 的協(xié)同調度問題，引入握手區(qū)概念，以最小化AGV等待時間和自動化軌道吊運行時間為目標建立模型進行求解。

對于三種設備的多層協(xié)同調度問題，Luan等[10]研究了岸橋、AGV、場橋三種設備的集成調度問題，考慮了容量約束并引入雙循環(huán)策略。Yang 等[11]提出了裝卸設備協(xié)調和AGV 路徑選擇的集成調度方法，建立了雙層規(guī)劃模型，結合了滾動時域和雙層遺傳算法對問題進行了求解。Yue等[12]提出了一個兩階段模型去最小化裝卸船期間的能源消耗、最大化AGV的利用率。Ji等[13]建立了兩階段模型，第一階段利用自適應遺傳算法去計算岸橋、AGV、場橋的集成調度問題，第二階段利用遺傳算法解決AGV 的路徑規(guī)劃問題。He 等[14]研究了岸橋、內集卡、場橋聯(lián)合調度的問題，用優(yōu)化算法進行求解，用仿真設計進行評估。仲昭林等[15]結合AGV路徑無沖突約束，建立了以最小化船舶在港時間和最小化總能耗為目標的多目標混合整數(shù)規(guī)劃模型，設計了雙層遺傳算法進行求解，針對集裝箱作業(yè)規(guī)模和決策目標進行仿真實驗。Lau等[16]建立了最小化岸橋延誤時間、AGV和場橋總運行時間的集成調度模型，算例結果顯示最大匹配遺傳算法的求解效果要優(yōu)于多層遺傳算法。黃永付等[17]針對碼頭卸船過程中岸橋、AGV 和場橋的集成調度問題，以最小化卸船完工時間為目標，確定各裝卸設備作業(yè)序列并優(yōu)化緩存位-任務的分配關系。秦琴等[18]針對雙小車岸橋+AGV+緩沖支架+自動化軌道吊的裝卸工藝，利用柔性流水車間調度理論建立集成調度優(yōu)化模型，設計了NEH 啟發(fā)式算法產(chǎn)生初始解的遺傳算法進行求解。Luo 等[19]以最小化船舶靠泊時間為目標，對場橋、AGV、岸橋的聯(lián)合調度問題建立了混合整數(shù)規(guī)劃模型，利用自適應遺傳算法進行了求解，并測試了自適應遺傳算法的效率。

從以上研究中可以發(fā)現(xiàn)：

（1）對于自動化集裝箱碼頭場橋、AGV、雙小車岸橋三種設備多層聯(lián)合調度的研究并不多，且已有的研究大多未對設備的調度規(guī)則做出詳細分析，而碼頭設備調度過程中所遇到的情況繁多，調度規(guī)則的分析有助于說明調度算法的合理性。

（2）對于雙小車岸橋中轉平臺的研究，基本集中在平臺容量的約束，很少考慮箱子進出平臺的次序，而對于能夠容納多個箱子的平臺，箱子進出平臺的次序又直接影響裝卸效率。

（3）對于場橋、AGV、雙小車岸橋聯(lián)合調度的研究，由于問題的復雜性，大部分學者選擇忽略AGV 的擁堵因素，而AGV 擁堵又是影響碼頭作業(yè)效率的關鍵因素之一。在自動化集裝箱碼頭中，AGV 擁堵問題作為路徑規(guī)劃的重點問題，可能導致碼頭吞吐量最多下降達85%[20]。

（4）在以往的碼頭設備調度問題的研究中，很少采用優(yōu)化算法與仿真結合的方式，由于碼頭多層設備調度過程中動態(tài)因素較多，而仿真軟件便于將設備動態(tài)作業(yè)的過程展現(xiàn)出來，不僅能驗證數(shù)學模型是否考慮全面，還能彌補數(shù)學模型難以分析動態(tài)因素的劣勢。

為了解決上述問題，本文做出了如下創(chuàng)新：

（1）詳細分析了集裝箱經(jīng)由場橋、AGV、雙小車岸橋多層設備聯(lián)合吊運時的各種規(guī)則，構建了基于時空節(jié)點表示方法的裝船任務時空流動圖，又通過plant-simulation仿真軟件對碼頭生產(chǎn)過程進行了模擬，用理論分析加仿真實現(xiàn)的方式對調度規(guī)則進行了展現(xiàn)，同時獲取了實驗所需數(shù)據(jù)。

（2）在上述多層設備聯(lián)合吊運規(guī)則的基礎上，考慮了設備的互相等待時間、箱子進出中轉平臺次序、中轉平臺容量等約束，建立了以最大完工時間最小化為目標的由堆場到船上的多層設備全流程運作集成調度模型，通過自適應遺傳算法求解出場橋、AGV、雙小車岸橋的多層設備聯(lián)合調度方案，并與禁忌搜索算法和模擬退火算法進行了對比，驗證了模型及算法的有效性。

（3）提出算法與仿真結合的方式，將調度方案在仿真中進行了實施，利用仿真可直觀展示動態(tài)過程的優(yōu)勢，即保證了算法所得解的可行性又進一步驗證了模型和算法的有效性。

（4）根據(jù)求得的調度方案在仿真場景中提出隨機路線、固定路線、分組隨機路線三種AGV運作策略并進行完工時間、設備等待時間、AGV擁堵次數(shù)的對比，通過對不同AGV運作策略進行分析來將調度方式進一步優(yōu)化。

1 問題描述

1.1 自動化集裝箱碼頭多層設備協(xié)調

圖1 展示了自動化集裝箱碼頭多層設備布局。陸側場橋負責堆場裝卸箱，為第一層設備；AGV負責水平運輸為第二層設備；岸橋門架小車負責將箱子從AGV上吊運至中轉平臺，為第三層設備；岸橋主小車負責將箱子從中轉平臺上吊運至船上，為第四層設備。

圖1 多層設備協(xié)同布局Fig.1 Layout of multi-layer equipment collaboration

在裝船過程中場橋接到任務指令后前往目標箱所在場箱位處，將集裝箱提起并吊運至堆場前交接點。AGV 接到任務指令后前往堆場前交接點處，接收并轉運集裝箱至雙小車岸橋下交接點。若場橋與AGV未能同時到達堆場前交接點，則先到者產(chǎn)生等待。雙小車岸橋門架小車接到指令后前往岸橋下交接點，若門架小車與AGV 未能同時到達岸橋下交接點，則先到者產(chǎn)生等待。門架小車提起集裝箱后將箱子吊運至岸橋中轉平臺，若中轉平臺有空閑位置，則將集裝箱直接放置于空閑位置，若中轉平臺無空閑位置，則需等待岸橋主小車從平臺上吊走一個任務箱。岸橋主小車接到任務指令后前往中轉平臺處吊運集裝箱至船上，若中轉平臺為空，則主小車需等待集裝箱到達中轉平臺。

1.2 基于多層設備運作規(guī)則的時空流動圖

本文引入了一種時空節(jié)點的方式將碼頭場景進行了節(jié)點劃分，由陸側到海側節(jié)點編號依次增大。圖2是裝船過程中第一個任務箱的軌跡，圖中共有5 種弧，分別為移動弧、等待弧、提箱弧、放箱弧、恢復弧，其中紅色弧表示場橋軌跡，黑色弧表示岸橋大車軌跡，綠色弧表示岸橋門架小車軌跡，淺藍色弧表示岸橋主小車軌跡，深藍色弧表示AGV軌跡。當兩種設備的軌跡弧產(chǎn)生交叉時，表示箱子到達交接點。每一段弧都有對應的坐標，例如移動?。?0，6，0，6）表示該設備從節(jié)點10 移動到節(jié)點6，起始移動時刻為0，到達節(jié)點6的時刻為6。圖中場橋先通過移動弧（6，3，0，3）由節(jié)點6移動到箱子堆存的位置節(jié)點3，然后在節(jié)點3進行提箱作業(yè)，分別經(jīng)歷了提箱?。?，4，3，4）和恢復?。?，3，4，5），整個提箱作業(yè)從時刻3開始到時刻5結束。場橋提完箱后在時刻5從節(jié)點3 出發(fā)，在時刻8 到達節(jié)點6，形成移動?。?，6，5，8）。在時刻8，AGV經(jīng)歷了移動?。?0，6，0，6）和等待?。?，6，6，8）后到達節(jié)點6，在節(jié)點6 場橋和AGV 進行箱子的交接，場橋經(jīng)過了放箱?。?，5，8，9）和恢復?。?，6，9，10）后，將箱子交接給了AGV。AGV從節(jié)點6出發(fā)移動至節(jié)點11，形成移動?。?，11，10，16）。在時刻16，岸橋經(jīng)過了等待?。?1，11，0，16），在節(jié)點11 處與AGV 進行交接。岸橋門架小車進行提箱動作，形成提箱?。?1，12，16，17）和恢復?。?2，11，17，18）。岸橋門架小車接到箱子后，從節(jié)點11移動至節(jié)點13到達中轉平臺上方，形成了移動弧（11，13，18，19），然后進行放箱動作。箱子放到中轉平臺后，岸橋主小車從中轉平臺上提起箱子，經(jīng)過提箱?。?3，14，21，22）和恢復?。?4，13，22，23）。主小車提起箱子后移動至船上箱子要堆存的貝位，經(jīng)過移動?。?3，15，23，24），最后主小車進行放箱動作，將箱子放到船上，產(chǎn)生放箱?。?5，14，24，25）和恢復?。?4，15，25，26），至此該裝船箱任務結束。

圖2 多層設備協(xié)同作業(yè)時空流動圖Fig.2 Time and space flow of multi-layer equipment collaboration

1.3 裝船任務完工時間計算

裝船任務完工時間即為最后一個任務箱裝上船的時間，本文以最小化完工時間為目標，建立了多層設備協(xié)同調度模型，利用自適應遺傳算法對該模型進行了求解，在理想時間內得到了較優(yōu)的多層設備協(xié)同調度方案并將該方案在仿真中進行了實施。

場橋作為第一層設備，其吊運一個任務箱的時間計算邏輯見圖3。在場橋到堆場中進行提箱時，需要判斷場橋在做該任務箱之前是否還做了其他任務。若做了其他任務，則場橋開始抓該任務箱的時間即為場橋做完上一個任務箱后來到本次任務箱位置的時間，該任務箱到達場橋與AGV交接點的時間點為場橋抓完上一個箱后來到本次任務箱位置的時間點加上場橋將箱子從堆場提起至將箱子放到AGV上的時間。若場橋做該任務箱之前沒做其他任務，則該任務箱為這臺場橋作業(yè)的第一個任務，場橋開始抓本次任務箱的時間記為0，該任務箱到達場橋與AGV交接點的時間為場橋將箱子從堆場提起至將箱子放到AGV上的時刻。

圖3 第一層設備作業(yè)時間計算邏輯Fig.3 Logic for calculating working time of first layer of equipment

AGV 作為第二層設備，其載運一個任務箱的時間計算邏輯見圖4。當箱子到達堆場前的交接點時，需要判斷分配給該箱子的AGV在作業(yè)該任務箱之前是否還作業(yè)了其他箱子。若之前作業(yè)了其他箱子，則箱子交接給AGV 的時間為AGV 作業(yè)完上一個箱子后回到堆場交接點處的時間與場橋帶著箱子到達交接點處的時間之間取較大值，箱子到達岸橋下交接點的時間為該較大值加上AGV將箱子運輸至岸橋下交接點的時間。若該任務箱是AGV作業(yè)的第一個箱子，則AGV接到箱子的時間為場橋到達交接點的時間與AGV從起始位置出發(fā)后到達場橋交接點的時間之間的較大值，箱子到達岸橋下交接點的時間為該較大值加上AGV將箱子運輸至岸橋下交接點的時間。

圖4 第二層設備作業(yè)時間計算邏輯Fig.4 Logic for calculating working time of second layer of equipment

岸橋門架小車作為第三層設備，其吊運一個任務箱的時間計算邏輯見圖5。當箱子到達岸橋下交接點時，需判斷岸橋門架小車在作業(yè)該任務前是否還作業(yè)了其他任務。若之前作業(yè)了其他任務，則比較門架小車作業(yè)完上一個任務箱后回到交接點處的時間與AGV帶著箱子到達岸橋下交接點處的時間，取兩者的較大值記為M。然后判斷岸橋在做該任務箱之前所做的任務數(shù)量是否小于2，若小于2則中轉平臺上一定有位置，門架小車從AGV上提起集裝箱的時間即為M，箱子放到中轉平臺上的時間即為M加上門架小車處理箱子的時間。若岸橋之前所做的任務數(shù)量大于等于2，則將該任務箱記為岸橋作業(yè)的第i個箱，在岸橋作業(yè)的第i-2 個箱被岸橋主小車提起的時刻與M之間取較大值，記為N，則N為門架小車將箱子從AGV 上提起的時間。箱子放到中轉平臺上的時間為N加上門架小車處理箱子的時間。若門架小車之前沒有作業(yè)過其他任務，則中轉平臺上一定有位置，門架小車提箱時間即為AGV 帶著箱子到達岸橋下交接點處的時間，箱子被放到中轉平臺上的時間即為AGV到達交接點的時間加上門架小車處理箱子的時間。

圖5 第三層設備作業(yè)時間計算邏輯Fig.5 Logic for calculating working time of third layer of equipment

岸橋主小車為第四層設備，其作業(yè)時間判斷邏輯見圖6。箱子到達中轉平臺時，需判斷該任務箱是否為主小車作業(yè)的第一個任務，若是第一個任務，則箱子放上船的時間為：箱子到達中轉平臺的時間加上主小車處理該任務箱的時間；若不是第一個任務，則在主小車做完上一個任務后回到中轉平臺的時間點與箱子到達中轉平臺的時間點之間取較大值，記為P，箱子放上船的時間為P加上主小車處理該箱子的時間。

圖6 第四層設備作業(yè)時間計算邏輯Fig.6 Logic for calculating working time of fourth layer of equipment

1.4 AGV運作策略

為了證明算法的合理性及優(yōu)化調度方式，提出了AGV的隨機路線、固定路線、分組隨機路線三種運作策略。

隨機路線策略中AGV 為作業(yè)面調度，被所有設備共享，即AGV 可服務于任意場區(qū)和岸橋，根據(jù)AGV 的目的地選擇較近的行駛路線，見圖7。

圖7 隨機路線策略路線布局Fig.7 Random route strategy route layout

固定路線行駛策略中AGV固定的服務于某一場區(qū)和岸橋，AGV 只能在固定的路線上行駛，見圖8。圖中不同顏色的箭頭分別代表不同組的AGV 路線，黃色箭頭為服務于岸橋QC1和場區(qū)B1的AGV路線，紅色箭頭為服務于岸橋QC2和場區(qū)B2的AGV路線，綠色箭頭為服務于岸橋QC3和場區(qū)B3的AGV路線，粉色箭頭為服務于岸橋QC4 和場區(qū)B4 的AGV 路線，AGV 只能在一條路線行駛，不能跨越到其他路線。

圖8 固定路線策略布局圖Fig.8 Fixed route strategy route layout

分組隨機策略中將場區(qū)和岸橋劃分為兩組，紅色分隔線左右兩側分別為一組，在每一個分組內仍采用隨機策略運行，見圖9。

圖9 分組隨機路線策略布局圖Fig.9 Grouping random strategy route layout

1.5 仿真場景

基于上文自動化集裝箱碼頭多層設備協(xié)同作業(yè)規(guī)則，在plant-simulation仿真軟件中搭建裝船運作場景如圖10，該場景包含一條150 m長的船、四臺場橋、四臺雙小車岸橋，分別對不同規(guī)模的任務進行仿真，并獲取相關數(shù)據(jù)，仿真場景見圖10。

圖10 仿真場景Fig.10 Simulation scene

仿真實驗旨在證明算法的有效性及提高算法的適用性。本文在仿真場景中對算法所求多層設備協(xié)同調度方案進行了實施，對所提出的隨機路線、固定路線、分組隨機路線三種AGV 運作策略進行了詳細分析，彌補了模型及算法難以分析動態(tài)因素的劣勢。

綜上，自動化集裝箱碼頭多層設備集成調度運作規(guī)則極其繁雜，如果設備調度方案不合理，就極易造成等待時間增加和阻塞嚴重，從而使得最終完工時間增加。為解決這一問題，本文以最小化最大完工時間為目標，考慮了各設備之間的互相等待時間、中轉平臺的容量約束、任務箱進出中轉平臺的次序等，利用plant-simulation仿真軟件對碼頭多層設備聯(lián)合調度的運作過程進行了模擬，建立了多層設備集成調度的模型，通過自適應遺傳算法對模型進行了求解，并與禁忌搜索算法和模擬退火算法進行了對比。將算法求得的調度方案在仿真中進行了實施，驗證了算法的有效性。最后基于求得的調度方案在仿真場景中對AGV隨機路線、固定路線、分組隨機路線三種運作策略下的完工時間、設備互相等待時間、擁堵次數(shù)等進行詳細分析，進一步證明算法有效性的同時找出了能最大化算法效用的運作方式。

2 數(shù)學模型構建

本文研究了場橋、AGV、岸橋門架小車、岸橋主小車的多層設備聯(lián)合調度問題，以最小化最大完工時間為目標，建立了多層設備集成調度模型，對設備調度方案進行了優(yōu)化，已知條件如下：

（1）任務箱的堆存位置已知；

（2）場橋將任務箱由堆存位置送到固定交接點所需的時間已知；

（3）任務箱、場橋、岸橋、AGV的數(shù)量已知；

（4）模型中AGV被所有的岸橋和場橋共享；

（5）AGV在任意兩個節(jié)點間的運行時間已知；

（6）場橋、岸橋門架小車、岸橋主小車處理每個集裝箱所需時間已知。

2.1 模型假設

（1）場橋、岸橋主小車、岸橋門架小車、AGV分別一次只能處理一個集裝箱；

（2）不考慮翻箱問題；

（3）AGV擁堵在模型中不考慮，在仿真實施時考慮；

（4）任務箱均為40英尺；

（5）雙小車岸橋中轉平臺可容納兩個40英尺集裝箱。

2.2 模型參數(shù)及決策變量

2.2.1 模型參數(shù)

K：場橋集合，編號為{1…k}，k∈K；

V：AGV集合，編號為{1…v}，v∈V；

Q′：岸橋門架小車集合，編號為{1…q′}，q′∈Q′；

Q"：岸橋主小車集合，編號為{1…q"}，q"∈Q"；

L：所有任務的集合，編號為{1…i}，i∈L；

O：虛擬起始任務；

θ：虛擬終止任務；

M：足夠大的正數(shù)；

U：中轉平臺上緩存位置的集合，編號為{1…u}，u∈U；

2.2.2 決策變量

pui為0-1變量，任務i被分配給中轉平臺上的緩存位u則為1，否則為0。

2.3 目標函數(shù)及約束條件

式（1）為最小化最大完工時間目標函數(shù)，完工時間為最后一個任務箱被岸橋主小車裝上船的時間。

關于場橋的約束：

式（2）表示一個任務箱只能被處理一次；式（3）表示一臺場橋一次只能處理一個集裝箱；式（4）為保證集裝箱按次序被場橋處理；式（5）為場橋處理任務箱的時間約束，表示當場橋k依次處理任務箱i和任務箱j時，處理任務箱j的開始時間應等于場橋處理完任務箱i后來到任務箱j所在位置的時間。式（6）表示場橋k處理完任務箱i的時間應等于開始處理任務箱i的時間加上處理的時間。

關于AGV的約束：

式（7）表示一個任務箱只能被處理一次；式（8）表示AGV一次只能運送一個任務箱；式（9）為保證集裝箱按次序被AGV運送；式（10）表示若AGV依次運送任務箱i和j，則AGV運送任務箱j的開始時間應等于或晚于AGV 運送任務箱i的結束時間加上結束任務箱i后來到任務箱j所在位置的空載時間。式（10）、（11）聯(lián)合表示當AGV 依次處理任務箱i和j時，AGV 開始處理任務箱j的時間為在場橋處理任務箱j的結束時間與AGV 處理完任務箱i后回到場橋交接點的時間之間取較大值。式（12）表示AGV運送任務箱i的結束時間應等于運送任務箱i的開始時間加上運輸時間。

關于岸橋門架小車的約束：

式（13）表示一個任務箱只能被岸橋門架小車處理一次；式（14）表示岸橋門架小車一次只能處理一個任務箱；式（15）表示岸橋門架小車必須按次序處理任務箱；式（16）表示任務箱只有一個緊前任務和一個緊后任務；式（17）表示若岸橋門架小車依次處理任務箱i和j，則門架小車開始處理任務箱j的時間應等于或晚于門架小車處理完任務箱i后回到岸橋下交接點的時間；式（17）、（18）表示當岸橋門架小車依次處理任務箱i和j時，岸橋門架小車開始處理任務箱j的時間為在AGV處理任務箱j的結束時間與岸橋門架小車處理完任務箱i后回到岸橋下交接點的時間之間取較大值。式（19）表示岸橋門架小車處理任務箱i的結束時間等于處理任務箱i的開始時間加上處理時間。

關于岸橋主小車的約束：

式（20）表示一個任務箱只能被處理一次；式（21）表示岸橋主小車一次只能處理一個任務箱；式（22）為保證岸橋主小車按次序處理任務箱；式（23）表示任務箱只有一個緊前任務和一個緊后任務；式（24）表示若岸橋主小車依次處理集裝箱i和j，則開始處理任務箱j的時間應等于或晚于執(zhí)行完任務i后岸橋主小車回到中轉平臺的時間；式（24）、（25）聯(lián)合表示當岸橋主小車依次處理任務箱i和j時，岸橋主小車開始處理任務箱j的時間為在岸橋門架小車處理任務箱j的結束時間與岸橋主小車處理完任務箱i后回到中轉平臺的時間之間取較大值。式（26）表示岸橋主小車處理任務箱i的結束時間等于處理任務箱i的開始時間加上處理時間。

關于岸橋中轉平臺的約束：

式（27）表示每個任務箱只分配給一個中轉平臺上的緩存位；式（28）表示一個緩存位只能放一個任務箱；式（29）表示岸橋門架小車從AGV上提起岸橋作業(yè)的第x個任務箱i的時間應晚于岸橋主小車將岸橋作業(yè)的第x-2 個任務箱從中轉平臺上提起的時間。

3 模型求解

由于全設備調度問題變量規(guī)模巨大，難以用精確算法進行求解，而遺傳算法、禁忌搜索算法、模擬退火算法等具有全局搜索能力的啟發(fā)式算法在諸如此類調度問題中已有所應用，并取得了一定效果。盡管有很多新的啟發(fā)式算法被用在碼頭的設備調度問題中，但因為自適應遺傳算法中的染色體能夠很方便地將問題的決策變量表示出來，且能夠在較短時間內求得結果，所以自適應遺傳算法依然很適用于去研究[19]。本文基于裝船過程中的設備調度規(guī)則，引入了自適應遺傳算法，如圖11。

圖11 算法流程圖Fig.11 Algorithm flow chart

算法步驟如下：

步驟1隨機生成初始種群P。

步驟2對種群P進行個體評價，計算適應度。

步驟3采用了隨機通用采樣和精英保留策略結合的方法對種群P進行了選擇操作。

步驟4交叉后產(chǎn)生種群P1，計算種群P1 的適應度標準差。

步驟5對種群P1 進行變異操作產(chǎn)生種群P2，計算種群P2 的適應度標準差。

步驟6比較種群P1 和種群P2 的適應度標準差，若P2 適應度標準差小于P1，說明P2 的種群多樣性較差，則將變異率pm增加0.01；否則，保持變異率不變。

步驟7將經(jīng)過選擇、交叉、變異操作后得到的候選種群與父代精英保留策略下保留下來的優(yōu)秀個體進行了重插入操作，得到了子代種群。

步驟8判斷是否達到迭代終止條件，若未達到，則將子代種群作為下一代的父代種群，重復步驟2～7；若達到，則結束。

3.1 自適應遺傳算法

（1）染色體編碼

采用實數(shù)編碼方式，任務箱的數(shù)量即為染色體的長度。如圖12 所示，為三臺AGV、三臺場橋、兩臺岸橋協(xié)同處理九個集裝箱。以染色體第一列為例（4，3，2，2）表示集裝箱4分別被3號AGV、2號場橋、2號岸橋處理，染色體其他列以此類推。從單個設備來看，各設備處理任務的次序都為從左至右，1 號AGV 先后處理（2，3，1，5）四個集裝箱，2 號AGV 先后處理（9，6，7）三個集裝箱，3號AGV 先后處理（4，8）兩個集裝箱；1 號場橋先后處理（2，3，1）三個集裝箱，2號場橋先后處理（4，6，5）三個集裝箱，3 號場橋先后處理（9，7，8）三個集裝箱；1 號岸橋先后處理（2，9，6，7，8）五個集裝箱，2 號岸橋先后處理（4，3，1，5）四個集裝箱；以此方法來確定各設備作業(yè)的任務及作業(yè)次序。

圖12 染色體示例Fig.12 Chromosome example

（2）種群初始化

本文在考慮約束條件的前提下，采用隨機生成法產(chǎn)生初始種群。

（3）目標函數(shù)計算

模型以最小化最大完工時間為目標，對由堆場到船上這一作業(yè)過程中場橋、AGV、岸橋門架小車、岸橋主小車四層設備協(xié)調作業(yè)的調度方案進行了計算，四層設備之間的詳細協(xié)調規(guī)則見1.1～1.2 節(jié)，算法的設計即是基于該協(xié)調規(guī)則。

算法中目標函數(shù)即完工時間的計算邏輯見1.3 節(jié)，將該計算邏輯轉化為數(shù)學模型后，算法對模型中約束的具體處理示例如下：

以圖12 中染色體為例，從左至右依次計算各集裝箱的完工時間，再取出所有集裝箱的完工時間的最大值，即為所有任務的總完工時間。以圖12 染色體中第一個箱號為4的集裝箱的完工時間的計算為例，其依次被2 號場橋、3 號AGV、2 號岸橋作業(yè)，詳細計算方法如下文，其中各約束公式對應的詳細解釋見2.3節(jié)，其余集裝箱完工時間的計算方法與此相同。

對于第一層設備場橋，先根據(jù)式（2）～（6）對2 號場橋處理4號集裝箱的完工時間進行計算。首先判斷4號集裝箱是否為2號場橋的首個任務，若為首個任務，則2號場橋開始處理4 號集裝箱的時間記為0，因此可根據(jù)式（6）直接得出2號場橋處理4號集裝箱的完工時間；若4號集裝箱不是2號場橋的首個任務，則需根據(jù)式（5）得出2號場橋開始處理4號集裝箱的時間，再根據(jù)式（6）得出2號場橋處理4號集裝箱的完工時間。

對于第二層設備AGV，根據(jù)式（7）～（12）對3 號AGV 處理4 號集裝箱的完工時間進行計算。首先判斷4 號集裝箱是否為3 號AGV 的首個任務，若為首個任務，則3號AGV開始處理4號集裝箱的時間為2號場橋處理4 號集裝箱的完工時間；若4 號集裝箱不是3 號AGV的首個任務，則需聯(lián)合式（10）、（11）得出3號AGV開始處理4 號集裝箱的時間，再根據(jù)式（12）得出3 號AGV處理4號集裝箱的完工時間。

對于第三層設備岸橋門架小車，根據(jù)式（13）～（19）對2號岸橋門架小車處理4號集裝箱的完工時間進行計算。首先判斷4號集裝箱是否為2號岸橋門架小車作業(yè)的前兩個任務。如果4號集裝箱是2號岸橋門架小車作業(yè)的前兩個任務，則由式（27）、（28）及中轉平臺可容納兩個40 英尺集裝箱可知中轉平臺上一定有空位，此時若4 號集裝箱為2 號岸橋門架小車的首個任務，則2 號岸橋門架小車開始處理4 號集裝箱的時間為3 號AGV處理4號集裝箱的完工時間。若4號集裝箱是2號岸橋門架小車的第二個任務，則先聯(lián)合式（17）、（18）得出2號岸橋門架小車開始處理4 號集裝箱的時間，即在3 號AGV 處理4 號集裝箱的結束時間與2 號岸橋門架小車處理完上一個任務箱后回到岸橋下交接點的時間之間取較大值，再根據(jù)式（19）得出2 號門架小車處理4 號集裝箱的完工時間。如果4號集裝箱不是2號岸橋門架小車的前兩個任務，則岸橋中轉平臺上可能沒有位置，需要聯(lián)合式（17）、（18）和式（29）來計算2號岸橋門架小車開始處理4 號集裝箱的時間，其中式（29）用于保證2 號岸橋門架小車開始處理4號集裝箱的時間應晚于2號岸橋主小車將4 號集裝箱之前的第二個箱子從中轉平臺上提起的時間，即當2 號岸橋主小車將4 號集裝箱之前的第二個箱子從中轉平臺上提起后，中轉平臺上才有空位置；計算出2 號門架小車處理4 號集裝箱的開始時間后，再根據(jù)式（19）得出該操作的完工時間。

對于第四層設備岸橋主小車，根據(jù)式（20）～（26）對2 號岸橋主小車處理4 號集裝箱的完工時間進行計算。首先判斷4 號集裝箱是否為2 號岸橋主小車的首個任務，若為首個任務，則2號岸橋主小車開始處理4號集裝箱的時間為2號岸橋門架小車處理4號集裝箱的完工時間；若4號集裝箱不是2號岸橋主小車的首個任務，則需聯(lián)合式（24）、（25）得出2 號岸橋主小車開始處理4 號集裝箱的時間，再根據(jù)式（26）得出2 號岸橋主小車處理4號集裝箱的完工時間，即該任務箱裝上船的時間。

（4）適應度計算

適應度函數(shù)采用目標函數(shù)的倒數(shù)，適應度值較大的個體其完工時間較小。

其中，T為一個調度方案的完工時間。

（5）選擇算子的設計

采用隨機通用采樣（stochastic universal sampling）與精英保留策略結合的選擇方法。精英保留策略用于避免優(yōu)良個體的丟失。

（6）交叉算子設計

對于表示集裝箱的部分，采用部分匹配法交叉（partially matching crossover），對于AGV 和岸橋部分采用均勻交叉，如圖13、圖14所示。

圖13 部分匹配交叉Fig.13 Partially matching crossover

圖14 均勻交叉Fig.14 Uniform crossover

（7）變異算子設計

本文對變異前后父代和子代種群適應度的標準差進行比較，若子代小于父代，則將變異率增加0.01；若子代大于或等于父代，則保持變異率不變。

3.2 結果分析

為了驗證模型及算法的有效性，本節(jié)運用了模型算法與仿真運行結合的方法。先運行仿真模型，獲取場橋作業(yè)各任務箱的起步空載時間、重載時間、兩個任務之間的空載時間;獲取AGV 在各岸橋交接點和場橋交接點之間運行所需行駛時間；獲取岸橋門架小車和主小車的單箱作業(yè)時間。再將獲取的基礎數(shù)據(jù)分別代入自適應遺傳算法（AGA）、禁忌搜索算法（TS）、模擬退火算法（SA）中，進行了16組不同任務規(guī)模的對比實驗，對每組實驗求解10次，以平均值作為最終結果，各算法所得調度方案均放回仿真模型中進行運行，以確保解的可行性及觀察模型是否考慮問題全面。運行結果見表1及圖15。實驗運用plant-simulation15.0.0 及MATLAB 2018a，運行環(huán)境為Window10操作系統(tǒng)，Intel?CoreTMi7-7700HQ CPU@2.80 GHz，8 GB內存。

表1 AGA-TS-SA算法數(shù)據(jù)對比Table 1 Data comparison of AGA-TS-SA algorithm

圖15 AGA、TS和SA完工時間對比Fig.15 Comparison of completion time of AGA，TS and SA

從實驗結果可以看出：

（1）在16 組實驗中有13 組為自適應遺傳算法求得的解優(yōu)于禁忌搜索和模擬退火。

（2）在16 組實驗中有11 組為自適應遺傳算法計算時間小于模擬退火算法；有16 組為自適應遺傳算法計算時間小于禁忌搜索算法。

（3）以表1中實驗4及實驗14為例，實驗4中集裝箱數(shù)量為20，AGV數(shù)量為6，完工時間為16.6 min；實驗14中集裝箱數(shù)量為40，AGV數(shù)量為6，完工時間為35 min，基本符合現(xiàn)階段自動化碼頭作業(yè)調度時間。

（4）隨著集裝箱數(shù)量增多，完工時間也隨之增加；同等任務數(shù)時，一定程度上增加AGV 數(shù)量可以提高裝卸效率。

為了進一步比較三種算法的性能，分別在不同規(guī)模任務下對三種算法的收斂性進行對比，結果見圖16、圖17。其中圖16 和圖17 分別為集裝箱數(shù)為20 和40 時的收斂情況。從圖中可以看出，自適應遺傳算法的收斂時間隨著任務規(guī)模的增大而增大，且收斂結果優(yōu)于另外兩種算法，這是由于自適應遺傳算法采用自適應變異策略使得算法能夠跳出局部最優(yōu)解，而其他兩種算法均過早收斂且陷入局部最優(yōu)解。

圖16 20個任務箱算法收斂情況對比Fig.16 Comparison of algorithm convergence of 20 task containers

圖17 40個任務箱算法收斂情況對比Fig.17 Comparison of algorithm convergence of 40 task containers

4 AGV運行策略仿真分析

由于自動化集裝箱碼頭多層設備協(xié)同調度問題較為復雜，數(shù)學模型難以將因素考慮全面，因此本文在前述研究的基礎上利用plant-simulation 仿真軟件對提出的隨機路線、固定路線、分組隨機路線三種AGV運行策略進行了對比分析，進一步驗證文中所提算法的合理性及改善調度方式，找出能使算法發(fā)揮出最大效用的AGV運作策略。

4.1 隨機路線策略仿真

隨機路線策略中綜合考慮了全局情況，對AGV 進行作業(yè)面調度，能夠提高AGV 的利用率。本文模型及算法部分即采用了隨機路線策略，將隨機路線策略在仿真中實施后所得數(shù)據(jù)見表2及圖18。

表2 隨機路線仿真數(shù)據(jù)Table 2 Random route simulation data

圖18 隨機路線策略下完工時間Fig.18 Completion time under random route strategy

由表2 和圖18 可以看出，在不同規(guī)模實驗中，隨著AGV 數(shù)量的遞增，完工時間、場橋等待時間、門架小車等待時間、主小車等待時間均在AGV 數(shù)量為8 時達到最小值，而AGV 在場橋交接點處的停留時間卻逐步遞增；因此AGV配額為8時裝船效率最高，當AGV數(shù)量過大時會造成資源浪費。

4.2 固定路線策略仿真

為了進一步證明算法的合理性，利用仿真可以動態(tài)分析復雜問題的優(yōu)勢，在仿真場景中引入按固定路線行駛的AGV 運行策略，與算法中的隨機路線策略進行對比。固定路線行駛策略為AGV固定的服務于某一場區(qū)和岸橋，當場區(qū)和岸橋數(shù)量較多時，需至少擁有與場區(qū)或岸橋同等數(shù)量的AGV 才能作業(yè)，對固定路線進行分析后所得數(shù)據(jù)見表3及圖19。

表3 固定路線仿真數(shù)據(jù)Table 3 Fixed route simulation data

圖19 固定路線策略下完工時間Fig.19 Completion time under fixed route strategy

由表3 及圖19 可以看出，在固定路線行駛策略下，當AGV 數(shù)量為8 時，完工時間、場橋總等待時間、門架小車總等待時間、主小車總等待時間均達到最小值且不再隨著AGV 數(shù)量的遞增而改變，該結果進一步說明了該實驗場景下8 臺AGV 為最優(yōu)配額，此時的完工時間為相應規(guī)模任務的最優(yōu)完工時間；此外，當AGV數(shù)量達到8以后，場橋的等待時間為0，岸橋的等待時間也不再變化，說明在當前的設備效率及數(shù)量配置下已達到最優(yōu)效果，此時能夠影響完工時間的不再是AGV的數(shù)量，而是設備作業(yè)能力及場地大小等其他因素。在AGV數(shù)量為8 時，對AGV 速度進行靈敏度分析，結果見圖20，隨著AGV 速度的提升，最優(yōu)完工時間平滑下降固定路線策略雖能取得很好的效果，但該策略需要為每一臺岸橋和每一個場區(qū)提供專用的AGV，當場區(qū)和岸橋數(shù)量較多時，AGV數(shù)量也需增加，而對于任務箱所在箱區(qū)較分散的情況就需要足夠多的AGV 才能作業(yè)；如果任務箱數(shù)量少且分布不集中，則可能會造成AGV資源利用不充分，而隨機路線策略采用AGV 共享模式，可避免該問題。將隨機路線與固定路線完工時間進行對比，S表示隨機路線，G表示固定路線，結果見表4。

表4 隨機路線與固定路線數(shù)據(jù)對比Table 4 Comparison of random route and fixed route data

圖20 AGV速度靈敏度分析Fig.20 Sensitivity analysis of AGV speed

由表4可看出，隨機路線與固定路線在任務規(guī)模相同時，完工時間接近。表4中差額=（S完工時間-G完工時間）/S完工時間，20 個任務箱8 臺AGV 時，完工時間相同；40個任務箱8臺AGV時，完工時間差額為6.89%；因此按隨機路線進行計算的算法具有一定效果。

4.3 分組隨機路線策略仿真

隨機路線策略雖能對全局綜合考慮，但由于設備眾多會造成算法時間復雜度較高，算法求解耗時較長。為了能夠提高算法的適用性，提出了分組隨機路線的策略。

將隨機路線和分組隨機路線進行對比，結果見表5及圖21、22；其中完工差額=（隨機路線完工時間-分組隨機完工時間）/隨機路線完工時間，運行時間差額=（隨機路線運行時間-分組隨機路線運行時間）/隨機路線運行時間。

表5 隨機路線與分組隨機路線數(shù)據(jù)對比Table 5 Comparison of random route data and grouped random route data

圖21 20箱分組隨機路線與隨機路線運算時間對比Fig.21 Comparison of calculation time between grouped random route and random route of 20 task containers

圖22 40箱分組隨機路線與隨機路線運算時間對比Fig.22 Comparison of calculation time between grouped random route and random route of 40 task containers

由表5 可看出，兩種策略下完工時間最小差額為0.63%，最大差額為7.69%，差額較小。由圖21、22 可看出，同等任務規(guī)模下分組隨機能夠大大縮短算法計算時間，各規(guī)模算例下最低縮短運行時間33.21%，最高縮短運行時間59.24%。由于分組隨機中AGV的行駛范圍較小，且兩組AGV 互不干擾，因此AGV 之間的堵塞次數(shù)也有所減少，在8 組對比實驗中有5 組分組隨機策略阻塞次數(shù)小于隨機策略阻塞次數(shù)，有2 組阻塞次數(shù)相同，見圖23、24。

圖23 20箱分組隨機路線與隨機路線阻塞次數(shù)對比Fig.23 Comparison of blocking times between grouped random routes and random routes of 20 task containers

圖24 40箱分組隨機路線與隨機路線阻塞次數(shù)對比Fig.24 Comparison of blocking times between grouped random routes and random routes of 40 task containers

綜上，分組隨機策略在取得與隨機策略相近的完工時間的同時，還能大大減少算法運行時間并減少阻塞次數(shù)，提高了算法的適用性。

5 結論

本文重點研究了集裝箱由堆場到船上這一過程中多層設備的集成調度問題，所做工作及成果如下：

（1）詳細分析了自動化集裝箱碼頭中多層設備聯(lián)合吊運集裝箱時的各種規(guī)則。采用由整體到局部的思想，先在規(guī)則的基礎上以時空節(jié)點的方式構建了裝船任務時空流動圖，從集裝箱的視角出發(fā)，分析了集裝箱在整個裝船過程中被多層設備吊運的情況。又將多層設備進行拆分，從各層設備的視角出發(fā)，對每層設備在運行期間的完工時間計算邏輯進行了分析，將規(guī)則與所提出的模型聯(lián)系了起來。通過以上工作彌補了過往研究中對設備調度規(guī)則分析不夠深入的不足，即為本文中的模型及仿真提供了支撐，又為碼頭設備調度類問題的研究提供了一些參考。

（2）采用了數(shù)學模型與仿真相結合的思想。在設備調度規(guī)則的基礎上，建立了多層設備集成調度模型和仿真場景。數(shù)學模型用于調度方案的求取，仿真場景用于調度規(guī)則及調度方案的實施和分析，用仿真方法彌補了數(shù)學模型難以全面考慮復雜動態(tài)問題的劣勢。

（3）分別利用自適應遺傳算法、模擬退火算法和禁忌搜索算法進行了求解，并將各算法求得的調度方案放入仿真模型中進行驗證對比。結果表明所提出的自適應遺傳算法在執(zhí)行時間和求解結果方面均優(yōu)于其他兩種算法，證明了所提出的自適應遺傳算法在碼頭多層設備調度問題中的有效性。

（4）為了能夠進一步驗證算法的有效性及最大化算法的使用效果，提出了隨機路線、固定路線、分組隨機路線三種AGV 運行策略。在仿真場景中，對三種策略下的各設備等待時間、AGV 最優(yōu)配額、完工時間、AGV 阻塞次數(shù)、算法運行時間進行了對比和分析，結果表明在文中實驗場景下AGV 配額為8 臺時，完工時間和各設備等待時間均最短，當AGV配額大于8臺時，會造成資源的浪費。同時也證明了所提出的自適應遺傳算法與分組隨機路線策略結合既能保證完工時間較優(yōu)又能減少AGV 阻塞次數(shù)，還將算法運行時間縮短了33.21%至59.24%。

本文的不足之處在于：所提出算法的性能仍有很大的提升空間；只研究了裝船過程中的多層設備集成調度問題。未來將嘗試采用混合算法或尋找求解速度快且精度高的其他算法去求解裝卸同步進行的多層設備集成調度問題。