柴佳祺 張清波 邊志成

上海振華重工（集團）股份有限公司 上海 200125

0 引言

近年來，勞動力成本逐年攀高，隨著集裝箱碼頭整體裝備設(shè)計制造水平的不斷提升以及新工藝新技術(shù)的不斷完善，國內(nèi)外自動化集裝箱碼頭（Automated Container Terminal，ACT）已掀起新一波建設(shè)熱潮。然而，自動化集裝箱碼頭生產(chǎn)組織的信息化、智能化等軟實力的發(fā)展必須與裝備制造等硬實力的發(fā)展相適應(yīng)，二者缺一不可。因此，國內(nèi)自動化碼頭生產(chǎn)作業(yè)管理相關(guān)理論與方法正面臨著迫切需求，關(guān)于自動化碼頭智能計劃及動態(tài)調(diào)度等一系列智能協(xié)同作業(yè)成套問題已成為該領(lǐng)域研究的核心與熱點。本文所研究的自動化集裝箱碼頭卸船箱動態(tài)選位問題正是ACT智能協(xié)同作業(yè)成套問題中的重要研究方向之一。

自20世紀(jì)70年代以來，越來越多的業(yè)界學(xué)者和專家針對箱區(qū)選位問題從不同角度進行分析，運用各種方法解決實際問題。Bazzazi M等[1]建議使用有效的遺傳算法（GA）來解決擴展儲存空間分配問題（SSAP），該問題考慮了集裝箱碼頭現(xiàn)存的大量等式約束；Yu M等[2]在不同策略下的進站集裝箱的存儲空間分別設(shè)計了最優(yōu)艙位分配模型，從而縮短跨運車等待時間。謝塵等[3]采用分布式遺傳算法和啟發(fā)式算法相結(jié)合的混合算法求解選位模型，提出基于混堆模式的出口箱進場選位優(yōu)化策略，從而降低了船舶壓箱總數(shù)和在港時間；Zhang C等[4]采用滾動時域的方法，對每個計劃周期，縮短集裝箱從堆存區(qū)到船停泊位置的運輸距離，減少了工作量的不平衡，避免了站點可能出現(xiàn)的障礙；王志明等[5]以實例利用遺傳算法求解到場箱的分配箱位，研究了集裝箱后方堆場堆存策略，實現(xiàn)了對一次卸船或進港的一批箱子進行集裝箱堆場作業(yè)的全局優(yōu)化；Kim K H等[6]討論了動態(tài)分配方法，建立混合整數(shù)規(guī)劃模型，基于集裝箱在港停留時間和梯度下降優(yōu)化，分別提出2個啟發(fā)式算法，使堆場具有較高的裝船作業(yè)效率和空間利用率；Kang J等[7]對箱重信息不確定條件下的進口箱箱位分配問題進行研究，整個優(yōu)化過程運用模擬退火算法和仿真技術(shù)相結(jié)合的手段；Kim K H等[8]利用動態(tài)規(guī)劃模型多階段逆向求解的特征，建立基于動態(tài)規(guī)劃的進口箱箱位分配模型；楊淑芹等[9]根據(jù)進口集裝箱先到港以及盡量輕箱在下、重箱在上的原則，采用啟發(fā)式方法合理安排進口集裝箱堆場箱位，以達到裝船作業(yè)時堆場機械的翻箱率最低。

1 問題描述

卸船箱動態(tài)選位問題屬于自動化集裝箱碼頭的資源分配問題，選位算法的方法和原則與卸船箱堆存計劃有關(guān)。常用的卸船堆存計劃模式可分為一對一計劃和模糊計劃2種，隨著碼頭吞吐量和運營水平的不斷變化，這2種計劃實用性漸弱。為此，需要通過實時的自動選位和任務(wù)捕捉來增加箱位分配的靈活性、實時性和有效性，即需要智能選位算法來支撐堆場動態(tài)選位模式。

卸船進場選位算法由集裝箱碼頭營運系統(tǒng)數(shù)據(jù)庫服務(wù)器來執(zhí)行，其功能是動態(tài)監(jiān)測場地內(nèi)任務(wù)中已被卸船落箱在水平運輸設(shè)備上但尚未分配具體場地位置的卸船落位任務(wù)，一旦發(fā)現(xiàn)目標(biāo)便根據(jù)相關(guān)數(shù)據(jù)流信息由卸船進場選位算法計算出最合理的場地位置，并將該計算結(jié)果寫入卸船箱落箱任務(wù)中。

