二維矩形條帶裝箱問題的離散化左下角定位模型

李 明,張曼曼 ,亓?xí)袁?,唐秋華

(1.武漢科技大學(xué)理學(xué)院,湖北 武漢，430065;2.武漢科技大學(xué)機械自動化學(xué)院,湖北 武漢，430081)

?

二維矩形條帶裝箱問題的離散化左下角定位模型

李 明,張曼曼 ,亓?xí)袁?,唐秋華

(1.武漢科技大學(xué)理學(xué)院,湖北 武漢，430065;2.武漢科技大學(xué)機械自動化學(xué)院,湖北 武漢，430081)

分別針對不旋轉(zhuǎn)和可旋轉(zhuǎn)兩種情況下的離散化二維矩形條帶裝箱問題(2DR-SPP)，采用各矩形的左下角坐標(biāo)對矩形的放置點進行定位，建立了兩個整數(shù)線性規(guī)劃模型。采用GAMS/CPLEX軟件對標(biāo)桿算例進行求解，驗證了所建模型的有效性和準確性。

二維裝箱問題;離散化；定位模型;整數(shù)規(guī)劃

二維矩形條帶裝箱問題(2D rectangular strip packing problem, 簡稱2DR-SPP)是指將給定的若干個矩形互不重疊地裝入給定寬度、長度無限的矩形條帶箱中，使得箱子被矩形所占用的長度最短。2DR-SPP是在板材切割、布料裁剪和木材加工等領(lǐng)域普遍存在的一個問題，對此問題的建模與求解有重要的理論研究價值。

目前，對2DR-SPP的研究主要集中于求解算法。Hifi[1]利用分支定界算法對中小規(guī)模2DR-SPP 進行了有效求解。Burke等[2]針對正交2DR-SPP，提出一種最優(yōu)匹配(best-fit)啟發(fā)式算法，根據(jù)當(dāng)前部分解的狀態(tài)選擇具有最佳適應(yīng)度的矩形放置解，此外該算法還在求解的不同階段運用不同的處理策略以減少求解時間。Chen等[3]提出一種雙階段啟發(fā)式搜索算法求解2DR-SPP，首先根據(jù)普通占角規(guī)則選擇放置位置，然后根據(jù)全局適應(yīng)度對其進行評價并選擇最佳位置。Cui等[4]將遞歸結(jié)構(gòu)和分支定界策略相結(jié)合，提出一種啟發(fā)式遞歸分支定界算法。張德富等[5]基于砌墻規(guī)則提出一種啟發(fā)式算法，可有效求解規(guī)模較大的算例。蔣興波等[6]首先提出一種含五種啟發(fā)式規(guī)則的底部左齊擇優(yōu)匹配算法，然后將此算法與遺傳算法相結(jié)合，得到了精度更高的解。Leung等[7]提出一種基于層的快速啟發(fā)式算法。彭碧濤等[8]提出一種迭代啟發(fā)式算法，采用矩形裝載適應(yīng)度計算規(guī)則和樹型迭代搜索規(guī)則，選擇最高適應(yīng)度的矩形置入箱內(nèi)。黃嵐等[9]將遺傳算法和離散粒子群算法相融合，提出一種混合算法求解矩形排樣問題。Chen等[10]提出一種融合了啟發(fā)式算法、局部搜索算法和demon算法的混合算法。此外，Yang等[11]還針對2DR-SPP提出了一種簡單的隨機搜索算法。

與求解算法相比，對2DR-SPP建模方面的研究較少。于洪霞等[12]針對不可旋轉(zhuǎn)2DR-SPP建立了非線性規(guī)劃理論模型。Castro等[13]基于矩形左下角端點坐標(biāo)建立了二維矩形裝箱問題的混合整數(shù)規(guī)劃模型，其借助一種特殊的連續(xù)輔助變量控制矩形的重疊行為，可有效求解矩形不旋轉(zhuǎn)情形下的2DR-SPP，而對可旋轉(zhuǎn)情形只是給出了問題的理論模型。

本文對文獻[13]中的模型進一步改進，針對不旋轉(zhuǎn)和可旋轉(zhuǎn)兩種情形建立2DR-SPP的純整數(shù)線性規(guī)劃模型，并借助GAMS/CPLEX軟件對標(biāo)桿算例進行求解，以檢驗所建模型的有效性和準確性。

1 問題描述

假設(shè)2DR-SPP中矩形的寬度和高度以及條帶箱的寬度值都為整數(shù)。記矩形的序號集合為I，I={i|i=1,…,|I|}，矩形i的高度和寬度分別為hi和li，條帶箱的寬度為L。

當(dāng)矩形要求以不旋轉(zhuǎn)方式分配至條帶箱中時，上述問題稱為不旋轉(zhuǎn)2DR-SPP。此時由于矩形的高度和寬度固定，且放置方式唯一，故矩形所占條帶箱的行和列位置可由其左下角單元位置唯一確定，由此所建立的數(shù)學(xué)模型稱為2DR-SPP的離散化不旋轉(zhuǎn)左下角定位模型。

2 離散化不旋轉(zhuǎn)左下角定位模型

