基于SP-AS/RS與ASC的自動化碼頭協(xié)同調(diào)度研究

孟慶堯，朱 瑾

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

0 引言

在船舶大型化、集裝箱碼頭規(guī)模不斷擴張的背景下，提高集裝箱的周轉(zhuǎn)效率，降低船舶的停泊時間等已成為自動化碼頭關(guān)注的主要問題，研究高效率的裝卸作業(yè)系統(tǒng)協(xié)同調(diào)度是提高碼頭整體運作效率的重要途徑。

現(xiàn)有的大多數(shù)自動化堆場中，集裝箱采用堆疊方式儲存在堆場，因此在進行調(diào)度操作時不可避免的會產(chǎn)生翻箱操作，李隋凱[1]等提出了一種兩倍狀態(tài)多階段動態(tài)規(guī)劃算法來減少翻箱數(shù)量。魏亞茹[2]等通過同時考慮集裝箱的存儲位置優(yōu)選和翻箱問題，以最小完工時間為目標(biāo)建立混合整數(shù)規(guī)劃模型，設(shè)計遺傳算法與蟻群融合算法求解，討論了接力模式與混合模式下的效率問題。王祥雪[3]等根據(jù)多智能體系統(tǒng)的方法，將碼頭中的裝卸設(shè)備抽象為具有一系列屬性和方法的智能體，將船舶、堆場、任務(wù)管理、設(shè)備管理等視為智能體并且構(gòu)建出自動化碼頭協(xié)同作業(yè)系統(tǒng)模型。仲美穌[4]等根據(jù)自動化碼頭中邊裝邊卸的工作模式，通過群智能算法求解自動化碼頭自動引導(dǎo)車、岸橋和自動化軌道吊的協(xié)同調(diào)度問題。在集裝箱堆場中，歐洲一些港口率先使用具有水平與豎直移動設(shè)備組成的立體存儲裝置SP-AS/RS進行集裝箱的存放，這種裝置不僅解決了堆疊式堆場中在進行作業(yè)時需要進行的翻箱操作，并且在堆存集裝箱高度上也有了提升，提高了堆場的集裝箱存儲容量。Ya-Hong Hu[5,6]等提出了一種新的存儲/檢索機制（AS/RS），并提出了停留點策略下的連續(xù)旅行時間模型，給出了新的AS/RS機構(gòu)的矩形實時AS/RS機架的優(yōu)化設(shè)計準則，緩解了集裝箱的無序問題和AS/RS設(shè)備上水平移動與垂直移動的設(shè)備的擁堵問題。S.M.Homayouni[7,8]等根據(jù)岸橋，自動導(dǎo)引車（Automated Guided Vehicle，AGV）和一種新型的裝箱自動碼頭裝卸設(shè)備，建立了集裝箱自動碼頭裝卸設(shè)備一體化調(diào)度的混合整數(shù)規(guī)劃模型，并使用模擬退火算法SAA與遺傳算法GA，在較低的計算時間內(nèi)找到問題的近似最優(yōu)解。

在自動化碼頭中，自動導(dǎo)引車AGV、具有舉升集裝箱功能且需要輔助設(shè)備完成裝卸箱的ALV（automated lifting vehicles）、具有自主裝卸箱而不需要其他設(shè)備輔助的ASC是目前自動化碼頭主要使用的三種水平運輸車，在對集裝箱進行水平運輸時，AGV運行至QC處需要額外的輔助設(shè)備才能對集裝箱進行裝卸操作，這會造成額外的延時等待，而ASC具有自動裝卸集裝箱的功能，不僅解決了與QC的耦合問題，同樣也解決了與SP-AS/RS交接處的耦合問題，能夠提高各個設(shè)備之間交接集裝箱的作業(yè)效率。Xiaoming Yang[9]等提出了一種基于軌道穿梭機的自動化碼頭。該研究采用了兩種運輸工具，即跨運車和升降式AGV。通過仿真表明，SC在基于軌道的自動化碼頭中優(yōu)于升降式AGV，特別是在卸貨操作上。而有關(guān)于ASC的研究，目前大多學(xué)者主要針對ASC的路徑規(guī)劃問題進行研究，Cai B[10,11]等人通過建立帶時間窗的優(yōu)化模型，將ASC的路徑規(guī)劃問題視為一個二進制規(guī)劃，再通過分支界定的方法對模型進行求解。

