摘要：集裝箱運輸具有“快速、安全、質優”的特性，已經成為交通運輸現代化的重要標誌和國際貿易的首選方式。配載作為集裝箱運輸過程的一個核心環節，目的是尋求一種滿足倒箱最少和作業高效的裝載方案。在實地調研寧波港3期碼頭的基礎上，結合遺傳演算法，設計了基於禁忌搜尋演算法的集裝箱配置演算法，優化了原有的裝箱演算法，提高了工作效率，對集裝箱碼頭的現代化管理有廣泛的工程背景和應用價值。
關鍵詞：集裝箱 配載 禁忌搜尋 港口 遺傳演算法
港口業一直是寧波的支柱產業，港口的發展拉動了寧波數以千計的外貿產業，也推動了寧波的經濟的發展。如何打造寧波的港口業一直是學術界的熱點問題，而集裝箱配載作為港口的一個重要環節，在港口運輸過程中佔有了重要的地位。它確定了集裝箱在船上的具體位置，形成集裝箱裝卸順序，理想的配置方式可以提高了港口的工作效率，減少了翻箱的次數，保證了船舶和貨物的安全職稱論文。
配置是在保證船舶穩定性和強度的基礎上，根據基本的配置原則，把一定的貨物裝載到船倉的過程。研究的物件是集裝箱。集裝箱碼頭的配置過程如下：
1、集裝箱碼頭配置的作業流程
集裝箱的配置過程分為六步，具體如下：
第一步：確定裝艙貨物卸港的先後次序，後到港的集裝箱放在艙內，先到港的集裝箱後裝或放在甲板上，裝箱的過程中航次貨運量不得大於航次淨載重量，即貨物總的裝箱數量不能超過船舶在當前港口能裝載的總箱數。第二步：依次向艙內安排貨物。按分艙的結果，向艙內裝載貨物，按卸港的順序和箱子的.重量將集裝箱安排到具體的箱位。第三步：計算穩性和總強度。根據船舶資料資料及集裝箱在船上的具體安排情況，計算船舶相關的穩性和總強度資料。第四步：調整。根據穩性和總強度計算的結果對個別集裝箱的位置進行調整，以保證滿足穩性和總強度要求。第五步：預配。預配也稱為佈置配載，主要是將裝載港的集裝箱按貨物型別、尺寸及目的港組成同類箱組，依據一定的預配原則和優化目標將其分配到船舶的不同Bay位上，確定集裝箱在船上的縱向裝載位置，完成集裝箱在船上的總體佈置。第六步：Bay位排箱。Bay位排箱主要是在預配的基礎上，確定單個集裝箱在船上Bay位中的具體位置，主要考慮箱子的尺寸、重量，船舶的穩性及倒箱等因素，確定集裝箱沿船舶縱向和橫向的合理分佈，它將影響船舶的GM、橫傾及扭轉強度。
具體的集裝箱船每航次一般都要停靠多箇中途港進行貨物裝卸，配載時應綜合考慮貨物性質、船舶到港順序、貨物重量、裝卸作業條件，應保證中途港貨物順利卸出及中途港貨物裝卸後的船舶效能，具體配載演算法可考慮以下啟發式規則：①成組指派技術將集裝箱按貨物型別、集裝箱尺寸、到港順序予以歸類，同一屬性的貨物組成同類箱組;以箱組為單位分別在船上選擇相應位置。②當貨物屬性不同時，先特殊後一般將貨物按型別劃分為危險貨物、冷藏貨物及普通貨物.在配載時，應首先選擇危險貨物及冷藏貨物的艙位，然後根據具本情況適當安排普通貨物的艙位。
2、配置過程的數學函式和約束條件
配載達到的要求為滿足一定約束條件下最大體積裝載率或重量裝載率，以提高集裝箱的利用率，獲得最佳效益。裝箱的目標可描述為其中：n為貨物數;k為集裝箱數;li，wi，hi，gi分別表示貨物的長、寬、高和質量;Lj，Wj，Hj，Mj分別表示集裝箱的長、寬、高和最大裝載質量.貨物裝載時必須要求：貨物平行於集裝箱的邊放置;貨物不能完全懸空，放置在上層的貨物必須與下層貨物有接觸。
配置的具體約束如下：約束一：集裝箱重心位置的約束。為了使集裝箱在運輸過程中保持平衡，對集裝箱的重心位置有一定的要求，即實際重心與集裝箱的幾何中心的距離不能超過一定的距離(D)。約束二：集裝箱單箱重量約束。為了便於運輸與搬運，集裝箱單箱重量不超過上限。約束三：貨物放置順序約束。實際裝載過程中儘量做到“大不壓小，重不壓輕”原則，即貨物放置的層有一定的限制。約束四：貨物擺放方位約束。集裝箱長、寬、高均為L、W、H規格，優化目標為集裝箱的空間利用率最高，即對一批固定的貨物進行轉載，使選用集裝箱的數量最少。
3、基於禁忌搜尋演算法的求解方法
禁忌搜尋引入了人工智慧的記憶機制，特別對於一些複雜問題，顯示出極強的尋優能力。禁忌指的是禁止重複前面的操作。為了防止搜尋陷入區域性最優，用一個叫禁忌表的結構記錄下已經到達過的區域性最優點，在下一次搜尋中，利用禁忌表中的資訊不再或有選擇地搜尋這些點，以此來跳出區域性最優點，同時“遺忘”又使禁忌在一定時間後失效，最終達到全域性優化。我們使用DBSTree的演算法來實現這一思想，具體的操作如下：
Step1：初始化箱子容量、箱子標號、物品數量及各物品所佔空間;
Step2：以箱子容量為關鍵值構造DBSTree，併為每個結點標號;
Step3：依次裝載每個物品，如果物品的尺寸大於容量最大的箱子，則將物品拆分，先將超尺寸物品裝入當前容量最大的箱子中，如果拆分後物品的殘餘部分還大於箱子的容量，則繼續拆分，否則轉Step4。
Step4：搜尋：尋找最優匹配的箱子，假設該物品所佔的空間為s1，尋找大於等於量的關鍵值：首先從根開始，如果根為空，那麼搜尋樹不包含任何關鍵值，查詢挫敗，則將醜與根的關鍵值相比較。
Step5：插入：如果箱子未被裝滿，則以箱子的剩餘空間更新箱子容量，假設箱子的剩餘空間為e，則首先通過搜尋二元樹來確定要插入的值e的位置，如果搜尋不成功，新元素插入到搜尋的中斷點，轉Step7：
Step6：刪除：如果箱子已被裝滿，則從樹中刪除最優箱子，分三種情況：
Case1：要刪除的節點t是樹葉：丟棄樹葉結點;
Case2： 要刪除的節點f只有一個非空子樹：如果t沒有父結點，則將t丟棄，t的唯一子樹的節點成為新的搜尋樹的根節點;如果t有父結點node—f，則修改node的指標，使得node指向node的唯一孩子，然後刪除節點node。
Case3： 要刪除一個左右子樹都不為空的節點中的元素，將該元素替換為它的左子樹中的最大元素或右子樹中的最小元素。
Step7：所有物品都被裝載了嗎?如果是，轉Step8;否則轉Step3：
Step8：輸出所用箱子個數、總容量及裝箱結果，結束。
4、結論
集裝箱船配載問題是帶有複雜約束的多目標組合優化問題，傳統優化方法對此類問題的解決因面臨“組合爆炸”而失去可行性，要解決這個問題，必須探討新的優化方法，在探討新的優化演算法過程中，重點研究了神經網路、禁忌搜尋、蟻群演算法及遺傳演算法等。考慮到配載問題的複雜性，單純使用一種演算法無法很好的滿足系統建模的要求，最後選擇針對不同的模型特點採用不同的演算法，主要應用了禁總搜尋演算法，佈局優化中的裝箱演算法和隱式圖啟發式搜尋演算法等用於解決集裝箱船全航線配載問題。
參考文獻：
[1]Steenken D，Stefan V，Rober ainer terminal operation and operatins research：a classification and literation Spectrum，2007，36：3-2[J].
姜義東，何大勇.船舶積載系統的發展.鐵道學報，2008，229(3)：9-13.
Wilson I D，Roach P ciples of combinatorial optimization applied to containership stowage planning. Journal of Heuristic，2009，5：403-408.
黃有群，劉嘉敏.集裝箱裝入演算法的研究.瀋陽工業大學學報，2006，24(4)：306-308.