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

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

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

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