在自動化碼頭中，設(shè)備間的協(xié)同調(diào)度即為堆場設(shè)備，水平運輸車，岸橋兩種或多種設(shè)備同時考慮進行集裝箱的裝卸作業(yè)流程，實現(xiàn)各個設(shè)備之間的有效且合理的調(diào)度，能夠提高碼頭作業(yè)效率，丁一[12]等根據(jù)雙小車岸橋與AGV協(xié)同的方式研究自動化碼頭調(diào)度問題，并且結(jié)合AGV空載與行駛成本和岸橋作業(yè)延誤成本建立混合整數(shù)規(guī)劃模型。湯鵬飛[13]等將ALV總行駛時間與QC等待ALV的時間和最小為目標(biāo)，建立數(shù)學(xué)模型，并通過遺傳算法對模型求解，且給出了在有緩存區(qū)情況下的合理調(diào)度方案。梁承姬[14]等建立了帶有緩存區(qū)設(shè)置的集裝箱碼頭AGV和堆場場橋的聯(lián)合調(diào)度模型，并采用遺傳算法對建立的模型進行求解，再針對不同的緩存區(qū)容量的設(shè)置進行調(diào)度方案完工時間的結(jié)果進行比較。王秋芬[15]通過分析流水作業(yè)調(diào)度問題最優(yōu)解的結(jié)構(gòu)特征,建立了遞歸關(guān)系式，并且總結(jié)了最優(yōu)調(diào)度具有的特點,設(shè)計了兩種算法解決該調(diào)度問題。

綜上分析，現(xiàn)有裝卸工藝多為AGV與傳統(tǒng)堆場或與SP-AS/RS的協(xié)同調(diào)度問題，本文結(jié)合ASC在裝卸集裝箱時能夠自舉升裝卸，在完成上一集裝箱裝卸任務(wù)后能夠直接進行下一任務(wù)，從而減少了等待延時的特點與SP-AS/RS減少翻箱率與增加存儲容量的特點，考慮ASC與SP-AS/RS的最小工作時間與QC最小延時等待時間，以SP-AS/RS、ASC等關(guān)鍵設(shè)備在同裝同卸條件下的時間窗約束建立混合整數(shù)規(guī)劃（mixed integer programming，MIP）模型，目的在于探討AGV、ASC兩種無人運輸車分別與SP-AS/RS結(jié)合對集裝箱裝卸效率的影響問題。

1 問題描述

自動化碼頭集裝箱裝卸流程主要分為QC的裝卸作業(yè)，運輸車對集裝箱的運輸以及堆場設(shè)備的集裝箱存取作業(yè)，因為在進行裝卸作業(yè)時各個設(shè)備同時工作，之間銜接時可能會產(chǎn)生延時等待，進而影響自動化碼頭的工作效率，延長貨船的靠泊時間。如圖1所示，自動化碼頭集裝箱的裝船操作是將需要裝船的目標(biāo)箱從SP-AS/RS系統(tǒng)中運送至緩存區(qū)等待指定的ASC拾取，當(dāng)ASC拾取后運輸至指定的QC等待裝船，卸船操作即為裝船操作的反過程。在ASC運輸集裝箱使呈逆時針方向運行，可減少ASC之間的擁堵與碰撞問題，并且為了提高運輸效率，允許ASC在堆場處向岸橋穿梭運行。

圖1 采用ASC與SP-AS/RS碼頭布局圖

對于SP-AS/RS系統(tǒng)，根據(jù)文獻[7]作者描述的結(jié)構(gòu)如圖2所示，SP-AS/RS系統(tǒng)由兩臺分體式機架組成，兩臺機架間每一層都有一臺能夠水平移動的裝置HP，在每個機架的一端都有一臺能夠豎直移動的裝置VP，能夠?qū)崿F(xiàn)對目標(biāo)箱的直接訪問，當(dāng)進行裝船任務(wù)時，目標(biāo)箱所在層的HP首先將目標(biāo)箱取出，移動至機架一端H/O站處，同時VP也移動至同一位置完成集裝箱的交接，最終運送至I/O站，等待ASC拾取集裝箱運往下一個地點，卸船任務(wù)即為裝船任務(wù)的反順序，目標(biāo)箱最終儲存在SP-AS/RS系統(tǒng)中。

