基于禁忌搜索算法的集裝箱裝載問題研究.pdf

1、集裝箱裝載問題(Container Loading Problem，簡稱CLP)屬于“切割和裝入”問題，在數(shù)學(xué)理論上為NP完全問題，即不能在多項(xiàng)式時(shí)間內(nèi)找到問題的最優(yōu)解。CLP雖然求解困難，但隨著計(jì)算機(jī)技術(shù)的發(fā)展，使用計(jì)算機(jī)輔助求解CLP成為可能，但因CLP本身特征，實(shí)際應(yīng)用中無法采用純數(shù)學(xué)方法，而是采用基于啟發(fā)式的近似求解方法。 計(jì)算機(jī)輔助布局優(yōu)化能夠有效提高空間裝載效率，在鐵路和遠(yuǎn)洋運(yùn)輸中能夠降低運(yùn)輸成本，研究成果還可以推廣

2、到計(jì)算機(jī)內(nèi)存分配等空間資源優(yōu)化領(lǐng)域，因此有著重要的實(shí)際意義。近年來CLP逐漸成為人們關(guān)注的焦點(diǎn)。 本文緒論先對CLP的產(chǎn)生背景及實(shí)際意義進(jìn)行論述，然后對其研究范疇和分類予以介紹，最后在查閱大量文獻(xiàn)的基礎(chǔ)上闡明了CLP的國內(nèi)外發(fā)展現(xiàn)狀。 禁忌搜索算法(Tabu Search，簡稱TS)是近年來逐漸引起人們興趣的一種現(xiàn)代啟發(fā)式算法，因其特殊的“記憶”機(jī)制，表現(xiàn)出極好的全局尋優(yōu)能力，在對一些復(fù)雜、困難問題的求解中取得了很好效果

3、。本文從TS的原理、搜索技術(shù)以及收斂理論等方面進(jìn)行說明。 應(yīng)用TS求解CLP在國內(nèi)還沒有相關(guān)研究，本文結(jié)合CLP的實(shí)際特征，提出了不同于Bortfeldt和Gehring方法的新的編碼、解碼及鄰域解構(gòu)造方法；在解碼中引入了新的空間合并策略，提高了集裝箱利用率；應(yīng)用“組合塊”思想減少了剩余空間的零碎劃分，降低了搜索代價(jià)；本文創(chuàng)造性的將TS應(yīng)用于求解多箱裝載問題，取得了理想效果。 結(jié)果顯示對于集裝箱裝載系統(tǒng)的應(yīng)用有重要意義，