二維裝箱問題之BL法修正版（附MATLAB程式碼）
01 | 問題匯入
二維裝箱問題顧名思義就是將若干個矩形物品裝進矩形箱子中，並且在裝箱的過程中
不允許將矩形物品斜著放
（PS：下圖就是不允許的裝箱操作），同時在裝箱過程中允許將物品旋轉90度放置（但是為了簡單地求解問題，
我們規定不允許將物品旋轉90度
），一般來說求解的目標是最小化箱子的使用數目。
02 | 演算法描述
BL法全稱是bottom-up left-justified，通俗點來說將一個要裝箱的物品1先
緊靠在箱子的右上角
，如下圖所示。
然後將物品1
向下移動
一直移動到再也不能向下移動為止，於是就如下圖所示。
在上圖基礎上，再將物品
向左移動
到再也不能移動為止，
然後再向下移動，然後再向左移動，……，一直到不能移動為止
，最終物品1就裝箱完成（PS：這個圖可能看不出來，案例解析中會充分體現這一思想）。
這一思想相信大家很快能理解，下面舉一個例子進行簡單的描述。
03 | 案例解析
比如說現在有若干個邊長為10的正方形箱子，有7個矩形物品，各個物品的寬度和高度如下：
寬度 高度
物品1： 5 6
物品2： 5 8
物品3： 4 1
物品4： 4 3
物品5： 9 3
物品6： 1 2
物品7： 5 4
箱子以及物品示意圖如下圖所示。
使用BL法將物品裝箱，首先要確定裝箱的順序，就上述7個要裝箱的物品來說，裝箱的順序可以是1234567，也可以是7654321，不一樣的裝箱順序可能會導致箱子使用數目的不同。
這裡為了簡單的描述上述案例，我們按照1234567的順序將物品裝箱。
1。裝物品1
2。裝物品2
3。裝物品3，注意這一步，
物品3在到達最左端後，還可以繼續向下降落
4。裝物品4，發現裝不進去
5。裝物品5，也裝不進去
6。裝物品6
7。裝物品7，發現物品7也不能裝進這個箱子
8。此時還有物品4、物品5和物品7沒有裝進箱子，於是新拿一個箱子先裝物品4，再裝物品5，最後裝物品7
上述就是使用BL法解決一個簡單的裝箱問題。
04 | 程式碼展示
在裝箱過程中，一個物品在箱子中任意位置
最大能下降多少距離
？
最多能向左移動多少距離？然後不斷地向下移動，向左移動，直到不能再移動為止
，這個物品即表示裝箱完成。
使用Horizontal_Lines_Intersect（）函式判斷兩條水平線段經過豎直移動後是否會相交，如果相交，計算兩條水平線段豎直距離是多少。
%% 判斷兩條水平線段經過豎直移動後是否會相交，如果相交，計算兩條水平線段豎直距離是多少
%思路：分5種情況：1）左方不相交；2）左方相交；3）右方相交；4）右方不相交；5）line1完全包含line2
% 輸入line1： 第一條線段［leftx，lefty，rightx，righty］
% 輸入line2： 第二條線段［leftx，lefty，rightx，righty］
% 輸出flag： 判斷兩條水平線段經過豎直移動後是否會相交，flag=1相交，flag=0不相交
% 輸出HD： 兩條豎直線段距離是多少，如果平移動後相交，HD為正數，反之為負數
function
［flag，HD］
=
Horizontal_Lines_Intersect
（
line1，line2
）
%第一種情況，line1完全在line2左方，即line1右端頂點x座標小於等於line2左端頂點x座標，且兩條線段經過豎直移動後不會相交
if
line1
（
3
）
<
=
line2
（
1
）
flag
=
0
；
HD
=
line1
（
2
）
-
line2
（
2
）；
%第二種情況，line1在line2左方，即line1右端頂點x座標大於line2左端頂點x座標且小於等於且line2右端頂點x座標，但兩條線段經過豎直移動後會相交
elseif
（
line1
（
3
）
>
line2
（
1
））
&&
（
line1
（
3
）
<
=
line2
（
3
））
flag
=
1
；
HD
=
line1
（
2
）
-
line2
（
2
）；
%第三種情況，line1在line2右方，即line1左端頂點x座標大於等於line2左端頂點x座標且小於且line2右端頂點x座標，但兩條線段經過豎直移動後會相交
elseif
（
line1
（
1
）
>
=
line2
（
1
））
&&
（
line1
（
1
）
<
line2
（
3
））
flag
=
1
；
HD
=
line1
（
2
）
-
line2
（
2
）；
%第四種情況，line1完全在line2右方，即line1左端頂點x座標大於等於line2右端頂點x座標，且兩條線段經過豎直移動後不會相交
elseif
line1
（
1
）
>
=
line2
（
3
）
flag
=
0
；
HD
=
line1
（
2
）
-
line2
（
2
）；
%第五種情況，line1完全包含line2，即line1左端頂點x座標小於等於line2左端頂點x座標，
%line1右端頂點x座標大於等於line2右端頂點x座標，且兩條線段經過豎直移動後會相交
% elseif （line1（1）<=line2（1））&&（line1（3）>=line2（3））
% flag=1；
% HD=line1（2）-line2（2）；
else
flag
=
1
；
HD
=
line1
（
2
）
-
line2
（
2
）；
end
end
使用Point_Horizontal_Line（）函式根據物品右上角頂點座標和物品寬度和高度，求出物品下端水平線段左右兩端座標［leftx，lefty，rightx，righty］。
%% 根據物品右上角頂點座標和物品寬度和高度，求出物品下端水平線段左右兩端座標［leftx，lefty，rightx，righty］
% 輸入item： 物品［寬度，高度］
% 輸入RPXY：物品右上角頂點座標［x，y］
% 輸出leftLine： 物品下端水平線段左右兩端座標［leftx，lefty，rightx，righty］
function
bottomLine
=
Point_Horizontal_Line
（
item，RPXY
）
RBPXY
=［
RPXY
（
1
），
RPXY
（
2
）
-
item
（
2
）］；
%物品右下角頂點座標
LBPXY
=［
RPXY
（
1
）
-
item
（
1
），
RPXY
（
2
）
-
item
（
2
）］；
%物品左下角頂點座標
bottomLine
=［
LBPXY
，
RBPXY
］；
end
使用downHAtPoint（）函式可以計算在當前箱子中，物品從箱子在箱子內
任意位置可以下降的最大高度。
%% 計算在當前箱子中，物品item在箱子內任意位置可以下降的最大高度
% 輸入item： 物品［寬度，高度］
% 輸入Item： 各個物品［寬度，高度］
% 輸入itemRP： 此時物品右上角頂點座標［x，y］
% 輸入RPNXY： 當前箱子中所有物品右上角頂點座標陣列
% 輸出downH： 物品item在箱子內任意位置可以下降的最大高度（如果能裝入當前箱子，則downH為正數；如果不能裝入當前箱子，則為負數）
function
downH
=
downHAtPoint
（
item，Item，itemRP，RPNXY
）
bottomLine
=
Point_Horizontal_Line
（
item
，
itemRP
）；
%物品下端水平線段左右兩端座標［leftx，lefty，rightx，righty］
RP_NUM
=
size
（
RPNXY
，
1
）；
%箱子內物品數目
if
RP_NUM
~=
0
sRPNXY
=
sortrows
（
RPNXY
，
3
，{
‘descend’
}）；
%將RPNXY按照Y座標降序排列
sRBPNXY
=
sRPNXY
；
sRBPNXY
（：，
2
）=
sRPNXY
（：，
2
）
-
Item
（
sRPNXY
（：，
1
），
1
）；
%將RPNXY按照Y座標降序排列後的左上角頂點座標
topLine
=［
sRBPNXY
（：，
2
：
3
），
sRPNXY
（：，
2
：
3
）］；
%物品按照Y座標降序排列後，物品上端水平線段左右兩端座標［leftx，lefty，rightx，righty］
%逐個遍歷sRPNXY中的物品
alldownH
=［］；
%儲存所有滿足相交條件的下降距離
for
i
=
1
：
RP_NUM
%判斷兩條水平線段經過豎直移動後是否會相交，flag=1相交，flag=0不相交
%兩條水平線段距離是多少，如果豎直移動後相交，HD為正數，反之為負數
［
flag
，
HD
］=
Horizontal_Lines_Intersect
（
bottomLine
，
topLine
（
i
，：））；
if
（
flag
==
1
）
&&
（
HD
>
=
0
）
alldownH
=［
alldownH
，
HD
］；
end
end
%如果不存在滿足相交條件的物品，則直接下降到箱子最底端
if
isempty
（
alldownH
）
downH
=
itemRP
（
2
）
-
item
（
2
）；
else
%如果存在滿足相交條件的物品，則下降距離為alldownH中的最小值
downH
=
min
（
alldownH
）；
end
else
downH
=
itemRP
（
2
）
-
item
（
2
）；
%此時箱子沒有物品，物品直接下降到箱子底端
end
end
使用Vertical_Lines_Intersect（）函式判斷兩條豎直線段經過水平移動後是否會相交，如果相交，計算兩條豎直線段水平距離是多少。
%% 判斷兩條豎直線段經過水平移動後是否會相交，如果相交，計算兩條豎直線段水平距離是多少
%思路：分5種情況：1）上方不相交；2）上方相交；3）下方相交；4）下方不相交；5）line1完全包含line2
% 輸入line1： 第一條線段［topx，topy，bottomx，bottomy］
% 輸入line2： 第二條線段［topx，topy，bottomx，bottomy］
% 輸出flag： 判斷兩條豎直線經過水平移動後是否會相交，flag=1相交，flag=0不相交
% 輸出HD： 兩條豎直線段距離是多少，如果平移動後相交，HD為正數，反之為負數
function
［flag，HD］
=
Vertical_Lines_Intersect
（
line1，line2
）
%第一種情況，line1完全在line2上方，且兩條線段經過平移後不會相交
if
line1
（
4
）
>
=
line2
（
2
）
flag
=
0
；
HD
=
line1
（
1
）
-
line2
（
1
）；
%第二種情況，line1在line2上方，但兩條線段經過平移後會相交
elseif
（
line1
（
4
）
<
line2
（
2
））
&&
（
line1
（
4
）
>
=
line2
（
4
））
flag
=
1
；
HD
=
line1
（
1
）
-
line2
（
1
）；
%第三種情況，line1在line2下方，但兩條線段經過平移後會相交
elseif
（
line1
（
2
）
<
=
line2
（
2
））
&&
（
line1
（
2
）
>
line2
（
4
））
flag
=
1
；
HD
=
line1
（
1
）
-
line2
（
1
）；
%第四種情況，line1完全在line2下方，且兩條線段經過平移後不會相交
elseif
line1
（
2
）
<
=
line2
（
4
）
flag
=
0
；
HD
=
line1
（
1
）
-
line2
（
1
）；
% elseif （line1（4）<=line2（4））&&（line1（2）>=line2（2））
% flag=1；
% HD=line1（1）-line2（1）；
else
flag
=
1
；
HD
=
line1
（
1
）
-
line2
（
1
）；
end
end
使用Point_Vertical_Line（）函式根據物品右上角頂點座標和物品寬度和高度，求出物品左端豎直線段上下兩端座標［topx，topy，bottomx，bottomy］。
%% 根據物品右上角頂點座標和物品寬度和高度，求出物品左端豎直線段上下兩端座標［topx，topy，bottomx，bottomy］
% 輸入item： 物品［寬度，高度］
% 輸入RPXY：物品右上角頂點座標［x，y］
% 輸出leftLine： 物品左端豎直線段上下兩端座標［topx，topy，bottomx，bottomy］
function
leftLine
=
Point_Vertical_Line
（
item，RPXY
）
LUPXY
=［
RPXY
（
1
）
-
item
（
1
），
RPXY
（
2
）］；
%物品左上角頂點座標
LBPXY
=［
RPXY
（
1
）
-
item
（
1
），
RPXY
（
2
）
-
item
（
2
）］；
%物品左下角頂點座標
leftLine
=［
LUPXY
，
LBPXY
］；
end
使用 leftWAtPoint（）函式計算在當前箱子中，物品在箱子內
任意位置
可以
向左移動的最大距離。
%% 計算在當前箱子中，物品item在箱子內任意位置可以向左移動的最大距離
% 輸入item： 物品［寬度，高度］
% 輸入Item： 各個物品［寬度，高度］
% 輸入itemRP： 此時物品右上角頂點座標［x，y］
% 輸入RPNXY： 當前箱子中所有物品右上角頂點座標陣列
% 輸出leftW： 物品item在箱子內任意位置可以向左移動的最大距離
function
leftW
=
leftWAtPoint
（
item，Item，itemRP，RPNXY
）
leftLine
=
Point_Vertical_Line
（
item
，
itemRP
）；
%物品左端豎直線段上下兩端座標［topx，topy，bottomx，bottomy］
RP_NUM
=
size
（
RPNXY
，
1
）；
%箱子內物品數目
if
RP_NUM
~=
0
sRPNXY
=
sortrows
（
RPNXY
，
2
，{
‘descend’
}）；
%將RPNXY按照X座標降序排列
sRBPNXY
=
sRPNXY
；
sRBPNXY
（：，
3
）=
sRPNXY
（：，
3
）
-
Item
（
sRPNXY
（：，
1
），
2
）；
%將RPNXY按照X座標降序排列後的右下角頂點座標
rightLine
=［
sRPNXY
（：，
2
：
3
），
sRBPNXY
（：，
2
：
3
）］；
%物品按照X座標降序排列後，右端線段上下兩端座標［topx，topy，bottomx，bottomy］
%逐個遍歷sRPNXY中的物品
allLeftW
=［］；
%儲存所有滿足相交條件的左移距離
for
i
=
1
：
RP_NUM
%判斷兩條豎直線經過水平移動後是否會相交，flag=1相交，flag=0不相交
%兩條豎直線段距離是多少，如果平移動後相交，HD為正數，反之為負數
［
flag
，
HD
］=
Vertical_Lines_Intersect
（
leftLine
，
rightLine
（
i
，：））；
if
（
flag
==
1
）
&&
（
HD
>
=
0
）
allLeftW
=［
allLeftW
，
HD
］；
end
end
%如果不存在滿足相交條件的物品，則直接移動箱子最左端
if
isempty
（
allLeftW
）
leftW
=
itemRP
（
1
）
-
item
（
1
）；
else
%如果存在滿足相交條件的物品，則左移距離為allLeftW中的最小值
leftW
=
min
（
allLeftW
）；
end
else
leftW
=
itemRP
（
1
）
-
item
（
1
）；
end
end
使用Update_itemRP（）函式計算物品在箱子中從當前位置itemRP下降downH又向左移動leftW後，
右上角頂點的座標
；
%% 計算物品在箱子中從右上角下降downH又向左移動leftW後，右上角頂點的座標
% 輸入itemRP： 此時物品右上角頂點座標［x，y］
% 輸入downH： 物品item從右上角可以下降的最大高度
% 輸入leftW： 物品item從右上角下降最大高度以後，可以向左移動的最大距離
% 輸出itRPXY： 物品item在箱子中下降downH又向左移動leftW後，右上角頂點的座標
function
itRPXY
=
Update_itemRP
（
itemRP，downH，leftW
）
itRPXY
=
zeros
（
1
，
2
）；
%儲存物品item在箱子中下降downH又向左移動leftW後，右上角頂點的座標
itRPXY
（
2
）=
itemRP
（
2
）
-
downH
；
%y座標
itRPXY
（
1
）=
itemRP
（
1
）
-
leftW
；
%x座標
end
使用finalPos（）函式計算物品在箱子中從右上角經過不斷地下降和左移以後，最終停止時右上角頂點的座標；
%% 計算物品從當前位置向下向左移動後到最終位置後右上角頂點座標
% 輸入item： 物品［寬度，高度］
% 輸入Item： 各個物品［寬度，高度］
% 輸入itemRP： 此時物品右上角頂點座標［x，y］
% 輸入RPNXY： 當前箱子中所有物品右上角頂點座標陣列
% 輸出finalRP：物品item在箱子內任意位置向下向左移動後到最終位置後右上角頂點座標
function
finalRP
=
finalPos
（
item，Item，itemRP，RPNXY
）
%當物品item不能再繼續下降或不能繼續左移的時候，跳出迴圈
while
1
downH
=
downHAtPoint
（
item
，
Item
，
itemRP
，
RPNXY
）；
%計算物品item在箱子內itemRP位置處可以下降的最大高度
leftW
=
0
；
itemRP
=
Update_itemRP
（
itemRP
，
downH
，
leftW
）；
%更新物品item當前位置右上角頂點座標
downH
=
0
；
leftW
=
leftWAtPoint
（
item
，
Item
，
itemRP
，
RPNXY
）；
%計算物品item在箱子內itemRP位置處可以向左移動的最大距離
itemRP
=
Update_itemRP
（
itemRP
，
downH
，
leftW
）；
%更新物品item當前位置右上角頂點座標
if
（
downH
==
0
）
&&
（
leftW
==
0
）
finalRP
=
itemRP
；
break
end
end
end
使用overlap（）函式判斷處於當前位置的物品在箱子中是否與其它物品有重合，有重合flagOL=1，反之flagOL=0
%% 計算物品從當前位置向下向左移動後到最終位置後右上角頂點座標
%% 判斷物品item在當前位置itemRP與箱子中其他物品是否有重合
% 輸入item： 物品［寬度，高度］
% 輸入Item： 各個物品［寬度，高度］
% 輸入itemRP： 此時物品右上角頂點座標［x，y］
% 輸入RPNXY： 當前箱子中所有物品右上角頂點座標陣列
% 輸出flagOL： 如果重合flagOL=1；反之flagOL=0
function
flagOL
=
overlap
（
item，Item，itemRP，RPNXY
）
flagOL
=
0
；
%初始化不存在重合情況
itemLBP
=［
itemRP
（
1
）
-
item
（
1
），
itemRP
（
2
）
-
item
（
2
）］；
%左下角頂點座標
A
=［
itemLBP
，
item
］；
num
=
size
（
RPNXY
，
1
）；
%箱子中物品數目
if
num
>
0
for
i
=
1
：
num
Sbx
=
Item
（
RPNXY
（
i
，
1
），
1
）；
%Item（RPNXY（i，1），：）寬度
Sby
=
Item
（
RPNXY
（
i
，
1
），
2
）；
%Item（RPNXY（i，1），：）高度
LBPXY
=［
RPNXY
（
i
，
2
）
-
Sbx
，
RPNXY
（
i
，
3
）
-
Sby
］；
%Item（RPNXY（i，1），：）的左下角頂點座標
B
=［
LBPXY
，
Sbx
，
Sby
］；
area
=
rectint
（
A
，
B
）；
%計算物品A與B相交的面積
%如果AB相交，則滿足下列關係
if
area
>
0
flagOL
=
1
；
break
end
end
end
end
最後是主函式，如果想要修改
箱子、物品的引數
可以修Bin變數和Item變數。如果不想改變
物品裝箱順序
，可以刪除ran變數。
%%
% BL（bottom-up left-justified）法求解二位裝箱問題
% @隨心390
% 思想：首先將選中的物體放在箱子的右上角，然後儘量向下向左作連續移動，直到不能移動為止
clear
clc
% load problem。mat Bin itemNum Item ran
%% 輸入引數
Bin
=［
10
，
10
］；
%箱子寬度與高度
itemNum
=
30
；
%物品數目
Item
=
ceil
（
0。5
*
Bin
（
1
）
*
rand
（
itemNum
，
2
））；
%隨機生成30個物品
ran
=
randperm
（
itemNum
）；
%隨機生成裝箱序列
ansBXY
=
zeros
（
itemNum
，
3
）；
%［箱子編號，X座標，Y座標］
RPNXY
=［］；
BinNum
=
1
；
flagItem
=
zeros
（
itemNum
，
1
）；
%標記物品是否被裝入箱子，0沒有裝入，1裝入
%% 開始裝箱
while
find
（
flagItem
==
0
）
figure
rectangle
（
‘position’
，［
0
，
0
，
Bin
（
1
），
Bin
（
2
）］）
%其中，x，y代表矩形左下角座標 w，h代表寬度、長度
axis
（［
0
Bin
（
1
）
0
Bin
（
2
）］）
for
i
=
1
：
itemNum
if
flagItem
（
ran
（
i
））
==
0
item
=
Item
（
ran
（
i
），：）；
itemRP
=
Bin
；
%起點全部在箱子右上角頂點
flagOL
=
overlap
（
item
，
Item
，
itemRP
，
RPNXY
）；
%如果重合flagOL=1；反之flagOL=0
if
flagOL
==
0
itemRP
=
finalPos
（
item
，
Item
，
itemRP
，
RPNXY
）；
%更新物品從當前位置向下向左移動後到最終位置後右上角頂點座標
if
~
isempty
（
itemRP
）
RPNXY
=［
RPNXY
；
ran
（
i
），
itemRP
］；
flagItem
（
ran
（
i
））=
1
；
ansBXY
（
ran
（
i
），
1
）=
BinNum
；
ansBXY
（
ran
（
i
），
2
）=
itemRP
（
1
）；
ansBXY
（
ran
（
i
），
3
）=
itemRP
（
2
）；
rectangle
（
‘position’
，［
ansBXY
（
ran
（
i
），
2
）
-
Item
（
ran
（
i
），
1
），
ansBXY
（
ran
（
i
），
3
）
-
Item
（
ran
（
i
），
2
），
。。。
Item
（
ran
（
i
），
1
），
Item
（
ran
（
i
），
2
）］，
‘FaceColor’
，［
0
0。4470
0。7410
］，
‘EdgeColor’
，
‘k’
）
%其中，x，y代表矩形左下角座標 w，h代表寬度、長度
text
（
ansBXY
（
ran
（
i
），
2
）
-
Item
（
ran
（
i
），
1
）
/
2
，
ansBXY
（
ran
（
i
），
3
）
-
Item
（
ran
（
i
），
2
）
/
2
，
num2str
（
ran
（
i
）））
end
end
end
end
if
find
（
flagItem
==
0
）
BinNum
=
BinNum
+
1
；
RPNXY
=［］；
else
break
end
end
05 | 演算法不足
畢竟是一個最基本的裝箱方法，所以效果可能不會很好。比如會存在如下所示的裝箱方案，很明顯物品4應該放置到物品2的上面。但是對基本的BL法來說，這是沒有辦法的。
因為物品4在箱子的右上角只能左移到物品3以上
，所以基本BL法還有很大改進空間，各位小夥伴可以嘗試改進一下。
各位小夥伴可以在微信公眾號後臺給小編留言，希望小編講解
某一個具體問題
，或者講解
某一個具體演算法
，或者
復現某一篇經典論文的演算法
，小編會盡力為各位解決問題。
點選此處提取程式碼，提取碼為
ffbu
。
往期精彩
更多資源請微信關注：最佳化演算法交流地