圖2 SP-AS/RS結(jié)構(gòu)圖

2 數(shù)學(xué)模型

在自動化碼頭裝卸作業(yè)中，每個設(shè)備都需要完成裝箱任務(wù)與卸箱任務(wù)，并且每個任務(wù)都可以分為兩部分，第一部分為設(shè)備從當(dāng)前所在的位置移動到任務(wù)起點位置，第二部分為設(shè)備從任務(wù)起點位置移動到任務(wù)終點位置。因此，一個完整裝箱任務(wù)首先由SP-AS/RS設(shè)備中的HP進行取箱，并運行至H/O站，VP從H/O站將目標(biāo)箱運行至I/O站等待ASC取箱，ASC取箱后運行至QC，最終由QC將目標(biāo)箱裝船，卸箱操作即為裝箱操作的反順序，目標(biāo)箱由QC從船上卸下，交付給ASC后運送至SPAS/RS系統(tǒng)最終存放至指定位置。

2.1 模型假設(shè)

對于自動化碼頭的集裝箱任務(wù)量通常是已知的，并且根據(jù)集裝箱的堆存位置可以得到SP-AS/RS設(shè)備中相應(yīng)VP與HP的運行時間以及ASC的選擇與路程確定，綜上對進行的研究進行假設(shè)：

1）每個任務(wù)的起點和終點已知，并且每個SP-AS/RS機架的緩存區(qū)存放集裝箱最大容量為2。

2）每個裝載任務(wù)中目標(biāo)存儲單元存在集裝箱；每個卸載任務(wù)中目標(biāo)存儲單元為空。

3）對于QC，ASC，HP與VP，空載或負載時運輸時間不變。

4）不考慮ASC之間的擁堵問題。

5）所有設(shè)備在完成每個任務(wù)后都遵循停在原位的停留策略，即不再回到任務(wù)的起點位置，任務(wù)結(jié)束即在原位停止，等待下一任務(wù)。

6）每兩臺機架間的各個HP在進行裝卸集裝箱時互不影響。

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

在模型中，QC的集合用K表示，ASC起點與終點的集合分別用S、F表示，ki表示上一個任務(wù)第k個QC的第i個任務(wù)，lj表示當(dāng)前任務(wù)第l個QC的第j個任務(wù)，Qk表示第k個QC的總?cè)蝿?wù)數(shù)，HP與VP起點與終點的集合分別用V、W表示，mp表示第m個機架的當(dāng)前任務(wù)，mn表示第m個機架的上一個任務(wù)，Nm表示第m個機架的總?cè)蝿?wù)數(shù)，其中決策變量為：

2.3 模型建立

目標(biāo)函數(shù)：

目標(biāo)函數(shù)(1)表示最小化所有ASC工作總時間、QC工作總延遲與SP-AS/RS的工作總時間之和，TA為ASC完成任務(wù)時起點到取箱處的時間，其中Taw表示運輸過程與裝卸箱的工作時間，Taf表示空閑時間，即等待延時，TB為ASC從任務(wù)起點到完成任務(wù)終點的時間，Tbw，Tbf分別與Taw，Taf對應(yīng)，如式(12)，式(13)所示，TQC表示所有QC完成任務(wù)的實際總時間，ES表示QC預(yù)計完成時間，TSR表示SP-AS/RS的工作總時間。

約束(2)與約束(3)表示連續(xù)執(zhí)行QC的任務(wù)只能由同一個ASC完成并且每次只完成一個任務(wù)。約束(4)與約束(5)分別表示同一SP-AS/RS系統(tǒng)的貨架中，一個任務(wù)的完成只需要一組VP與HP。約束(6)表示每臺QC工作時間的計算方式，根據(jù)裝卸（分別用L和U表示）操作的不同A的值根據(jù)下表對應(yīng)不同的公式代入，M是一個相對大的正數(shù)，當(dāng)為1時公式被激活。約束(7)表示每架SP-AS/RS工作時間的計算方式，同樣根據(jù)裝卸操作的不同B的值代入不同公式。約束(8)表示任一任務(wù)的完成時間都應(yīng)大于等于最早可能完成的時間，約束(9)表示每個QC后續(xù)完成任務(wù)的時間都應(yīng)大于上一任務(wù)完成的時間。約束(10)與約束(11)表示Ω與θ為二進制數(shù)，只能取0或1作為決策變量使用。