定義0-1決策變量xijk和輔助變量zijk(i∈I,j∈J,k∈K)，其中當(dāng)矩形i的左下角單元占用箱子的單元(j,k)時xijk=1，否則xijk=0；當(dāng)矩形i占用箱子的單元(j,k)時zijk=1，否則zijk=0。

對于矩形i，由于其列數(shù)(或行數(shù))為li(或hi)，所以其左下角單元不能被置于箱子的第L-li+2,…,L列和第|J|-hi+2,…,|J|行，否則該矩形將從列或行的方向溢出箱子(列溢出情形見圖1)，所以要滿足

xijk=0,?i∈I,(j,k)∈(Ω-Ωi)

(1)

式中：Ω={(j,k)|j∈J,k∈K}為箱子的單元區(qū)域，Ωi={(j,k)|j≤|J|-hi+1,k≤L-li+1,j∈J,k∈K}為矩形i左下角單元的可放置區(qū)域。

圖1 矩形列溢出和未溢出兩種情形示例

Fig.1 Two examples with and without rectangle columnoverflow

矩形i的左下角單元在其可放置區(qū)域Ωi中必須且僅占有一個單元，即要滿足

,?i∈I

(2)

約束條件式(1)和式(2)可保證任意一個矩形i的左下角單元(j,k)占且僅占用其可放置區(qū)域Ωi的一個單元，并保證矩形的所有單元不會溢出箱子。下面利用另一變量zijk保證各矩形的所有單元都被不重疊地置于箱子中。

圖2 矩形左下角單元和其它單元的關(guān)系示意圖

Fig.2 Relationship between left bottom corner and the other elements of a rectangle

(3)

約束條件式(3)可保證矩形i的所有單元都被置于箱子中，但無法保證箱子的某個單元被多個矩形占用。

為了防止矩形的單元在條帶箱中發(fā)生重疊，即防止箱子中存在單元格被至少2個或以上矩形占用，增加以下約束：

≤1,?j∈J，k∈K

(4)

引入變量N表示箱子被矩形占用的行數(shù)，對目標(biāo)線性化得式(5)和式(6)。

min N

(5)

(6)

此外，由于所有矩形都必須被置入箱內(nèi)，所以根據(jù)所有矩形的單元總數(shù)和箱子列數(shù)的關(guān)系，可得箱子所需的最小單元行數(shù)，即理論最優(yōu)值為：

此理論最優(yōu)值可為優(yōu)化目標(biāo)中的最小行數(shù)N進行定界，以減小問題的可行解空間，即有

N≥N1

(7)

3 離散化可旋轉(zhuǎn)左下角定位模型

當(dāng)矩形可旋轉(zhuǎn)放置時，它所占條帶箱的行數(shù)和列數(shù)不僅取決于該矩形的高度和寬度，也取決于其放置方式，即不旋轉(zhuǎn)放置還是旋轉(zhuǎn)90°放置。

在已有0-1變量xijk的基礎(chǔ)上，增加新的0-1變量yi(i∈I)，定義yi=1表示矩形i不旋轉(zhuǎn)放置，yi=0表示矩形旋轉(zhuǎn)90°放置。

xijk≤(1-yi),?i∈I，(j,k)∈(Ω-Ωi)

(8)

(9)

,?i∈I

(10)

對條帶箱的任意一個單元(j,k)，約束式(11)可保證所裝的矩形不會發(fā)生重疊。

≤1,?j∈J，k∈K

(11)

綜合考慮兩種情形可建立相應(yīng)約束如下：

zij′k′≥xijk-(1-yi),

(12)

zij*k*≥xijk-yi,

(13)

基于式(5)和式(6)，構(gòu)建可旋轉(zhuǎn)情形下二維矩形條帶裝箱問題的優(yōu)化目標(biāo)如下：

min N

(14)

?i∈I

(15)

此外，當(dāng)矩形i的行數(shù)hi超出箱子的列數(shù)L時，必須不旋轉(zhuǎn)放置，即yi=1 ，于是有

≤yi

(16)

而當(dāng)矩形i的列數(shù)li超出箱子的列數(shù)L時，則必須旋轉(zhuǎn)放置，即yi=0，相應(yīng)要滿足

≤1-yi

(17)

4 算例

為了檢驗所建模型的準確性和有效性，將兩個模型分別應(yīng)用于文獻[13]中一個中等規(guī)模的標(biāo)桿算例Ex5，采用GAMS/CPLEX軟件進行求解，并將所得結(jié)果與文獻[13]所建模型的求解結(jié)果進行比較。標(biāo)桿算例Ex5所含矩形個數(shù)為21，條帶箱列數(shù)為10，各矩形的高度和寬度見表1。

表1 標(biāo)桿算例中各矩形的高度和寬度

Table 1 Height and width of each rectangle in the example

矩形序號高度寬度115222332427551666751084393210951142矩形序號高度寬度1211132314311526162217121821192120112111

標(biāo)桿算例求解結(jié)果見表2，由模型(Ⅰ)和模型(Ⅱ)的計算結(jié)果得到的矩形鋪設(shè)方案見圖3。

