朱 向,雷定猷,游 偉

(中南大學(xué)交通運(yùn)輸工程學(xué)院,長(zhǎng)沙410075)

多階段帶時(shí)間約束的變尺寸裝箱問(wèn)題優(yōu)化研究

朱 向*,雷定猷,游 偉

(中南大學(xué)交通運(yùn)輸工程學(xué)院,長(zhǎng)沙410075)

多階段帶時(shí)間約束的變尺寸裝箱問(wèn)題,是將一般的變尺寸裝箱問(wèn)題(VS-BPP)置于動(dòng)態(tài)環(huán)境下并加入時(shí)間約束而形成的.通過(guò)合理的計(jì)劃對(duì)多階段、有交付時(shí)間要求的物品選擇箱子進(jìn)行裝入,達(dá)到包括箱子使用成本及與物品相關(guān)時(shí)間成本在內(nèi)的總成本最小化的目的.問(wèn)題具有復(fù)雜、動(dòng)態(tài)的特點(diǎn),其在現(xiàn)實(shí)中的應(yīng)用很多.本文將一般的帶時(shí)間約束的VS-BPP置于多階段研究框架內(nèi),建立了基于確定信息的靜態(tài)模型和基于滾動(dòng)更新信息的動(dòng)態(tài)模型,根據(jù)問(wèn)題的特點(diǎn)設(shè)計(jì)了基于最佳適應(yīng)規(guī)則與迭代松弛定界法相結(jié)合的啟發(fā)式構(gòu)造算法進(jìn)行求解.經(jīng)過(guò)實(shí)例的運(yùn)算和分析,證明了方法在求解該問(wèn)題時(shí)具有有效性.

物流工程;動(dòng)態(tài)優(yōu)化;構(gòu)造算法;變尺寸裝箱;帶時(shí)間約束

1 引 言

變尺寸裝箱(VariableSizeBinPacking Problem,VS-BPP)問(wèn)題是在經(jīng)典的裝箱問(wèn)題基礎(chǔ)上,將箱子擴(kuò)展為多種規(guī)格而提出來(lái)的,即指將不同大小的物品分配到不同大小有容量限制的一系列箱子里,要求所使用箱子的總成本(或總數(shù))最小,它屬于典型的NP難題.目前關(guān)于VS-BPP的研究比較多,集中于如何提高算法求解的質(zhì)量和速度方面[1,2],對(duì)帶時(shí)間約束變尺寸裝箱問(wèn)題(T-VSBPP)涉及不多.文獻(xiàn)[3]基于物品到達(dá)時(shí)間的不確定,提出了隨機(jī)帶時(shí)間約束的變尺寸裝箱問(wèn)題(ST-VS-BPP)并進(jìn)行了研究,該裝箱問(wèn)題具有動(dòng)態(tài)性特點(diǎn),但主要屬于單階段問(wèn)題;文獻(xiàn)[4]針對(duì)制造商托盤裝載問(wèn)題建立了整數(shù)規(guī)劃模型,可適應(yīng)下游顧客多品種及實(shí)時(shí)性裝盤要求;文獻(xiàn)[5]針對(duì)及時(shí)生產(chǎn)制下實(shí)時(shí)二維切斷下料問(wèn)題,建立了基于滾動(dòng)時(shí)域和Multi-agent方法的求解框架.基于已有研究,本文結(jié)合裝箱問(wèn)題在實(shí)際操作中具有的條件不確定及連續(xù)運(yùn)行的特點(diǎn),提出多階段帶時(shí)間約束變尺寸裝箱的概念,并嘗試對(duì)這一具有復(fù)雜動(dòng)態(tài)特點(diǎn)的問(wèn)題進(jìn)行研究.

2 問(wèn)題的描述及數(shù)學(xué)模型

2.1 問(wèn)題的描述

