集裝箱裝載問題的分析及其有效算法的研究.pdf

1、隨著經(jīng)濟(jì)貿(mào)易的增長，物流效率的提高成為物流產(chǎn)業(yè)發(fā)展的一個(gè)主題。集裝箱作為物流活動(dòng)中最為重要的工具之一，其優(yōu)化問題的研究直接影響著企業(yè)物流費(fèi)用的支出。集裝箱裝載問題是一個(gè)經(jīng)典的組合優(yōu)化問題：給定的一些不同規(guī)格的三維箱子，將箱子的一個(gè)子集裝載進(jìn)集裝箱，使得集裝箱的空問使用率最大。近幾年，該問題的研究相對于過去有較大的突破，這主要源于一種基于塊構(gòu)造的觀念的提出。本文稱使用這個(gè)觀念的算法為基于塊構(gòu)造途徑的算法。近期的一些成功的算法本質(zhì)上都是一類

2、基于塊構(gòu)造途徑的算法。然而這些具體的算法各自包含了許多看似區(qū)別很大的模塊，這使得對該問題及其有效算法做一個(gè)系統(tǒng)的分析顯得非常困難。
　　 本文針對基于塊構(gòu)造途徑的算法提出了一個(gè)包含6個(gè)關(guān)鍵決策因素的分析框架，它們是：1)可行放置區(qū)域的表示；2)候選塊的構(gòu)造；3)可用空問的選擇；4)裝載塊的選擇；5)塊在所選的空間中的裝載；6)總體上使用怎樣的搜索策略。從本質(zhì)上講，所有基于塊構(gòu)造途徑的算法之間的區(qū)別，儀在于它們對這6個(gè)決策要素各自

3、采用的啟發(fā)策略不同?；谠摽蚣埽疚膶诎l(fā)表的兩個(gè)成功但內(nèi)部結(jié)構(gòu)復(fù)雜的算法進(jìn)行剖析，它們分別是劃分控制樹搜索算法(CLTRS)和極大化空問表示算法(MS)。結(jié)合該框架的分析使得這些優(yōu)秀算法內(nèi)部的工作原理可以被更好的理解，另外其不足之處也得以呈現(xiàn)。本文通過組合有效的策略，改進(jìn)評估函數(shù)的準(zhǔn)確度，設(shè)計(jì)了一個(gè)新的啟發(fā)式算法。新算法使用一個(gè)3維的R-Tree來管理集裝箱內(nèi)部的剩余空間，這相對于基于列表的方式能更高效進(jìn)行數(shù)據(jù)維護(hù)。此外，新算法也加