自動化集裝箱碼頭卸船箱動態選位問題研究*

柴佳祺 張清波 邊志成

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

0 引言

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

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

1 問題描述

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

卸船進場選位算法由集裝箱碼頭營運系統數據庫服務器來執行，其功能是動態監測場地內任務中已被卸船落箱在水平運輸設備上但尚未分配具體場地位置的卸船落位任務，一旦發現目標便根據相關數據流信息由卸船進場選位算法計算出最合理的場地位置，并將該計算結果寫入卸船箱落箱任務中。

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

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

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

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

3）落箱任務發送 將選好的最優箱位發送到該任務記錄的水平運輸設備接收終端上，以指導運輸方位。

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

圖1 合同網選位過程示意圖

2 模型構建

2.1 模型的約束條件

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

1）均衡性約束

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

圖2 均衡性約束示意圖

2）合理性約束

如圖3所示，一個集裝箱只能進入一個箱區，目標箱位唯一，該約束可表示為

圖3 合理性約束示意圖

3）有效性約束

如圖4所示，一個集裝箱不能進入分數為0的箱區，該約束可表示為

圖4 有效性約束示意圖

2.2 目標函數

該模型所表示的是單目標規劃問題，其目標函數可表示為

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

3 算例分析

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

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

步驟2：導入Mij和Dij的分數、Tj現有任務數量；

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

步驟4：設置目標函數Z；

步驟5：設置3個約束條件（本例中箱區內的最大任務數量N取500）；

步驟6：編寫程序。

通過相關數據的錄入，為模型求解提供數據支持，從而直觀地從求解結果中得到作業計劃的最優分配，Aimms決策模型可在短時間內對所做方案進行求解，且所求的最優方案滿足目標函數取得最大值。

3.1 已知數據獲取與分析

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

表1 卸船箱信息表

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

表2 箱區信息表

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

圖5 箱區布局案例示意圖

表3 Dij分數數據表

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

圖6 A1箱區剖面圖

圖7 A2箱區剖面圖

圖8 A3箱區剖面圖

圖9 B1箱區剖面圖

圖10 B2箱區剖面圖

圖11 B3箱區剖面圖

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

表4 Mij分數數據表

3.2 算例求解與分析

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

圖12 卸船箱選位結果

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

表5 算例效率對比

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

4 總結

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

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