設(shè)場(chǎng)地內(nèi)有一系列需要裝載的物品及不同規(guī)格可供裝載使用的箱子,物品具有不同體積及交付時(shí)間等屬性,不同類型的箱子對(duì)應(yīng)不同的使用成本,且隨著時(shí)間的推移,后續(xù)需要裝載的物品才能陸續(xù)到達(dá),要求基于已掌握的信息進(jìn)行合理的計(jì)劃安排,在完成相關(guān)物品裝載任務(wù)的前提下實(shí)現(xiàn)包括使用成本和時(shí)間成本在內(nèi)的總成本最小化.現(xiàn)實(shí)中與之相類似的問(wèn)題很多:如在貨物運(yùn)輸中,運(yùn)量大的鐵路、船舶等方式單位貨運(yùn)成本比較低,可實(shí)現(xiàn)規(guī)模經(jīng)濟(jì)效益,但貨物集結(jié)與裝運(yùn)的時(shí)間較長(zhǎng),運(yùn)量小的公路運(yùn)輸單位成本高,但發(fā)運(yùn)時(shí)間短,可滿足適時(shí)性要求較高的運(yùn)輸任務(wù);同種方式不同規(guī)格的裝運(yùn)工具也存在成本和時(shí)間上的差異;工業(yè)生產(chǎn)中產(chǎn)品以不同單元組合進(jìn)行加工成本不一樣,但同時(shí)需要滿足訂單在時(shí)間規(guī)定方面的要求.上述問(wèn)題都存在裝載規(guī)格、處理成本及作業(yè)時(shí)間上的計(jì)劃與協(xié)調(diào)問(wèn)題,且具有實(shí)時(shí)動(dòng)態(tài)的特點(diǎn).

2.2 數(shù)學(xué)模型

為了使裝箱計(jì)劃既能滿足各方面要求,又反映隨時(shí)間推移動(dòng)態(tài)變化的情況,可確定多階段基于時(shí)間約束的變尺寸裝箱框架來(lái)處理.首先,需要界定問(wèn)題跨越的時(shí)區(qū)(如24小時(shí)),并按批量的累積規(guī)律將時(shí)區(qū)劃分為若干計(jì)劃階段;再針對(duì)每個(gè)階段累積的裝載物品,按其總體積與處理的時(shí)間要求,結(jié)合期間可用箱子的裝載能力,確定合理的裝載單元組合,以實(shí)現(xiàn)各階段總成本最小化的目的.由于多階段帶時(shí)間約束VS-BPP是在一般的VS-BPP的基礎(chǔ)上,基于動(dòng)態(tài)作業(yè)條件并考慮相關(guān)時(shí)間約束而形成的,對(duì)于動(dòng)態(tài)特性問(wèn)題可采取基于確定信息的靜態(tài)方法和基于實(shí)時(shí)信息的動(dòng)態(tài)方法[5],據(jù)此建立該問(wèn)題的模型.

2.2.1 靜態(tài)裝箱模型

設(shè)i為物品集N={1,…,n}中的第i個(gè)需要裝載的物品,物品的體積為vi,到達(dá)時(shí)間為Ai;設(shè)R={1,…,r}為可用箱子集合,其中的箱子j的裝載容積為Vj,其使用成本為Cj.關(guān)于時(shí)間方面屬性,設(shè)物品i到達(dá)時(shí)間為Ai,箱子j可用時(shí)刻為Aj,j在k階段裝載過(guò)程中耗費(fèi)時(shí)間為L(zhǎng)j(考慮由固定準(zhǔn)備時(shí)間α和與裝載數(shù)量有關(guān)的可變時(shí)間兩部分組成),設(shè)j裝載完畢進(jìn)入后續(xù)處理的時(shí)刻為tkj.根據(jù)上述設(shè)定,物品在系統(tǒng)中滯留的時(shí)間應(yīng)為tkj-Ai,令單位時(shí)間滯留成本(如暫存成本)為W;箱子j裝載完即進(jìn)入后續(xù)處理階段,設(shè)處理耗費(fèi)時(shí)間為Pkj,進(jìn)而可確定物品實(shí)際交付時(shí)間.設(shè)規(guī)定交付時(shí)間為Di,若存在延時(shí)設(shè)對(duì)應(yīng)延遲時(shí)間為di,單位延遲成本為pi.最后關(guān)于0-1決策變量ukj和Xikj,當(dāng)?shù)趉階段箱子j被使用及物品i裝入箱子j時(shí)它們?nèi)≈刀紴?,否則為0.

首先,按照各階段掌握的信息制定裝箱計(jì)劃,對(duì)應(yīng)各階段的目標(biāo)函數(shù)式為

