針對(duì)經(jīng)典的一維離線裝箱問(wèn)題,本文首次提出了利用降序最佳適應(yīng)BFD算法與禁忌搜索算法混合使用來(lái)解決此類(lèi)問(wèn)題的方法,并用Microsoft Visual C++編程得以實(shí)現(xiàn),詳細(xì)說(shuō)明了算法的關(guān)鍵內(nèi)容與步驟,并通過(guò)算例與簡(jiǎn)單遺傳算法和單純使用禁忌搜索算法解決裝箱問(wèn)題進(jìn)行了對(duì)比,得到以下結(jié)論:在求解一維離線裝箱問(wèn)題時(shí),BFD算法與禁忌搜索算法混合使用要比單純地使用禁忌搜索算法和簡(jiǎn)單遺傳算法效果好,實(shí)用價(jià)值良好。

【文章頁(yè)數(shù)】：5 頁(yè)

【部分圖文】：

圖1(a)某裝箱問(wèn)題的解1

(2)初始解:對(duì)于給定的m個(gè)物品按重量從大到小進(jìn)行排序，然后用BFD算法求得初始解，該初始解即為禁忌搜索的初始迭代起點(diǎn)。圖1(b)某裝箱問(wèn)題的解2

圖1(b)某裝箱問(wèn)題的解2

圖1(a)某裝箱問(wèn)題的解1(3)鄰域結(jié)構(gòu):即對(duì)m個(gè)物品(x[0]～x[m-1])解的序列中2個(gè)物品位置的變化，其中規(guī)定第一個(gè)物品的位置固定不變，在領(lǐng)域的映射為解的2-opt。如圖1(a)中的解將x[3]與x[4]位置調(diào)換后變成了圖1(b)中解的情況，即為一次鄰域搜索過(guò)程，且規(guī)定第....

圖2 算例中各物品的重量信息

為了便于說(shuō)明BFD算法與禁忌搜索算法混合使用的優(yōu)越性，本文將其與單純使用禁忌搜索算法和簡(jiǎn)單遺傳算法進(jìn)行比較，算法由MicrosoftVisualC++編程實(shí)現(xiàn)。圖3為單純使用禁忌搜索算法得到的最優(yōu)裝箱方案。圖4為BFD算法與禁忌搜索算法混合使用所得到的最優(yōu)方案。圖3單獨(dú)使用....

圖3 單獨(dú)使用禁忌搜索算法的求解情況

圖2算例中各物品的重量信息圖4BFD與禁忌搜索混合使用的求解情況

本文編號(hào)：4050735