表2 標(biāo)桿算例的計算結(jié)果

(a)模型(Ⅰ)(不旋轉(zhuǎn)) (b)模型(Ⅱ)(可旋轉(zhuǎn))

圖3 模型(Ⅰ)和模型(Ⅱ)求解標(biāo)桿算例的最優(yōu)布局方案

Fig.3 Optimal layout schemes of benchmark example solved by Model(Ⅰ) and Model(Ⅱ)

由表2和圖3可見，所建離散化不旋轉(zhuǎn)和可旋轉(zhuǎn)的左下角定位模型均可有效求解出標(biāo)桿算例的最優(yōu)解；可旋轉(zhuǎn)情形下的最優(yōu)解要優(yōu)于不旋轉(zhuǎn)情形下的最優(yōu)解(包含文獻[13]模型和本文模型(Ⅰ)的計算結(jié)果)。

5 結(jié)語

本文針對離散化二維矩形條帶裝箱問題，利用各矩形的左下角單元坐標(biāo)對矩形在條帶箱中的放置位置進行定位，就不旋轉(zhuǎn)和可旋轉(zhuǎn)兩種情形分別建立了該問題的純整數(shù)線性規(guī)劃模型。對標(biāo)桿算例的求解結(jié)果驗證了兩個模型的有效性和準確性。

然而，所建兩個模型只能求解出部分中小規(guī)模問題的最優(yōu)解，對于大規(guī)模問題還應(yīng)進一步研究啟發(fā)式或元啟發(fā)式求解算法。

[1] Hifi M. Exact algorithms for the guillotine strip cutting/packing problem[J]. Computers and Operations Research, 1998, 25(11): 925-940.

[2] Burke E K, Kendall G, Whitwell G. A new placement heuristic for the orthogonal stock-cutting problem[J]. Operations Research, 2004, 52(4):655-671.

[3] Chen Mao, Huang Wenqi. A two-level search algorithm for 2D rectangular packing problem[J]. Computers and Industrial Engineering, 2007, 53(1):123-136.

[4] Cui Yaodong, Yang Yuli, Cheng Xian, et al. A recursive branch-and-bound algorithm for the rectangular guillotine strip packing problem[J]. Computers and Operations Research, 2008, 35(4): 1281-1291.

[5] 張德富,韓水華,葉衛(wèi)國. 求解矩形Packing問題的砌墻式啟發(fā)式算法[J]. 計算機學(xué)報, 2008, 31(3)：509-515.

[6] 蔣興波,呂肖慶,劉成城.二維矩形條帶裝箱問題的底部左齊擇優(yōu)匹配算法[J]. 軟件學(xué)報, 2009, 20(6)：1528-1538.

[7] Leung S C H, Zhang Defu. A fast layer-based heuristic for non-guillotine strip packing[J]. Expert Systems with Applications, 2011,38(10): 13032-13042.

[8] 彭碧濤，周永務(wù). 求解2D條帶矩形Packing問題的迭代啟發(fā)式算法[J]. 軟件學(xué)報, 2012, 23(10)：2600-2610.

[9] 黃嵐，齊季，譚穎，等. 一種求解矩形排樣問題的遺傳-離散粒子群優(yōu)化算法[J]. 電子學(xué)報, 2012, 40(6)：1103-1107.

[10]Chen Bili, Wang Yong, Yang Shuangyuan. A hybrid demon algorithm for the two-dimensional orthogonal strip packing problem[J]. Mathematical Problems in Engineering,2015(3):1-14.

[11]Yang Shuangyuan, Han Shuihua, Ye Weiguo. A simple randomized algorithm for two-dimensional strip packing[J]. Computers and Operations Research, 2013, 40(1):1-8.

[12]于洪霞，張紹武，張立衛(wèi). 二維裝箱問題非線性規(guī)劃模型和算法[J]. 大連理工大學(xué)學(xué)報, 2008, 48(2)：308-312.

[13]Castro P M, Oliveira J F. Scheduling inspired models for two-dimensional packing problems[J]. European Journal of Operational Research, 2011, 215(1):45-56.

[責(zé)任編輯 尚 晶]

Discrete-space locating model with left bottom corner coordinate for 2D rectangular strip packing problem

LiMing1,ZhangManman1,QiXiaoying1,TangQiuhua2

(1.College of Science, Wuhan University of Science and Technology, Wuhan 430065, China;2. College of Machinery and Automation, Wuhan University of Science and Technology, Wuhan 430081, China)

To solve the discrete 2D rectangular strip packing problem (2DR-SPP) with non-rotating rectangles and rotatable ones respectively, two integer linear programming models are established which locate every rectangle according to its left bottom corner coordinate. The proposed models are employed to solve a benchmark example by GAMS/CPLEX software and the results demonstrate their effectiveness and accuracy.

two-dimensional packing problem; discretization; location model; integer programming

2016-08-28

湖北省教育廳科學(xué)技術(shù)研究項目(D20161104).

李 明(1976-)，男，武漢科技大學(xué)副教授，博士. E-mail:lmzqx@163.com

TP18;TP301

A

1674-3644(2016)06-0468-04