一維裝箱問題是組合優(yōu)化中的NP難問題,在有限的時間內(nèi)獲得問題的精確解非常困難。啟發(fā)式算法和遺傳算法是解決裝箱問題的兩類主要方法,但是,采用經(jīng)典啟發(fā)式裝箱算法得到的結(jié)果在極端情況下非常差,而遺傳算法在解決裝箱問題的過程中容易出現(xiàn)無效解,致使需要處理的數(shù)據(jù)量十分巨大。為了獲得裝箱問題的近似最優(yōu)解,文中針對目前的裝箱問題算法展開分析,提出了一種新型的啟發(fā)式裝箱算法。提出的IAMBS算法允許裝箱有一定的松弛量,使用隨機(jī)思想搜索局部最優(yōu),進(jìn)而獲得裝箱問題的全局最優(yōu)解。隨機(jī)松弛量使該算法不易陷入局部最優(yōu),具有較強(qiáng)的發(fā)現(xiàn)全局最優(yōu)解的能力。采用來自兩個數(shù)據(jù)集的1 410個基準(zhǔn)測試實例進(jìn)行實驗。最終,IAMBS算法獲得了1 152個實例的最優(yōu)解。實驗數(shù)據(jù)表明,IAMBS算法可以有效地獲得近似最優(yōu)解,比經(jīng)典裝箱算法更有優(yōu)勢。 

【文章來源】：計算機(jī)科學(xué). 2019,46(09)北大核心CSCD

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

【文章目錄】：
1 引言
2 相關(guān)工作
3 解決裝箱問題的啟發(fā)式算法
    3.1 一維裝箱問題的數(shù)學(xué)描述
    3.2 經(jīng)典的啟發(fā)式算法
    3.3 MBS算法
    3.4 MBS衍生算法
    3.5 蒙特卡洛算法和拉斯維加斯算法
4 AMBS算法
5 IAMBS
6 實驗分析
    6.1 實驗環(huán)境
    6.2 算法性能評價指標(biāo)
    6.3 實驗數(shù)據(jù)集
    6.4 實驗結(jié)果



本文編號：3198093