式(1)表示第k階段裝箱對(duì)應(yīng)的箱子使用成本、物品停留成本,以及物品延遲交付成本之和最小化.

目標(biāo)函數(shù)(2)最小化m階段包括箱子使用成本、物品停留成本以及物品延遲交付成本在內(nèi)的總成本.約束條件(3)、(4)為一般的VS-BPP問(wèn)題的約束條件:式(3)對(duì)裝入箱子中的物品的重量進(jìn)行約束,式(4)表示一件物品只裝入一個(gè)箱子.式(5)至式(7)為第k階段箱子j裝載及加工對(duì)應(yīng)的時(shí)間約束:式(5)表示第k階段箱子j開始處理時(shí)間與其到達(dá)時(shí)間及裝載所耗費(fèi)時(shí)間之間的關(guān)系,式(6)表示第k階段箱子j開始處理時(shí)間與箱內(nèi)各物品的到達(dá)時(shí)間及裝載時(shí)間之間的關(guān)系,式(7)表示第k階段箱子j開始處理時(shí)間與箱內(nèi)各物品交付時(shí)間之間的關(guān)系.M為充分大的正數(shù),以保證相關(guān)約束條件在物品i裝入箱子j時(shí)才起作用.

2.2.2 動(dòng)態(tài)裝箱模型

動(dòng)態(tài)裝箱是基于實(shí)時(shí)更新的信息不斷對(duì)計(jì)劃進(jìn)行修改,以反映實(shí)際變化了的情況,與實(shí)際操作中的環(huán)境相符.沿用靜態(tài)裝箱中確定時(shí)區(qū)的方法將整個(gè)時(shí)段按物品數(shù)量累積情況分為m階段,當(dāng)前階段裝箱計(jì)劃可結(jié)合未來(lái)若干階段進(jìn)行考慮:若當(dāng)前階段為s,設(shè)每次計(jì)劃所跨越的階段數(shù)為K+1,則需對(duì)第s,s+1,…,s+K階段一起計(jì)劃.此外,由于隨著時(shí)間推移后續(xù)新的需裝載的物品和箱子將進(jìn)一步到達(dá),則基于當(dāng)前條件形成的多階段計(jì)劃應(yīng)體現(xiàn)不同階段產(chǎn)生的作用不同,可通過(guò)引入權(quán)重加以反映.由此,得到問(wèn)題在當(dāng)前階段的裝箱模型為

式(9)中αs,k表示第k階段裝箱在當(dāng)前(第s階段)計(jì)劃中所占的比重,考慮采用降序形式權(quán)重,可令αs,k為等,其中0≤αs≤1,具體數(shù)值可根據(jù)系統(tǒng)的歷史運(yùn)行,通過(guò)統(tǒng)計(jì)的方法來(lái)確定,即α=1-物品數(shù)波動(dòng)率=1-新到達(dá)物品數(shù)/(已確定物品數(shù)+新到達(dá)物品數(shù)).

3 算法設(shè)計(jì)

3.1 初始解生成

由于涉及多方面因素,問(wèn)題具有規(guī)模大、動(dòng)態(tài)復(fù)雜的特點(diǎn),為了降低難度實(shí)現(xiàn)問(wèn)題快速求解,本文設(shè)計(jì)了啟發(fā)式構(gòu)造算法(Heuristics Constructive Algorithm,HCA)進(jìn)行求解.它是在啟發(fā)式規(guī)則的引導(dǎo)下逐個(gè)將物品裝入箱子,這一過(guò)程需要將選擇裝載對(duì)象與選擇空間相結(jié)合.根據(jù)問(wèn)題的特點(diǎn),先確定各階段需要裝載的物品,并對(duì)物品進(jìn)行排序以便于后續(xù)裝箱;再運(yùn)用松弛定界法計(jì)算出使用箱子數(shù)量的下界,達(dá)到控制箱子總數(shù)及降低使用成本的目的;然后在此基礎(chǔ)上采用最佳適應(yīng)規(guī)則(BFD),以迭代的方式增加箱子來(lái)完成物品裝箱.

3.1.1 物品排序

由于多階段裝箱的物品是隨時(shí)間的推移以動(dòng)態(tài)形式到達(dá),可先根據(jù)物品到達(dá)的批次及其時(shí)間關(guān)系進(jìn)行裝箱階段的劃分,進(jìn)而確定各階段裝載的對(duì)象,并按一定的規(guī)則對(duì)其進(jìn)行排序以便于后續(xù)裝載.

