機(jī)器人混合料多盤(pán)裝載問(wèn)題建模與求解

機(jī)器人混合料多盤(pán)裝載問(wèn)題建模與求解

在工業(yè)物流自動(dòng)化領(lǐng)域，使用硬盤(pán)處理大量物質(zhì)堆被認(rèn)為是材料處理的最有效手段，但對(duì)磁盤(pán)負(fù)載問(wèn)題的研究是實(shí)現(xiàn)有效方法的基礎(chǔ)。托盤(pán)裝載問(wèn)題是指如何將一些特定規(guī)格尺寸的長(zhǎng)方體箱子以盡可能多的數(shù)量放入一長(zhǎng)方體容器內(nèi),最大限度地利用長(zhǎng)方體容器的可用空間。若長(zhǎng)方體箱子的高度相同,托盤(pán)裝載問(wèn)題可簡(jiǎn)化為將一些小矩形塊放入大矩形的2維問(wèn)題。它屬于組合優(yōu)化問(wèn)題,國(guó)內(nèi)外許多學(xué)者對(duì)此問(wèn)題進(jìn)行了深入研究并且取得了進(jìn)展[1,2,3,4,5,6,7,8,9,10]。但這些研究只是單一尺寸物料的托盤(pán)裝載問(wèn)題,并且研究對(duì)象僅針對(duì)工程實(shí)踐中單一托盤(pán)的情形。本文結(jié)合機(jī)器人混合碼垛的工程實(shí)踐需要,研究一種新型的混料多盤(pán)裝載問(wèn)題。1如何使用盤(pán)多盤(pán)盤(pán)封裝如圖1所示的機(jī)器人碼垛工作站,無(wú)論是完成圖1a所示的分揀任務(wù),還是圖1b所示的混合碼垛功能,其本質(zhì)是混料多盤(pán)裝載問(wèn)題。如果有足夠多的托盤(pán),混料多盤(pán)裝載問(wèn)題研究的內(nèi)容可以簡(jiǎn)述如下:如何使用數(shù)量最少的長(zhǎng)方體容器(托盤(pán))裝載大小不同、數(shù)量一定的長(zhǎng)方體箱子?？梢?jiàn),混料多盤(pán)裝載追求的目標(biāo)是在滿足規(guī)定約束條件的前提下,盡可能地合理布局箱子在托盤(pán)上的位置,以減小每一個(gè)托盤(pán)上的無(wú)用空間,使平面占有率最大化,從而使托盤(pán)使用總數(shù)目最小。在強(qiáng)調(diào)最小浪費(fèi)的同時(shí),也強(qiáng)調(diào)了最大的利用,二者是辯證統(tǒng)一的。2混料多盤(pán)裝卸問(wèn)題的數(shù)學(xué)模型在圖2所示的托盤(pán)平面上,箱子既可以水平放置,也可以垂直放置。無(wú)論托盤(pán)還是箱子,將長(zhǎng)邊尺寸稱為長(zhǎng)度,短邊尺寸稱為寬度。研究目標(biāo)是將所有給定的箱子裝載到最小數(shù)量的托盤(pán)上。模型的輸入?yún)⒘咳缦?L為托盤(pán)長(zhǎng)度;W為托盤(pán)寬度;li為箱子長(zhǎng)度;wi為箱子寬度;Q為箱子總數(shù);Δ為一個(gè)大數(shù)?；炝贤斜P(pán)裝載問(wèn)題數(shù)學(xué)模型中使用的變量定義如下:xip為托盤(pán)p上箱子i的左下角的橫坐標(biāo);yip為托盤(pán)p上箱子i的左下角的縱坐標(biāo);P為可用托盤(pán)數(shù);σip為二進(jìn)制變量,當(dāng)箱子i放置于托盤(pán)p上時(shí)為1,否則為0;δi為二進(jìn)制變量,當(dāng)箱子i水平放置于托盤(pán)p上時(shí)為1,否則為0;τp為二進(jìn)制變量,當(dāng)托盤(pán)p被使用時(shí)為1,否則為0;Lijp為二進(jìn)制變量,在托盤(pán)p上當(dāng)箱子i放置于箱子j的左側(cè)時(shí)為1,否則為0(設(shè)托盤(pán)p上箱子i的左下角的頂點(diǎn)為Vip,箱子j的左下角的頂點(diǎn)為Vjp,如果Vip位于Vjp的左側(cè),則稱箱子i位于箱子j的左側(cè))。類似地,有二進(jìn)制變量Rijp、Bijp、Tijp,分別表示當(dāng)托盤(pán)p上箱子i放置于箱子j的右側(cè)、下側(cè)、上側(cè)時(shí)為1,否則為0。Lijp、Rijp、Bijp和Tijp的定義暗示了托盤(pán)上箱子之間的相對(duì)位置。這里需要說(shuō)明的是,對(duì)于如圖3a～圖3e的情形,即|xip-xjp|≤liδi+wj(1-δj)時(shí),令Lijp=Rijp=0;對(duì)于見(jiàn)圖4a～圖4e的情形,即|yip-yjp|≤wiδi+lj(1-δj)時(shí),令Bijp=Tijp=0。在上述分析的基礎(chǔ)上,建立混料多盤(pán)裝載問(wèn)題的數(shù)學(xué)模型如下:minτ=∑p=1Pτp(1)minτ=∑p=1Ρτp(1)s.t.xip+liδi+wi(1-δi)≤xjp+(1-Lijp)Δ(2)xjp+ljδj+wj(1-δj)≤xip+(1-Rijp)Δ(3)yip+wiδi+li(1-δi)≤yjp+(1-Bijp)Δ(4)yjp+wjδj+lj(1-δj)≤yip+(1-Tijp)Δ(5)Lijp+Rijp+Bijp+Tijp≥σip+σjp-1(6)∑p=1Pσip=1i=1,2,?,Q(7)∑p=1Ρσip=1i=1,2,?,Q(7)∑i=1Qσip≤Pτpp=1,2,?,P(8)∑i=1Qσip≤Ρτpp=1,2,?,Ρ(8)xip+liδi+wi(1-δi)≤L(對(duì)所有i,p)(9)yip+wiδi+li(1-δi)≤W(對(duì)所有i,p)(10)Δ=max{∑i=1Qli,L}(11)Δ=max{∑i=1Qli,L}(11)Lijp=Rijp=0,當(dāng)|xip-xjp|≤liδi+wj(1-δj)(12)Bijp=Tijp=0,當(dāng)|yip-yjp|≤wiδi+lj(1-δj)(13)τp,δi,σip,Lijp,Rijp,Bijp,Tijp=0或1,xip,yip≥0i,j,p∈Z+,Z+為正整數(shù);i<j式(2)～式(5)確保托盤(pán)平面上各箱子之間不重疊。只有位于同一托盤(pán)上的箱子數(shù)目超過(guò)1時(shí)才檢查是否重疊,這種情形的考慮反映在式(6)中。約束式(7)保證了每一個(gè)箱子只能放在一個(gè)托盤(pán)上。在P個(gè)托盤(pán)中,有一些可能不被使用,而沒(méi)被使用的托盤(pán)上是不能放置任何箱子的,式(8)描述了這種情形。約束式(9)和式(10)則表明放置于托盤(pán)上的所有箱子必須受到托盤(pán)尺寸的限制,不能超出托盤(pán)平面,即托盤(pán)上的箱子不能懸置。約束式(11)～式(13)是為了確保模型運(yùn)行而針對(duì)式(2)～式(6)的附加條件。根據(jù)文獻(xiàn),本文建立的上述模型是一個(gè)混合整數(shù)規(guī)劃模型,既包括0-1變量τp、δi、σip,也包括整數(shù)變量P,以及xip、yip等連續(xù)變量。可是,基于混料多盤(pán)裝載問(wèn)題的上述模型,因?yàn)镻未知而不能被直接求解。為了求解的需要,可以采用迭代法,每次迭代使用不同的P值。注意到目標(biāo)函數(shù)值僅能是整數(shù),可以在一開(kāi)始使用一個(gè)小值去檢驗(yàn)是否能夠找到一個(gè)可行解,如果這樣的可行解存在,則它一定是最優(yōu)的,否則逐量增加P的值重復(fù)迭代過(guò)程。為此,不以P=1開(kāi)始,而是采用一個(gè)下界Pd為(14)其中,表示不小于r的最小整數(shù)。在此基礎(chǔ)上,整個(gè)問(wèn)題的求解思路可以簡(jiǎn)單概括為如下步驟:(1)令P=Pd;(2)令τp=1,p=1,2,…,P;(3)解數(shù)學(xué)規(guī)劃問(wèn)題(*),當(dāng)獲得可行解后停止,(*)表示由式(1)～式(13)的混合整數(shù)規(guī)劃模型;(4)如果在步驟(3)中判斷為不可解,則令P=P+1,然后返回步驟(2)。這里僅強(qiáng)調(diào)如何將混料多盤(pán)裝載問(wèn)題模型化,并給出相應(yīng)的求解策略,而目的不在于如何開(kāi)發(fā)一個(gè)旨在求解上述步驟(3)的應(yīng)用程序。同時(shí)應(yīng)當(dāng)指出,如何找到可行解以及如何判斷無(wú)解是能否正確求解問(wèn)題的關(guān)鍵。為了檢查模型的有效性,我們?cè)贚EGENDPC上使用了SJTU-WXLMPLP軟件求解了一個(gè)小型算例,該算例的數(shù)據(jù)見(jiàn)表1。求解結(jié)果表明問(wèn)題的一個(gè)可行解是P