動態(tài)選位模式是指卸船箱進場前不做任何場地堆存計劃，而是通過算法對箱子進行檢測，判斷其類型、尺寸、貨特、貨主、持箱人等信息自動選擇最優(yōu)箱區(qū)，且自動進入最優(yōu)箱區(qū)的最優(yōu)倍位，從而實現(xiàn)現(xiàn)場無人工操作的智能化模式。目前，越來越多的自動化集裝箱碼頭將卸船計劃模塊從計劃部轉(zhuǎn)移到中控室，很大程度上提高了卸船計劃的動態(tài)性。

卸船箱進場自動選位是指管理系統(tǒng)自動為完成岸邊集裝箱起重機卸船作業(yè)的箱子選擇具體的場地位置并生成可供輪胎式集裝箱起重機終端看到的落位任務(wù)過程。集裝箱碼頭卸箱進場自動選位可分3個主要步驟：

1）服務(wù)器索箱 即服務(wù)器檢索進口箱選位任務(wù)，若檢測到該箱子，即進入下一步；

2）最優(yōu)箱位確定 最優(yōu)箱位確定是指給檢測到的箱子制定一個最佳落箱位置，該步驟可分為對檢測到的箱子進行類別判斷、根據(jù)箱子類別進一步確定該類箱子應(yīng)該堆存到場地哪些區(qū)域（卸船箱堆存計劃）、在既定區(qū)域內(nèi)選擇距離場地機械最近的位置、從該倍位上滿足卸箱要求的位置上選擇最優(yōu)落箱位置等環(huán)節(jié)；

3）落箱任務(wù)發(fā)送 將選好的最優(yōu)箱位發(fā)送到該任務(wù)記錄的水平運輸設(shè)備接收終端上，以指導(dǎo)運輸方位。

基于合同網(wǎng)的自動化集裝箱碼頭智能選位過程是通過招標(biāo)－投標(biāo)－中標(biāo)的市場競爭機制進行任務(wù)分配（見圖1）。當(dāng)集裝箱從岸邊卸下等待進場選位時，每個集裝箱會發(fā)出招標(biāo)請求，每個箱區(qū)則會投標(biāo)，通過算法模型可得到每個箱區(qū)給該集裝箱打的分?jǐn)?shù)，最終得到分?jǐn)?shù)的總和為目標(biāo)函數(shù)，分?jǐn)?shù)最高的則為最優(yōu)落箱位置。這種方法考慮了投標(biāo)商之間的負載均衡，綜合考慮與衡量投標(biāo)商的負載、能力和信任度等方面因素，從而使系統(tǒng)以較低代價、較高質(zhì)量完成任務(wù)分配的合同關(guān)系。

圖1 合同網(wǎng)選位過程示意圖

2 模型構(gòu)建

2.1 模型的約束條件

卸船箱選位的約束條件有均衡性約束、合理性約束和有效性約束。模型中使用符號及其表示的意義為：i為等待選位的集裝箱序號，1≤i≤I；I為等待選位的集裝箱總數(shù)；j為箱區(qū)序號，1≤j≤J；J為箱區(qū)總數(shù)；Mij為第i個箱子進入第j個箱區(qū)所獲得的分?jǐn)?shù)；Dij為第i個箱子到第j個箱區(qū)的距離分?jǐn)?shù)；Tj為箱區(qū)j內(nèi)已有任務(wù)數(shù)量；Nj為箱區(qū)j內(nèi)最大任務(wù)數(shù)量；Xij（0,1）矩陣為第i個集裝箱是否進入第j個箱區(qū)；Z為總目標(biāo)函數(shù)。

1）均衡性約束

如圖2所示，每個箱區(qū)的貝位都有最大任務(wù)數(shù)量的限制，并需要留有一定數(shù)量的翻箱位。已知每個區(qū)塊的容量由已知參數(shù)N表示，進入同一區(qū)位的任務(wù)數(shù)量不能超過該區(qū)位的最大任務(wù)數(shù)量，該約束可表示為

圖2 均衡性約束示意圖