對(duì)物品排序時(shí)結(jié)合考慮裝箱成本與時(shí)間成本兩方面因素,采取聚類排序的方法來(lái)實(shí)現(xiàn):設(shè)Dmin與Dmax對(duì)應(yīng)為各階段物品交付時(shí)間的上下限,將整個(gè)聚類區(qū)間分為若干簇,每簇區(qū)間的長(zhǎng)度相等,為上下極值之差乘以某一百分比系數(shù)[1,100],第i簇對(duì)應(yīng)的時(shí)段Di(θ)為

將所有物品按交付時(shí)間劃分為若干簇后,按簇的標(biāo)號(hào)進(jìn)行升序排列,對(duì)每簇內(nèi)的物品按對(duì)應(yīng)的單位延遲成本pi作降序排列,單位延遲成本相同的按物品體積作降序排列.綜上可得到階段內(nèi)物品的裝載序列,對(duì)其中物品賦予相應(yīng)的分值,給予第一個(gè)裝入對(duì)象分值為n,其次為n-1,…,最后一個(gè)為1.

3.1.2 箱子定界

裝箱問(wèn)題基于放松約束條件的下界求解方法,可確保最終使用箱子的數(shù)量較少,借鑒文獻(xiàn)[6]提出的松弛定界方法確定各階段使用箱子的下界.不考慮時(shí)間約束,利用松弛方法對(duì)2.2.1中的模型實(shí)施改造,得到松弛問(wèn)題模型:

而式(14)-式(16)組成的模型為0-1背包問(wèn)題模型,利用確定性方法求得下界LB(Z(y)),由此計(jì)算松弛問(wèn)題的下界:LB(Z(y)),以此作為某階段VS-BPP的箱子被選集.

3.1.3 裝箱處理

物品及箱子排序后,按照序列可依次將物品裝入對(duì)應(yīng)的箱子.裝載時(shí)優(yōu)先選擇已使用的箱子,當(dāng)已使用箱子裝不下時(shí)再打開序列中下一個(gè)新的箱子進(jìn)行裝載;對(duì)能裝進(jìn)物品且已裝入物品的多個(gè)箱子,按照BFD規(guī)則選擇箱子裝載,即選擇具有最大剩余空間(箱子的容積減去已裝載物品體積和)的箱子裝入當(dāng)前物品.

由下界方法確定的箱子序列難以將物品全部裝完,當(dāng)剩余物品較多時(shí),可對(duì)剩余物品重新計(jì)算下界,并以迭代的方式增加箱子進(jìn)行裝載;當(dāng)經(jīng)裝載后剩余物品數(shù)量較少時(shí),通過(guò)成本估算與比較來(lái)確定在本階段增加箱子完成裝載,還是將物品轉(zhuǎn)移至下一階段與后續(xù)物品合并裝載.

算法1 初始解生成過(guò)程

Step 1確定多階段VS-BPP跨越的時(shí)區(qū)T,根據(jù)已掌握的物品批次到達(dá)及交付時(shí)間信息將T分為Nj階段,確定各階段對(duì)應(yīng)的時(shí)間范圍.

Step 2對(duì)第k階段中對(duì)應(yīng)的物品,確定各物品i的交付時(shí)間di;根據(jù)di將第k階段內(nèi)物品按交付時(shí)間先后順序分為m簇,再將每簇中物品按體積作降序排列,將各簇物品序列相連得到第k階段的物品序列.

Step 3確定第k階段到達(dá)的可用箱子,運(yùn)用松弛定界法計(jì)算該階段使用箱子的下界,對(duì)其按體積以降序排列得到第k階段的箱子序列.

Step 4按物品序列選擇物品、按箱子序列確定箱子,并結(jié)合BFD規(guī)則選擇箱子實(shí)施第k階段裝箱,優(yōu)先裝入已使用的箱子,直至物品不能裝入為止.

Step 5設(shè)最大箱子的體積為Vmax,若階段k的剩余物品的總體積Vk＞Vmax,按Step 2至Step 4以迭代的方式進(jìn)行裝載,同時(shí)更新Vk,直至Vk≤Vmax轉(zhuǎn)Step 6.