表1表示QC任務(wù)完成所用時間計算法則，中Tlj表示當(dāng)前QC任務(wù)類型，Tl(j-1)表示當(dāng)前任務(wù)設(shè)備的上一任務(wù)類型，Tki表示完成當(dāng)前任務(wù)的ASC所完成的上一任務(wù)類型。

表1 約束(6)中A的取值規(guī)則

表2表示SP-AS/RS任務(wù)完成所用時間計算法則，其中Omn表示上一SP-AS/RS任務(wù)類型，Omp表示當(dāng)前任務(wù)類型，TQ與OQ表示QC中集裝箱在岸邊與船之間的運輸時間和在岸邊將集裝箱放置到地面上的運行時間。與分別表示VP、HP從上一任務(wù)停留點到下一任務(wù)起始點所用時間，分別表示VP、HP從當(dāng)前任務(wù)其實到移動到任務(wù)完成點所用時間，THPa與TVPa分別表示VP、HP到下一任務(wù)起點時的時間點，THPb與TVPb分別表示VP、HP到下一任務(wù)終點的時間點。

表2 約束(7)中B的取值規(guī)則

3 改進的遺傳算法IGA

3.1 染色體編碼

在一般的問題中，算法的適應(yīng)度函數(shù)由問題的目標(biāo)函數(shù)轉(zhuǎn)化而來，并且自動化碼頭集裝箱集成調(diào)度問題中起到主要影響因素的是集裝箱任務(wù)順序的優(yōu)先級，因此在本算法中染色體的編碼方式根據(jù)文獻[7]中提到的方式，N為集裝箱碼頭總裝卸任務(wù)數(shù)，每個任務(wù)根據(jù)QC的編號（1到K）以及每個QC的任務(wù)順序編號（1到Qk）進行分類，如下圖所示，Tki即表示第k架QC的第i個任務(wù)，而Omn是第m架SP-AS/RS中的第n個任務(wù)，兩者共同組成染色體中的一個事件，如圖中的“6”表示第2個QC的第1個任務(wù)，以及第5架SP-AS/RS中的第2個任務(wù)開始執(zhí)行，它在“5”事件開始后與“7”事件開始前進行。將ASC在QC與SP-AS/RS之間進行分配，并根據(jù)集裝箱任務(wù)序列決定每臺ASC的作業(yè)序列，AGV的作業(yè)序列確定后，計算每一個岸橋的開始裝卸時間和作業(yè)完工時間。其中集裝箱任務(wù)序列在染色體編碼中得到解決，有關(guān)時間的計算將在適應(yīng)度函數(shù)中考慮。將各個任務(wù)根據(jù)計劃開始時間進行優(yōu)先級的編號，任務(wù)的優(yōu)先級按照集裝箱任務(wù)計劃開始時間進行排序，任務(wù)的優(yōu)先級編號越小，任務(wù)的優(yōu)先級越大。

3.2 適應(yīng)度函數(shù)

在初始種群形成時，隨機產(chǎn)生三個染色體，并計算它們的適應(yīng)度，適應(yīng)度函數(shù)即為模型的目標(biāo)函數(shù)，適應(yīng)度最高的個體作為親代，通過重復(fù)這一操作直至產(chǎn)生所有親代。模型中約束條件(2)～(5)可以避免產(chǎn)生不可行解。在選擇過程，本文采用錦標(biāo)賽的選擇方式進行染色體的選擇。

3.3 交叉

在交叉算子中，隨機選擇一臺QC，并且將這臺QC標(biāo)記在兩個親代染色體中，并將第一個親代染色體中該QC任務(wù)位置復(fù)制到子代2的相應(yīng)位置，將第二個親代中該QC任務(wù)位置復(fù)制到子代1的相應(yīng)位置，子代1其余的位置同時滿足優(yōu)先級與親代2順序進行填充，子代2以相同方式進行填充，假設(shè)選擇第三臺QC進行交叉操作（如圖3所示），那么過程如圖4所示。

