多約束有色三維裝箱問題的混合遺傳算法研究.pdf

1、三維裝箱問題研究歷史悠久，是一個(gè)典型的NP完全難題，廣泛存在于生產(chǎn)生活的各個(gè)角落，對國民經(jīng)濟(jì)的影響巨大，尤其存在于現(xiàn)代物流行業(yè)中。對物流企業(yè)來說，優(yōu)化裝載問題，提高箱體體積或載重利用率可以壓縮企業(yè)成本，從而提高企業(yè)競爭力，因此三維裝箱問題是現(xiàn)代物流所研究的一個(gè)重要問題。
　　按裝載目標(biāo)可將三維裝箱問題分為箱柜裝載問題、容器裝載問題和背包裝載問題，其中箱柜裝載問題是以最少數(shù)目限定規(guī)格的集裝箱裝入所有需要裝入的貨物為研究目標(biāo)，是三維裝

2、箱問題一類重要的研究方向。本文以箱柜裝載問題為主要研究對象，結(jié)合實(shí)際應(yīng)用提出了多約束有色三維裝箱問題。多約束有色三維裝箱問題由多約束三維裝箱問題和有色裝箱問題組成，其中多約束三維裝箱研究者頗多，主要為解決實(shí)際生活中貨物擺放方式、裝卸順序、承受脆度不同而設(shè)計(jì)的一類三維裝箱問題;而有色裝箱是指裝入同一個(gè)箱子的貨物類型或者顏色要互異的一類裝箱問題。多約束三維裝箱問題是結(jié)合兩類問題的綜合問題。論文從多約束有色三維裝箱問題的產(chǎn)生背景以及研究意義出

3、發(fā)，對此類問題進(jìn)行深度剖析，提出了從模型建立到混合遺傳算法的一整套解決方案。解決方案首先包括多約束有色三維裝箱問題模型的抽象，并在此基礎(chǔ)上設(shè)計(jì)裝箱過程中的定位規(guī)則，利用遺傳算法的全局優(yōu)化能力尋找近似最佳解。在子空間分解問題上本文提出了基于空間優(yōu)化分解的空間分解方法，即箱體子空間的劃分是基于即將裝入未劃分的空間的物品對該空間的利用率來決定的，并提出了一種的新的數(shù)據(jù)結(jié)構(gòu)——改進(jìn)型三叉樹來表示此類空間劃分，在子空間使用最佳合并策略進(jìn)行合并，算