Step 6確定能裝入第k階段最后剩余物品成本最小的箱子組合,設(shè)其對(duì)應(yīng)成本為Ck1;若將其轉(zhuǎn)入第k+1階段,與第k+1階段物品一起按Step 2至Step 4過(guò)程進(jìn)行裝箱,計(jì)算轉(zhuǎn)入物品需分?jǐn)偟南渥映杀?加上對(duì)應(yīng)的延遲交付成本得到轉(zhuǎn)入成本Ck2.

Step 7若Ck1≤CK2,則剩余物品在本階段裝載,將Ck1計(jì)入第k階段總成本;若Ck1≥Ck2,則剩余物品在第k+1階段裝載,相關(guān)成本計(jì)入第k+1階段.

Step 8當(dāng)k≤Nj時(shí),令k=k+1,基于Step 6、Step 7考慮是否有物品加入,確定階段總待裝物品,按Step 2至Step 7進(jìn)行新階段物品裝箱.

Step 9當(dāng)k=Nj時(shí),將各階段裝箱計(jì)劃相加得到的完整的裝載方案,作為問(wèn)題初始解輸出.

3.2 解的改進(jìn)

不同的物品序列形成不同的裝載條件,并產(chǎn)生不同的裝載效果,因此可通過(guò)改變物品的裝載序列來(lái)獲得不同的解.下面基于物品分值更新機(jī)制對(duì)各階段物品序列進(jìn)行調(diào)整,以實(shí)現(xiàn)物品在箱子間重新分配及最優(yōu)解搜索的目的.

算法2初始解優(yōu)化過(guò)程.

Step 1設(shè)k代表第k階段裝箱,Bk是初始解中第k階段使用的箱子集,代表裝載率較高的箱子,b(i)為物品i所在的箱子;設(shè)以裝載率排序的箱子序列為(1,2,…,|Bk|),取B′k=另設(shè)n為第n輪更新,并設(shè)迭代產(chǎn)生的最優(yōu)目標(biāo)函數(shù)值為ZM,初始值為Z0.

Step 2令n=1,k=1,p=1,r=1按公式si=與)對(duì)物品的分值進(jìn)行修改,其中m為分?jǐn)?shù)修改的比例參數(shù),ˉs為分?jǐn)?shù)修改的最大百分比,p為ˉs的調(diào)節(jié)系數(shù),r為物品發(fā)生位置交換的數(shù)量規(guī)模參數(shù),pm、rm分別為p和r的最大值.

Step 3令k=k+1,轉(zhuǎn)Step 1完成后續(xù)各階段物品分?jǐn)?shù)修改,由此確定新的各階段物品裝載序列,再按算法1重新進(jìn)行裝箱,并計(jì)算新方案的目標(biāo)函數(shù)值Zn(n=1,…,ND).

Step 4當(dāng)n≤ND時(shí),令n=n+1進(jìn)入新的搜索:若r＜rm時(shí),令r=r+1,若r=rm時(shí),重置r=1,按Step 1至Step 3確定裝載方案,并計(jì)算新方案對(duì)應(yīng)的目標(biāo)函數(shù)值Zn;當(dāng)n=ND時(shí),轉(zhuǎn)Step 6.

Step 5若Zn＞ZM令ZM=Zn,若Zn＜ZM則ZM不變,若Zn=ZM時(shí)令p=p+1;轉(zhuǎn)Step 4.

Step 6將ZM對(duì)應(yīng)的裝載方案作為最終方案輸出.

4 實(shí)例分析

假設(shè)某公司在當(dāng)前獲得了從8點(diǎn)至17點(diǎn)時(shí)段內(nèi)8批次貨物到達(dá)信息,且隨時(shí)間的推移允許對(duì)時(shí)段內(nèi)的到貨信息進(jìn)行更改;根據(jù)貨物到達(dá)時(shí)間分布,將全部批次作業(yè)分為3個(gè)階段,各階段及批次包含的物品及相應(yīng)的時(shí)間信息如表1所示;箱子和物品的類數(shù)及體積以隨機(jī)方式生成:以[1,3]和[1,5]間隨機(jī)生成的整數(shù)分別作為箱子和物品的類數(shù),以[2,10]和[100,600]隨機(jī)生成整數(shù)分別表示物品和箱子的容積(結(jié)果如表2所示);設(shè)有足夠多的箱子可供使用,要求制定時(shí)段內(nèi)的裝箱計(jì)劃使總成本最小.