圖3 染色體編碼

圖4 交叉操作

3.4 變異

在變異算子中，將同一染色體上隨機的兩個基因位置互換，由于優(yōu)先級的影響，因此互換后符合優(yōu)先級的染色體才能被執(zhí)行，如果不符合優(yōu)先級，則對該染色體進行修正，使之按照優(yōu)先級生成變異染色體。變異操作保證了搜索空間的多樣性，使各種染色體序列都能被搜索到，并且盡可能避免解空間過于大時產(chǎn)生的過早收斂（收斂到局部最優(yōu)）的情況。

考慮到避免最優(yōu)解在迭代過程中被篩選掉的可能，每次迭代時均保留當(dāng)前種群中適應(yīng)度值最高的三條染色體進入下一代，這個操作能夠保證IGA不會得到比上次迭代更差的解，能夠在有限次的迭代后得到集成調(diào)度問題中的近似最優(yōu)解。

4 仿真實驗與分析

4.1 參數(shù)設(shè)置

進行仿真的計算機環(huán)境在Windows 7，Core i5-4200M CPU 2.50GHz，和MATLAB R2014a下進行，仿真中根據(jù)文獻[16]中提到的碼頭布局及相關(guān)參數(shù)進行仿真，QC進行裝卸箱升降操作的時間OQ為20秒，將集裝箱在岸邊與船之間的移動時間TQ定為10秒，在SP-AS/RS系統(tǒng)中，HP的移動速度為2米每秒，VP的移動速度為1米每秒，每個存儲單元寬和高定義為3米，每個SPAS/RS的貨架都為10排12列，即儲存架的高度為30米和寬度為36米，IGA的種群數(shù)量為50，迭代次數(shù)為 2000，并且在所有仿真中集裝箱任務(wù)數(shù)量、QC數(shù)量、SP-AS/RS數(shù)量、AGV/ASC數(shù)量，分別用T、Q、L、A表示。表3為ASC在各個QC與每個SP-AS/RS之間的行駛時間。QC為岸橋，SP為堆場自動裝卸系統(tǒng)。

表3 ASC在各個岸橋及堆場間的空載行駛時間

4.2 實驗結(jié)果與分析

實驗1：驗證IGA的有效性

1）在表4中，隨著任務(wù)數(shù)量的增加，任務(wù)序列的數(shù)量呈指數(shù)上升，在規(guī)模1～3中，搜索算法（遍歷所有解）在結(jié)果與CPU運行時間上均好于IGA與SAA，但在規(guī)模4中，任務(wù)量為12時，由于搜索算法的運算復(fù)雜度較高，使用搜索算法在有效時間內(nèi)已無法找到最優(yōu)解，在表4中用“*”表示。雖然在規(guī)模1～3中搜索算法有較好的表現(xiàn)，但由于在實際自動化碼頭生產(chǎn)中，集裝箱任務(wù)量遠大于表4中給出的規(guī)模，因此搜索算法已不適合在更大的規(guī)模中被使用。

表4 使用搜索算法（遍歷）與IGA、SAA在不同規(guī)模情況下結(jié)果對比

2）與搜索算法相比，IGA與SAA均在合理的時間內(nèi)求得近似最優(yōu)解，且IGA與SAA平均最優(yōu)差異分別為6.1%和10.5%，因此在小規(guī)模中IGA求得解的質(zhì)量要優(yōu)于SAA解的質(zhì)量。（GAP=（Obj1-Obj2）/Obj1）

3）在同一規(guī)模的實驗中，IGA的求解時間要比SAA求解時間長，這是因為IGA的每一次迭代運算都需要生成50組個體進行求解計算，相對于SAA來說加大了運算量，但IGA在消耗了更多時間的基礎(chǔ)上得到了較好的運算結(jié)果，相對于SAA提升了41.9%。

實驗2：在不同的規(guī)模下比較ASC與SP-AS/RS的組合和AGV與SP-AS/RS組合兩種裝卸流程下對自動化碼頭集裝箱裝卸效率的影響。

