三維裝箱問題是一類組合優(yōu)化問題,多用于物流運(yùn)輸業(yè)的貨物裝載,具有重要的實(shí)踐意義。它的最優(yōu)解受多種條件因素的影響,求解形式復(fù)雜且計(jì)算量較大,所以常用啟發(fā)式算法來解決。以空間分割為原則的啟發(fā)式算法融入遺傳算法中并結(jié)合二層規(guī)劃的思想,提出一種基于雙層啟發(fā)式遺傳的三維裝箱算法。通過雙層啟發(fā)式遺傳策略分別對可行解進(jìn)行廣度和深度的搜索來提高尋優(yōu)效率,從而得到最優(yōu)的三維裝箱方案。在此基礎(chǔ)上利用具體算例進(jìn)行運(yùn)算和分析,證明該算法在空間利用率和穩(wěn)定性上都有較好的效果,同時(shí)裝箱方案可以依托計(jì)算機(jī)技術(shù)進(jìn)行三維可視化,可為三維裝箱問題的信息可視化提供理論依據(jù)。 

【文章來源】：科學(xué)技術(shù)與工程. 2020年05期 北大核心

【文章頁數(shù)】：6 頁

【部分圖文】：

空間分割示意圖

圖2所示為基于雙層啟發(fā)式遺傳算法流程。上層遺傳使用選擇、交叉、變異等不受限的遺傳演化形式,這是為了加大可行解的搜索范圍,找到一個(gè)足夠優(yōu)秀的可行解;下層遺傳在上層遺傳的基礎(chǔ)上對這個(gè)可行解進(jìn)行有目的的多層次變異,經(jīng)過迭代進(jìn)化得到最優(yōu)解。從宏觀上對算法進(jìn)行分析,上層遺傳是面向廣度的搜索,而下層遺傳是面向深度的搜索,結(jié)合兩層遺傳的特點(diǎn)綜合使用可以找到最合適的裝箱方案。2.3 下層遺傳算法的設(shè)計(jì)

新的遺傳演化方法的特殊性主要體現(xiàn)在變異算子上,如圖3所示,在變異前要先確立有效裝箱區(qū)和無效裝箱區(qū),選定一個(gè)可行解編碼次序按照裝箱算法依次放入,直到出現(xiàn)無法放入箱容器內(nèi)的箱體則停止放入,該箱體之前的次序則為有效裝箱區(qū),其余的次序則都是無效裝箱區(qū)。如圖4所示,當(dāng)變異開始時(shí)隨機(jī)選取有效裝箱區(qū)的一位基因A和無效裝箱區(qū)的一位基因B,基因A放入無效裝箱區(qū)基因B的位置,有效裝箱區(qū)內(nèi)基因A之后的基因依次向前移動(dòng)一位,基因B放入有效裝箱區(qū)的最后一位。此后對新的有效裝箱區(qū)再運(yùn)行一遍裝箱算法并評估長度,如果與之前的有效裝箱區(qū)長度一樣,則再從無效裝箱區(qū)中隨機(jī)選取一位基因放入有效裝箱區(qū)的尾部,重復(fù)上述步驟直至有效裝箱區(qū)的長度無法再增加,則一次完整的變異過程結(jié)束。

【參考文獻(xiàn)】：
期刊論文
[1]求解非標(biāo)準(zhǔn)貨物貨機(jī)群裝載問題的啟發(fā)式搜索算法[J]. 鄭琰,李鵬.  科學(xué)技術(shù)與工程. 2018(23)
[2]有角件約束的集裝箱配載問題優(yōu)化算法[J]. 那日薩,崔雪蓮,韓琪瑋.  工業(yè)工程與管理. 2016(01)
[3]帶平衡約束三維裝箱問題的雙層混合遺傳算法[J]. 朱向,雷定猷.  交通運(yùn)輸系統(tǒng)工程與信息. 2015(02)
[4]求解三維裝箱問題的多層啟發(fā)式搜索算法[J]. 張德富,彭煜,張麗麗.  計(jì)算機(jī)學(xué)報(bào). 2012(12)
[5]遺傳算法選擇策略比較[J]. 張琛,詹志輝.  計(jì)算機(jī)工程與設(shè)計(jì). 2009(23)
[6]基于空間優(yōu)化的三維裝箱布局混合遺傳算法[J]. 莊鳳庭,宋淑娜,高尚.  科學(xué)技術(shù)與工程. 2009(03)
[7]求解矩形Packing問題的砌墻式啟發(fā)式算法[J]. 張德富,韓水華,葉衛(wèi)國.  計(jì)算機(jī)學(xué)報(bào). 2008(03)
[8]三維裝箱問題的組合啟發(fā)式算法[J]. 張德富,魏麗軍,陳青山,陳火旺.  軟件學(xué)報(bào). 2007(09)
[9]平衡裝載問題的優(yōu)化模型和算法[J]. 雷定猷,陳德良.  系統(tǒng)工程學(xué)報(bào). 2004(03)

碩士論文
[1]三維裝箱問題的混合遺傳算法研究[D]. 翟鈺.上海交通大學(xué) 2007
[2]裝箱問題方法研究及其集成應(yīng)用[D]. 韓運(yùn)實(shí).中國海洋大學(xué) 2004



本文編號：2931413