表1 各裝箱貨物數(shù)量與到達(dá)、交付時(shí)間信息Table 1 The items'amount and arriving and delivering time

表2 物品及箱子體積Table 2 The sizes of items and bins

針對(duì)上述問(wèn)題,先設(shè)定相關(guān)作業(yè)參數(shù),如表3所示.再結(jié)合2.2中提到的三種信息條件下的模型,使用Delphi實(shí)現(xiàn)有關(guān)算法(HCA),在配置為英特爾2.9G雙核處理器、2G內(nèi)存電腦上運(yùn)行,可較快計(jì)算出三種方式下的結(jié)果(如表4所示):第一種是靜態(tài)信息條件,即為各個(gè)階段獨(dú)立制定裝箱計(jì)劃,計(jì)劃時(shí)只掌握本階段物品信息;第二種為理想信息條件,即計(jì)劃時(shí)已獲悉三個(gè)階段物品信息,將三階段結(jié)合到一起統(tǒng)一計(jì)劃;第三種屬于信息可實(shí)時(shí)更新的情況,它基于已有信息并通過(guò)引入權(quán)重α以滾動(dòng)的形式制定出當(dāng)前包含多階段的整體裝箱計(jì)劃.

從計(jì)算結(jié)果中可看出,基于完全信息的整體優(yōu)化求得的解,比基于靜態(tài)信息且各階段單獨(dú)計(jì)劃產(chǎn)生的解要好,這與實(shí)際情況相符合,而單獨(dú)計(jì)劃解的質(zhì)量與階段的劃分有關(guān);實(shí)時(shí)信息下制定多階段計(jì)劃可使用不同的權(quán)重α(α=0.3,α=0.6),即權(quán)重序列(1,α,α2,…,αK)對(duì)應(yīng)不同的值,可得到不同的計(jì)算結(jié)果.α反映到達(dá)物品波動(dòng)變化程度,它通過(guò)影響有可能進(jìn)行階段轉(zhuǎn)移和裝載的物品產(chǎn)生相應(yīng)的作用,取值越大對(duì)波動(dòng)越不敏感,而完全信息條件可視其為1.

由于涉及多個(gè)階段裝箱問(wèn)題的研究甚少,相關(guān)實(shí)例及對(duì)比研究也比較缺乏,為了驗(yàn)證HCA算法的效果,結(jié)合文獻(xiàn)[3]設(shè)計(jì)的實(shí)例及其使用的馬爾科夫鏈-蒙特卡洛算法(MCMC)實(shí)施結(jié)果,進(jìn)一步針對(duì)單階段T-VS-BPP運(yùn)用本文方法來(lái)求解.為適應(yīng)對(duì)比需要,將算法中物品體積屬性改為重量形式;同時(shí)采取和文獻(xiàn)[3]相同的分布隨機(jī)生成物品重量及單位延遲成本,箱子的體積、處理時(shí)間和物品的數(shù)量、滯留成本等參數(shù)設(shè)置也與其相同,大箱子可用數(shù)為0.25 N,小箱子可用數(shù)為0.5 N;并將算法中的階段數(shù)Nj設(shè)為1.取20次運(yùn)行的平均值為最終計(jì)算結(jié)果,實(shí)驗(yàn)對(duì)比如表5所示.表5中列舉了6組不同數(shù)量的物品裝載的實(shí)驗(yàn)結(jié)果,分別包括目標(biāo)函數(shù)值、計(jì)算時(shí)間、大箱(RB)和小箱(RS)的使用比例.

表3 相關(guān)參數(shù)設(shè)定Table 3 The setting of parameters

表4 不同信息條件下的計(jì)算結(jié)果Table 4 The calculating results under different information conditions

表5 HCA算法單階段裝箱求解效果Table 5 Performance of HCA for a single phase problem