2）合理性約束

如圖3所示，一個集裝箱只能進入一個箱區(qū)，目標(biāo)箱位唯一，該約束可表示為

圖3 合理性約束示意圖

3）有效性約束

如圖4所示，一個集裝箱不能進入分?jǐn)?shù)為0的箱區(qū)，該約束可表示為

圖4 有效性約束示意圖

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

該模型所表示的是單目標(biāo)規(guī)劃問題，其目標(biāo)函數(shù)可表示為

該目標(biāo)函數(shù)等于決策變量乘以已知的二維矩陣所有元素之和，趨向于求最大值，即距離分?jǐn)?shù)以及箱子進入箱區(qū)所得分?jǐn)?shù)相加之和的最大化。其中，α、β為平衡兩者分?jǐn)?shù)的權(quán)重系數(shù)，該模型取α和β分別平衡兩者，意味著先考慮Mij即箱子進入箱區(qū)所得的分?jǐn)?shù)為主，而其次考慮距離分?jǐn)?shù)。

3 算例分析

為了證明本文所建立的單目標(biāo)規(guī)劃模型的有效性和可行性，采用Aimms軟件的CPLEX算法庫進行求解。按如下步驟即可得到最優(yōu)解：

步驟1：錄入待整理的箱號、待選箱區(qū)號；

步驟2：導(dǎo)入Mij和Dij的分?jǐn)?shù)、Tj現(xiàn)有任務(wù)數(shù)量；

步驟3：設(shè)置決策變量Xij為Binary矩陣；

步驟4：設(shè)置目標(biāo)函數(shù)Z；

步驟5：設(shè)置3個約束條件（本例中箱區(qū)內(nèi)的最大任務(wù)數(shù)量N取500）；

步驟6：編寫程序。

通過相關(guān)數(shù)據(jù)的錄入，為模型求解提供數(shù)據(jù)支持，從而直觀地從求解結(jié)果中得到作業(yè)計劃的最優(yōu)分配，Aimms決策模型可在短時間內(nèi)對所做方案進行求解，且所求的最優(yōu)方案滿足目標(biāo)函數(shù)取得最大值。

3.1 已知數(shù)據(jù)獲取與分析

根據(jù)模型中的已知參數(shù)定義，該模型需要獲取的數(shù)據(jù)主要包括卸船箱基本信息和箱區(qū)基本信息。某時刻生產(chǎn)系統(tǒng)服務(wù)器獲取到如表1所示10個等待選位的卸船箱，其中集裝箱IRSU5008950為冷藏箱、IRSU5007890為危險品箱。

表1 卸船箱信息表

表2列出了每個堆場箱區(qū)可堆箱子屬性的定義，其中A3箱區(qū)為冷藏箱箱區(qū)、B3箱區(qū)為危險品箱區(qū)，提單號與卸貨港未指定則表示對應(yīng)場位可堆放任意提單號和卸貨港的箱子（表中IF為進口重箱，GP為普通干貨箱）。

表2 箱區(qū)信息表

如圖5所示，將距離分最近、近、中等、遠、最遠等5個等級。例如A1箱區(qū)相對于箱子1和2的距離最近，故打100分；A2箱區(qū)相對較近，故打80分；A3箱區(qū)相對距離中等，故打60分；B1箱區(qū)相對較遠，則打40分；而B2和B3箱區(qū)相對最遠，故打20分，希望盡量不要進入最遠的箱區(qū)。按照上述距離規(guī)則Dij打分如表3所示。

圖5 箱區(qū)布局案例示意圖

表3 Dij分?jǐn)?shù)數(shù)據(jù)表

各箱區(qū)堆存狀態(tài)如圖6～圖11所示，A1箱區(qū)和B2箱區(qū)為堆放提單號為HS03D8765，來自某港的40 ft進重箱；A2箱區(qū)堆放小票箱，即將不同提單號的單個箱子放在一起；A3箱區(qū)為堆放提單號為YMQACTS1234567的冷藏箱箱區(qū)；B1箱區(qū)為空箱區(qū)；B3箱區(qū)為堆放來自某危險品箱區(qū)。

圖6 A1箱區(qū)剖面圖

圖7 A2箱區(qū)剖面圖

圖8 A3箱區(qū)剖面圖