1）由表5可知，77%以上的最優(yōu)值集中在交叉率為0.5以上與變異率0.5以下的組合中。因此在本模型中選擇以上組合更適合近似最優(yōu)解的搜索。

表5 在GA算法中使用AGV與ASC在不同規(guī)模情況下結(jié)果對比

2）在規(guī)模1和規(guī)模2中，使用AGV所得到的近似最優(yōu)解優(yōu)于使用ASC得到的近似最優(yōu)解，差異值為-0.85%，-1.73%，但從規(guī)模3開始，隨著規(guī)模中T、Q、L、A數(shù)量的增多，使用ASC得到的近似最優(yōu)解均優(yōu)于使用AGV得到的近似最優(yōu)解，這是由于ASC在與SPAS/RS和QC耦合時，能夠自主的裝卸集裝箱，不需要其他設(shè)備的輔助，而AGV在交換區(qū)裝卸集裝箱時則需要其他設(shè)備進行裝卸輔助，造成了額外的等待延時，在裝卸集裝箱的操作中，ASC自主裝卸的時間也要小于QC輔助裝卸的時間，而且在集裝箱被取走或裝載完成后AGV才能進行下一項任務(wù)，ASC在自主放置集裝箱后即可進行下一任務(wù)，因此在規(guī)模3～規(guī)模11中選擇ASC進行裝卸箱操作的表現(xiàn)優(yōu)于使用AGV。

在結(jié)論2）中，分別在使用AGV時取得最優(yōu)解與使用ASC時取得最優(yōu)解中GAP值最大的一組規(guī)模生成調(diào)度甘特圖進行比較，圖5～圖8分別為集裝箱任務(wù)數(shù)量規(guī)模2與規(guī)模5在使用AGV與ASC時調(diào)度甘特圖，在規(guī)模2中，使用AGV時目標(biāo)函數(shù)解較小，而規(guī)模7在使用ASC的目標(biāo)函數(shù)解則小于使用AGV時的解，圖中“1”表示QC工作時間，“2”表示ASC或AGV工作時間，“3”表示SP-AS/RS工作時間。

圖5 規(guī)模2且交叉率與變異率為0.3和0.7情況下使用AGV的碼頭調(diào)度甘特圖

圖6 規(guī)模2且交叉率與變異率為0.6和0.4情況下使用ASC的碼頭調(diào)度甘特圖

圖7 規(guī)模5且交叉率與變異率為0.7和0.3情況下使用AGV的碼頭調(diào)度甘特圖

圖8 規(guī)模5且交叉率與變異率為0.8和0.2情況下使用ASC的碼頭調(diào)度甘特圖

5 結(jié)語

本文根據(jù)ASC自主裝卸集裝箱與SP-AS/RS減少翻箱率與增加存儲容量的特點，考慮ASC與SP-AS/RS在同裝同卸的時間窗為約束，建立以ASC與SP-AS/RS的最小工作時間、QC最小延時等待時間為目標(biāo)的MIP模型。改進IGA對模型進行求解，并采用搜索算法與SAA在集裝箱任務(wù)量為8～12的情況下與IGA求得的解的質(zhì)量與求解速度進行對比，結(jié)果表明IGA在合理時間的內(nèi)得到了較好的運算結(jié)果，相對于SAA提升了41.9%；在不同的規(guī)模下比較了ASC+SP-AS/RS、AGV+SP-AS/RS的組合兩種裝卸流程下解的質(zhì)量，當(dāng)任務(wù)量在10至20之間時，AGV+SP-AS/RS的組合裝卸效率相對于ASC+SP-AS/RS的裝卸效率平均提升了1.29%，當(dāng)任務(wù)量在20至112之間時，ASC+SP-AS/RS的組合裝卸效率均好于AGV+SPAS/RS裝卸效率，效率平均提升了4.46%，實驗結(jié)果表明，在中、大規(guī)模中，使用ASC進行集裝箱的裝卸有利于自動化碼頭效率的提升。

在今后的工作中可以考慮比較ASC與AGV在QC或SP-AS/RS處裝卸箱傳遞時的時間差異對裝卸效率的影響問題，并且還可從SP-AS/RS不同工作模式下討論對自動化碼頭效率的影響。