通過(guò)對(duì)比可以看出,兩種方法對(duì)應(yīng)的目標(biāo)函數(shù)值基本接近,但存在一定的差異,這主要和實(shí)驗(yàn)以隨機(jī)方式生成有關(guān)屬性參數(shù)有關(guān);在計(jì)算效率上HCA基本優(yōu)于MCMC,HCA所具有的自適應(yīng)貪婪搜索特性[6]可加快搜索進(jìn)程,特別是當(dāng)問(wèn)題規(guī)模較大時(shí)更為明顯;從大小箱子使用情況來(lái)分析,兩種方法都偏向使用大的箱子,而HCA尤為如此,這也與其搜索機(jī)制有關(guān).由于多階段問(wèn)題求解是在單階段問(wèn)題求解的基礎(chǔ)上,引入成本比較及迭代搜索過(guò)程來(lái)實(shí)現(xiàn)的,因而HCA在處理單階段問(wèn)題時(shí)的效果,可為其適應(yīng)復(fù)雜的多階段問(wèn)題的求解提供較好的基礎(chǔ).

5 研究結(jié)論

多階段帶時(shí)間約束的VS-BPP考慮動(dòng)態(tài)環(huán)境下變尺寸裝箱優(yōu)化問(wèn)題,本文將一般帶時(shí)間約束的VS-BPP置于多階段研究框架,提出了基于確定信息的靜態(tài)模型和基于滾動(dòng)更新信息的動(dòng)態(tài)模型;根據(jù)問(wèn)題的特點(diǎn)設(shè)計(jì)了基于BFD規(guī)則與迭代松弛定界法相結(jié)合的構(gòu)造算法進(jìn)行求解;經(jīng)實(shí)例運(yùn)算和分析,證明方法能有效地對(duì)這一復(fù)雜動(dòng)態(tài)問(wèn)題進(jìn)行求解.下一步可對(duì)訂單取消、緊急插單等動(dòng)態(tài)事件的作用機(jī)理進(jìn)行研究,尋求適應(yīng)動(dòng)態(tài)復(fù)雜條件下裝箱問(wèn)題的算法也可作進(jìn)一步拓展.

[1] Correia I,Gouveia L.Solving the variable size bin packing problem with discretized formulations[J].Computers and Operations Research,2006,35:2103-2113.

[2] Haouari M,Serairi M.Relaxations and exact solution of the variable sized bin packing problem[J].Comput Optim Appl,2011,48:345-368.

[3] Fazi S,Woensel T V.A stochastic variable size bin packing problem with time constraints[J].Working Papers Beta,2012(804):1-19..

[4] Yaman H,Sen A.Manufacturer's mixed pallet design problem[J].EuropeanJournalofOperational Research,2008,186:826-840.

[5] Polyakovskiy S,Hallah R M.An intelligent framework to on line bin packing[J],Lecture Notes in Computer Science,2011,6704:226-236.

[6] Crainic T G,Perboli G.Efficient lower bounds and heuristics for the variable cost and size bin packing problem[J].Computers&Operations Research,2011, 38:

1474-148 2.

Optimization of Multi-phase Variable Size Bin Packing Problem with Time Constraints

ZHU Xiang,LEI Ding-you,YOU Wei
(School of Traffic&Transport Engineering,Central South University,Changsha 410075,China)

The multi-phase variable size bin packing problem with time constraints originates from the variable size bin packing problem(VS-BPP)after being placed in dynamical environment.It requires formulating a proper schedule which can minimize the total bin and time cost through selecting the different bins to form a combination to packing items involving multi-phase and with tardiness date.It has complex and dynamical natures,and there have been a plenty of applications in reality.This paper investigates the VS-BPP with time constraints under the multi-phase framework.Then it develops a static model based on exacted information and a dynamic model with rolling updating.According to the characteristics of the problem,a heuristic constructive algorithm is presented integrating the best first decreasing rule and lower bounds technique.The numerical example demonstrates that the models and the algorithm perform well when solving the special bin packing problems.

logisticsengineering;dynamicoptimization;constructivealgorithm;VS-BPP; time constraints

U294.6

: A

U294.6

A

1009-6744(2013)04-0157-07

2013-03-04

2013-04-14錄用日期:2013-04-26

國(guó)家自然科學(xué)基金資助項(xiàng)目(70971140).

朱向(1976-),男,湖南長(zhǎng)沙人,博士生,講師.

*通訊作者:cszhuxiang@163.com