圖9 B1箱區(qū)剖面圖

圖10 B2箱區(qū)剖面圖

圖11 B3箱區(qū)剖面圖

由以上信息可知，箱號IRSU5003253和IRSU5006389為同一提單號，且A1和B1箱區(qū)本身已存放此提單號HS03D8765的箱子，故盡量選擇將同票箱放在一起。同時，A1箱區(qū)可靠粘，B2箱區(qū)可壓粘。在本案例中，取壓粘分?jǐn)?shù)M1為100，靠粘分?jǐn)?shù)M2為90。各箱區(qū)內(nèi)沒有箱子IRSU5002041的同票箱，將雜票箱視為一個同票箱箱區(qū)，可考慮將其放入A2的雜票箱箱區(qū)為最優(yōu)，得100分。而冷藏箱和危險品箱這2個特殊箱則進入已有的冷藏箱區(qū)和危險品箱區(qū)，各得100分。B1箱區(qū)為空箱區(qū)，在空箱區(qū)內(nèi)可開新位，在此取開新位分?jǐn)?shù)M3為80分。其余分?jǐn)?shù)可此類推，箱子進入各箱區(qū)所得的分?jǐn)?shù)參數(shù)Mij如表4所示。

表4 Mij分?jǐn)?shù)數(shù)據(jù)表

3.2 算例求解與分析

模型求解后得到圖12所示的選位結(jié)果，并得到總分為876。其中，冷藏箱IRSU5008950選位進入了冷藏箱區(qū)A3；箱子IRSU5007034進入A1箱區(qū)搶位；箱子IRSU5003253進入A1箱區(qū)靠粘；箱子IRSU5006543、IRSU5004680、IRSU5008068、IRSU5003789進入空箱區(qū)B1，B1隨即成為同票箱箱區(qū)；箱子IRSU5002041因場內(nèi)還沒有進入的同一提單號箱子且為小票箱，故進入A2雜貨箱箱區(qū)；箱子IRSU5006389進入B2箱區(qū)壓粘；危險品箱IRSU5007890選位進入了B3危險品箱區(qū)。經(jīng)過大量的算例分析，證明了模型的有效性，且能達到較高的運算效率。

圖12 卸船箱選位結(jié)果

經(jīng)過大量的算例分析及系統(tǒng)測試，證明了此決策系統(tǒng)性能良好，在對實際場地策劃進行決策的過程中能保持高效率的運行計算。如表5所示，由不同算例所需時間及內(nèi)存對比可知，此決策系統(tǒng)在變量多的情況下計算時間較短，運行性能良好，且占用內(nèi)存較小，在對實際問題進行求解時，可提高箱子選位效率。

表5 算例效率對比

計算時間對比結(jié)果可反映為系統(tǒng)在計算變量數(shù)為12～144時，所用時間存呈遞增趨勢且增勢平緩；在計算變量數(shù)為144～500時，所用時間呈遞增趨勢且增幅較之前略大。

4 總結(jié)

本文通過對指定工藝流程的自動化集裝箱碼頭智能動態(tài)選位問題的研究與實踐，在分析與總結(jié)了不同場地計劃員工大量寶貴經(jīng)驗的基礎(chǔ)上，對自動化集裝箱碼頭卸船箱進場智能選位進行了業(yè)務(wù)探索和理論分析，并建立了基于合同網(wǎng)技術(shù)的智能選位系統(tǒng)算法研究。

經(jīng)過算例分析及實際的系統(tǒng)測試，證明了模型的有效性和實用性，證明了相關(guān)算法和數(shù)據(jù)庫的結(jié)構(gòu)合理性和較強的可拓展性。系統(tǒng)對較大規(guī)模的算例求解具有較好的收斂效果，算法的魯棒性較高。通過不斷改進，系統(tǒng)從索取數(shù)據(jù)到模型構(gòu)建再到模型求解所占用的內(nèi)存資源大大降低，具有一定的承壓能力，保證了系統(tǒng)的穩(wěn)定運行和實時性。系統(tǒng)的應(yīng)用有助于提高碼頭作業(yè)線效率，減少翻箱次數(shù)，最大限度地利用場地資源，從而實現(xiàn)最終決策的最優(yōu)化，具有實際的應(yīng)用價值。