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