王盼龍，梁承姬，王 鈺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 問題描述

1.1 自動化集裝箱碼頭多層設(shè)備協(xié)調(diào)

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

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

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

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

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

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

1.3 裝船任務(wù)完工時間計算

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

場橋作為第一層設(shè)備，其吊運一個任務(wù)箱的時間計算邏輯見圖3。在場橋到堆場中進(jìn)行提箱時，需要判斷場橋在做該任務(wù)箱之前是否還做了其他任務(wù)。若做了其他任務(wù)，則場橋開始抓該任務(wù)箱的時間即為場橋做完上一個任務(wù)箱后來到本次任務(wù)箱位置的時間，該任務(wù)箱到達(dá)場橋與AGV交接點的時間點為場橋抓完上一個箱后來到本次任務(wù)箱位置的時間點加上場橋?qū)⑾渥訌亩褕鎏崞鹬翆⑾渥臃诺紸GV上的時間。若場橋做該任務(wù)箱之前沒做其他任務(wù)，則該任務(wù)箱為這臺場橋作業(yè)的第一個任務(wù)，場橋開始抓本次任務(wù)箱的時間記為0，該任務(wù)箱到達(dá)場橋與AGV交接點的時間為場橋?qū)⑾渥訌亩褕鎏崞鹬翆⑾渥臃诺紸GV上的時刻。

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

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

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

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

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

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

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

1.4 AGV運作策略

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

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

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

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

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

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

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

1.5 仿真場景

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

圖10 仿真場景Fig.10 Simulation scene

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

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

2 數(shù)學(xué)模型構(gòu)建

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

（1）任務(wù)箱的堆存位置已知；

（2）場橋?qū)⑷蝿?wù)箱由堆存位置送到固定交接點所需的時間已知；

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

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

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

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

2.1 模型假設(shè)

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

（2）不考慮翻箱問題；

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

（4）任務(wù)箱均為40英尺；

（5）雙小車岸橋中轉(zhuǎn)平臺可容納兩個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：所有任務(wù)的集合，編號為{1…i}，i∈L；

O：虛擬起始任務(wù)；

θ：虛擬終止任務(wù)；

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

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

2.2.2 決策變量

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

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

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

關(guān)于場橋的約束：

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

關(guān)于AGV的約束：

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

關(guān)于岸橋門架小車的約束：

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

關(guān)于岸橋主小車的約束：

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

關(guān)于岸橋中轉(zhuǎn)平臺的約束：

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

3 模型求解

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

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

算法步驟如下：

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

步驟2對種群P進(jìn)行個體評價，計算適應(yīng)度。

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

步驟4交叉后產(chǎn)生種群P1，計算種群P1 的適應(yīng)度標(biāo)準(zhǔn)差。

步驟5對種群P1 進(jìn)行變異操作產(chǎn)生種群P2，計算種群P2 的適應(yīng)度標(biāo)準(zhǔn)差。

步驟6比較種群P1 和種群P2 的適應(yīng)度標(biāo)準(zhǔn)差，若P2 適應(yīng)度標(biāo)準(zhǔn)差小于P1，說明P2 的種群多樣性較差，則將變異率pm增加0.01；否則，保持變異率不變。

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

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

3.1 自適應(yīng)遺傳算法

（1）染色體編碼

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

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

（2）種群初始化

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

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

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

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

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

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

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

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

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

（4）適應(yīng)度計算

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

其中，T為一個調(diào)度方案的完工時間。

（5）選擇算子的設(shè)計

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

（6）交叉算子設(shè)計

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

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

圖14 均勻交叉Fig.14 Uniform crossover

（7）變異算子設(shè)計

本文對變異前后父代和子代種群適應(yīng)度的標(biāo)準(zhǔn)差進(jìn)行比較，若子代小于父代，則將變異率增加0.01；若子代大于或等于父代，則保持變異率不變。

3.2 結(jié)果分析

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

表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

從實驗結(jié)果可以看出：

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

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

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

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

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

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

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

4 AGV運行策略仿真分析

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

4.1 隨機路線策略仿真

隨機路線策略中綜合考慮了全局情況，對AGV 進(jìn)行作業(yè)面調(diào)度，能夠提高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 時達(dá)到最小值，而AGV 在場橋交接點處的停留時間卻逐步遞增；因此AGV配額為8時裝船效率最高，當(dāng)AGV數(shù)量過大時會造成資源浪費。

4.2 固定路線策略仿真

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

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

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

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

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

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

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

4.3 分組隨機路線策略仿真

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

將隨機路線和分組隨機路線進(jìn)行對比，結(jié)果見表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 可看出，同等任務(wù)規(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 結(jié)論

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

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

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

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

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

本文的不足之處在于：所提出算法的性能仍有很大的提升空間；只研究了裝船過程中的多層設(shè)備集成調(diào)度問題。未來將嘗試采用混合算法或?qū)ふ仪蠼馑俣瓤烨揖雀叩钠渌惴ㄈデ蠼庋b卸同步進(jìn)行的多層設(shè)備集成調(diào)度問題。