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