求解二維不規(guī)則帶排樣問題的擴(kuò)展局部搜索算法.pdf

1、二維不規(guī)則帶排樣問題(two-dimensional irregular strip packing problem),又稱為下料問題(nesting problem),它在工業(yè)生產(chǎn)中有著廣泛的應(yīng)用,其典型應(yīng)用如服裝制造、鋼鐵切割、家具制造、制鞋工業(yè)等制造工業(yè)中的零件下料問題。該問題的研究目標(biāo)在于如何充分利用原材料,即盡量減少原材料消耗,提高經(jīng)濟(jì)效益。因此研究二維不規(guī)則帶排樣問題有著非常重要的實(shí)際應(yīng)用價(jià)值。
　　 本文提出了求解

2、二維不規(guī)則帶排樣問題的擴(kuò)展局部搜索(ELS)算法。該算法首先采用簡單的啟發(fā)策略來獲得待排樣多邊形的一個(gè)合法放置。然后利用局部搜索算法來得到更好的解。局部搜索中所采用的鄰域?yàn)?交換兩個(gè)多邊形的位置和將一個(gè)多邊形放置到一個(gè)新的位置。在移動(dòng)多邊形的過程中可能會(huì)產(chǎn)生重疊區(qū)域,無約束非線性規(guī)劃模型被用于最小化這一重疊區(qū)域,以此來獲得一個(gè)合法的放置。在搜索過程中引入了禁忌搜索以避免陷入局部最優(yōu)。最后,本文還提出了一個(gè)壓縮算法用于進(jìn)一步優(yōu)化已得到的合