王盼龍，梁承姬，王 鈺

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 問題描述

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

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

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

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

1.2 基于多層設(shè)備運(yùn)作規(guī)則的時(shí)空流動(dòng)圖

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

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

1.3 裝船任務(wù)完工時(shí)間計(jì)算

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

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

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

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

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

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

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

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

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

1.4 AGV運(yùn)作策略

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

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

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

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

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

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

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

1.5 仿真場(chǎng)景

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

圖10 仿真場(chǎng)景Fig.10 Simulation scene

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

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

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

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

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

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

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

（4）模型中AGV被所有的岸橋和場(chǎng)橋共享；

（5）AGV在任意兩個(gè)節(jié)點(diǎn)間的運(yùn)行時(shí)間已知；

（6）場(chǎng)橋、岸橋門架小車、岸橋主小車處理每個(gè)集裝箱所需時(shí)間已知。

2.1 模型假設(shè)

（1）場(chǎng)橋、岸橋主小車、岸橋門架小車、AGV分別一次只能處理一個(gè)集裝箱；

（2）不考慮翻箱問題；

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

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

（5）雙小車岸橋中轉(zhuǎn)平臺(tái)可容納兩個(gè)40英尺集裝箱。

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

2.2.1 模型參數(shù)

K：場(chǎng)橋集合，編號(hào)為{1…k}，k∈K；

V：AGV集合，編號(hào)為{1…v}，v∈V；

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

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

L：所有任務(wù)的集合，編號(hào)為{1…i}，i∈L；

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

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

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

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

2.2.2 決策變量

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

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

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

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

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

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

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

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

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

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

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

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

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

3 模型求解

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

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

算法步驟如下：

步驟1隨機(jī)生成初始種群P。

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

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

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

步驟5對(duì)種群P1 進(jìn)行變異操作產(chǎn)生種群P2，計(jì)算種群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)秀個(gè)體進(jìn)行了重插入操作，得到了子代種群。

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

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

（1）染色體編碼

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

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

（2）種群初始化

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖14 均勻交叉Fig.14 Uniform crossover

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

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

3.2 結(jié)果分析

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

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

圖15 AGA、TS和SA完工時(shí)間對(duì)比Fig.15 Comparison of completion time of AGA，TS and SA

從實(shí)驗(yàn)結(jié)果可以看出：

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

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

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

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

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

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

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

4 AGV運(yùn)行策略仿真分析

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

4.1 隨機(jī)路線策略仿真

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

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

圖18 隨機(jī)路線策略下完工時(shí)間Fig.18 Completion time under random route strategy

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

4.2 固定路線策略仿真

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

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

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

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

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

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

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

4.3 分組隨機(jī)路線策略仿真

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

將隨機(jī)路線和分組隨機(jī)路線進(jìn)行對(duì)比，結(jié)果見表5及圖21、22；其中完工差額=（隨機(jī)路線完工時(shí)間-分組隨機(jī)完工時(shí)間）/隨機(jī)路線完工時(shí)間，運(yùn)行時(shí)間差額=（隨機(jī)路線運(yùn)行時(shí)間-分組隨機(jī)路線運(yùn)行時(shí)間）/隨機(jī)路線運(yùn)行時(shí)間。

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

圖21 20箱分組隨機(jī)路線與隨機(jī)路線運(yùn)算時(shí)間對(duì)比Fig.21 Comparison of calculation time between grouped random route and random route of 20 task containers

圖22 40箱分組隨機(jī)路線與隨機(jī)路線運(yùn)算時(shí)間對(duì)比Fig.22 Comparison of calculation time between grouped random route and random route of 40 task containers

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

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

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

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

5 結(jié)論

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

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

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

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

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

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