【Python】实现二维装箱Bottom-Left算法及用人工蜂群算法改进

1 题目

将若干个矩形物品装进矩形箱子中，并且在装箱的过程中不允许将矩形物品斜着放，即平行于横坐标。一般来说求解的目标是最小化箱子的箱子数目或者是箱子空间占用率。

当该算法适用于矩阵存储时，求解的最优目标是箱子的最大化空间占用率。以下即是求解的过程

2 装箱算法

2.1 所有装箱算法

参考【A Thousand Ways to Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin Packing】

以下我将会介绍其中一种叫Bottom-Left装箱算法。算法过程就是，矩形从箱子的右上角开始进入，先尽可能向下移动，再向左移动，一直循环，直至不再移动。在以下算法过程中，以0-1背包问题的思路去实现，即某个矩形装进箱子，则flag相应为1，未装进的flag为0。输出单个箱子占用率。

2.2 Bottom-Left具体算法过程

初始化是，输入箱子大小[W,H]

再输入每一个矩形的长和宽

4 5

4 7

4 2

4 4

7 4

初始装箱顺序为：12345

第一步：装第一个矩形，从右上角进入，一直向下移动，然后移动一直向左移动，直到左下角。用一个列表记录装进箱子的矩阵。表示为【x,y,width,height】x和y使右上角坐标。该矩形的flag标记为1。

第二步：装第二个矩形，先将矩形放入右上角，再判断第二个矩形是否与箱子中的矩形是否相交（overlap函数）。如果相交，就不放进箱子，换下一个矩形，如果不相交，计算可向下移动的距离（downHAtPoint函数），向下移动，并更新矩形位置（Update_itemRP函数），最后计算可向左移动的距离（leftWAtPoint函数），向左移动，并更新位置，直至可移动距离为0。将第二个矩形最终位置信息【x,y,width,height】添加进列表。该矩形的flag标记未1。

第三步：剩下的矩形，和第二步一样。如果该矩形装不进箱子，就换下一个矩阵，继续装，直至遍历完所有箱子。

3 Python 实现

本算法实现中，只用了一个箱子。如果想要多个箱子来装，可以修改本人去掉注释的地方，启用下一个箱子。

3.1 main.py主函数

from tools import *
import random

#   BL（bottom-up left-justified）法求解二位装箱问题
#   @BetterBench
#   思想：首先将选中的物体放在箱子的右上角，然后尽量向下向左作连续移动，直到不能移动为止
# 输入参数
itemNum=30 #物品数目
AllItem=np.array([[random.randint(1, 5) for j in range(1, 3)] for i in range(1,itemNum+1)])  #随机生成30个物品，[width,height]
Bin=[10,10] #箱子宽度与高度
ran=list(range(itemNum))
random.shuffle(ran) #随机生成装箱序列

ansBXY=np.zeros((itemNum,3))  #[箱子编号，X坐标，Y坐标]
RPNXY=[];
BinNum=1;
flagItem=np.zeros(itemNum) #标记物品是否被装入箱子，0没有装入，1装入
# 开始装箱

for i in range(itemNum):
    if flagItem[ran[i]]==0:
        item=AllItem[ran[i],:]
        itemRP=Bin  #起点全部在箱子右上角顶点
        flagOL=overlap(item,AllItem,itemRP,RPNXY) #如果重合flagOL=1；反之flagOL=0
        if flagOL==0:
            itemRP=finalPos(item,AllItem,itemRP,RPNXY) #更新物品从当前位置向下向左移动后到最终位置后右上角顶点坐标
            RPNXY.append([ran[i],itemRP[0],itemRP[1]]) # 记录装进箱子的矩形【ID,width,height】
            flagItem[ran[i]]=1
# 启用第下一个箱子
# if list(flagItem).count(0)>0:
#     BinNum=BinNum+1
#     RPNXY=[]

输出哪些矩形被装进箱子

print(flagItem)

array([0., 0., 1., 1., 1., 0., 1., 0., 1., 1., 0., 0., 1., 1., 1., 1., 0., 0., 0., 1., 0., 0., 0., 0., 0., 0., 0., 0., 1., 0.])

计算箱子占用率

rect_area = 0
bin_area = Bin[0]*Bin[1]
for id in RPNXY:
  width,height = AllItem[id[0]]
  rect_area += width*height
print('占用率:{}'.format(rect_area/bin_area))

占用率:0.81

可视化装箱后的结果

import matplotlib.pyplot as plt
import matplotlib.patches as patches
import random
fig, ax = plt.subplots(1, 1)
ax1 = fig.gca()
for i in RPNXY:
    width,height = AllItem[i[0]]
    rx,ry = i[1],i[2]
    lx,ly = rx-width,ry-height
    plt.xlim((0, Bin[0]))
    plt.ylim((0, Bin[1]))
    color = "#"+''.join([random.choice('0123456789ABCDEF') for j in range(6)])
    rect = patches.Rectangle((lx, ly), width,height,linewidth=1, facecolor = color)
    ax1.add_patch(rect)
plt.show()

3.2 overlap函数

判断物品item在当前位置itemRP与箱子中其他物品是否有重合，如果有重合FlagOL=1，反之FlagOL=0。

# 输入item：   物品[宽度，高度]
# 输入Item：   各个物品[宽度，高度]
# 输入itemRP： 此时物品右上角顶点坐标[x,y]
# 输入RPNXY：  当前箱子中所有物品右上角顶点坐标数组
# 输出flagOL： 如果重合flagOL=1；反之flagOL=0
def overlap(item,Item,itemRP,RPNXY):
    flagOL=0  # 初始化不存在重合情况
    itemLBP=[itemRP[0]-item[0],itemRP[1]-item[1]] #左下角顶点坐标
    A = Rectangle(itemLBP[0],itemLBP[1],item[0],item[1])
    num=len(RPNXY) # 箱子中物品数目
    if num>0:
        for i in range(num):
            width=Item[RPNXY[i][0],0]  #Item(RPNXY(i,1),:)宽度
            height=Item[RPNXY[i][0],1]  #Item(RPNXY(i,1),:)高度
            LBPXY=[RPNXY[i][1]-width,RPNXY[i][2]-height]  #在箱子中的当前矩形Item(RPNXY(i,1),:)的左下角顶点坐标
            B = Rectangle(LBPXY[0],LBPXY[1],width,height)
            area=rectint(A,B)#计算物品A与B相交的面积
            #如果AB相交，则满足下列关系
            if area>0:
                flagOL=1
                break
    return flagOL

3.3 finalPos函数

计算一个新的矩形从当前位置向下向左移动后到最终位置后右上角顶点坐标

# 输入item：   物品[宽度，高度]
# 输入Item：   各个物品[宽度，高度]
# 输入itemRP： 此时物品右上角顶点坐标[x,y]
# 输入RPNXY：  当前箱子中所有物品右上角顶点坐标数组
# 输出finalRP：物品item在箱子内任意位置向下向左移动后到最终位置后右上角顶点坐标
def 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)and (leftW==0):
            finalRP=itemRP
            break
    return finalRP

3.4 downHAtPoint函数

使用downHAtPoint()函数可以计算在当前箱子中，矩形在当前位置可以下降的最大高度。

# 计算在当前箱子中，物品item在箱子内任意位置可以下降的最大高度
# 输入item：   物品[宽度，高度]
# 输入AllItem：   各个物品[宽度，高度]
# 输入itemRP： 此时物品右上角顶点坐标[x,y]
# 输入RPNXY：  当前箱子中所有物品右上角顶点坐标数组
# 输出downH：  物品item在箱子内任意位置可以下降的最大高度（如果能装入当前箱子，则downH为正数；如果不能装入当前箱子，则为负数）
def downHAtPoint(item,AllItem,itemRP,RPNXY):
    bottomLine=Point_Horizontal_Line(item,itemRP)  #物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
    RP_NUM=len(RPNXY) #箱子内物品数目
    if RP_NUM!=0:
        sRPNXY=np.array(sorted(list(RPNXY), key=lambda x:x[2],reverse=True))#将RPNXY按照Y坐标降序排列
        sRBPNXY=sRPNXY.copy()
        sRBPNXY[:,1]=sRPNXY[:,1]-AllItem[sRPNXY[:,0],0]  #将RPNXY按照Y坐标降序排列后的左上角顶点坐标

        topLine=np.concatenate((sRBPNXY[:,1:3],sRPNXY[:,1:3]),axis=1)  #物品按照Y坐标降序排列后，物品上端水平线段左右两端坐标[leftx,lefty,rightx,righty]
        # 逐个遍历sRPNXY中的物品
        alldownH=[]  # 储存所有满足相交条件的下降距离
        for i in range(RP_NUM):
            #判断两条水平线段经过竖直移动后是否会相交，flag=1相交，flag=0不相交
            #两条水平线段距离是多少，如果竖直移动后相交，HD为正数，反之为负数
            flag,HD=Horizontal_Lines_Intersect(bottomLine,topLine[i,:])
            if (flag==1) and (HD>=0):
                alldownH.append(HD)
        # 如果不存在满足相交条件的物品，则直接下降到箱子最底端
        if len(alldownH)==0:
            downH=itemRP[1]-item[1]
        else:  # 如果存在满足相交条件的物品，则下降距离为alldownH中的最小值
            downH=min(alldownH)
    else:
        downH=itemRP[1]-item[1]  #此时箱子没有物品，物品直接下降到箱子底端
    return downH

3.5 Update_itemRP函数

计算物品在箱子中从右上角下降downH又向左移动leftW后，右上角顶点的坐标

# 输入itemRP： 此时物品右上角顶点坐标[x,y]
# 输入downH：  物品item从右上角可以下降的最大高度
# 输入leftW：  物品item从右上角下降最大高度以后，可以向左移动的最大距离
# 输出itRPXY： 物品item在箱子中下降downH又向左移动leftW后，右上角顶点的坐标
def Update_itemRP(itemRP,downH,leftW):
    h=itemRP[1]-downH  #y坐标
    w=itemRP[0]-leftW   #x坐标
    return [w,h]

3.6 leftWAtPoint函数

计算在当前箱子中，物品item在箱子内任意位置可以向左移动的最大距离

# 输入item：   物品[宽度，高度]
# 输入Item：   各个物品[宽度，高度]
# 输入itemRP： 此时物品右上角顶点坐标[x,y]
# 输入RPNXY：  当前箱子中所有物品右上角顶点坐标数组
# 输出leftW：  物品item在箱子内任意位置可以向左移动的最大距离
def leftWAtPoint(item,Item,itemRP,RPNXY):
    leftLine=Point_Vertical_Line(item,itemRP)  #物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
    RP_NUM=len(RPNXY)#箱子内物品数目
    if RP_NUM!=0:
        sRPNXY=np.array(sorted(list(RPNXY), key=lambda x:x[0]))  #将RPNXY按照X坐标降序排列
        sRBPNXY=sRPNXY.copy()
        sRBPNXY[:,2]=sRPNXY[:,2]-Item[sRPNXY[:,0],1] #将RPNXY按照X坐标降序排列后的右下角顶点坐标
        rightLine=np.concatenate((sRPNXY[:,1:3],sRBPNXY[:,1:3]),axis=1)#物品按照X坐标降序排列后，右端线段上下两端坐标[topx,topy,bottomx,bottomy]
        #逐个遍历sRPNXY中的物品
        allLeftW=[]  #储存所有满足相交条件的左移距离
        for i in range(RP_NUM):
            #判断两条竖直线经过水平移动后是否会相交，flag=1相交，flag=0不相交
            #两条竖直线段距离是多少，如果平移动后相交，HD为正数，反之为负数
            flag,HD=Vertical_Lines_Intersect(leftLine,rightLine[i,:])
            if (flag==1) and (HD>=0):
                allLeftW.append(HD)
        # 如果不存在满足相交条件的物品，则直接移动箱子最左端
        if len(allLeftW)==0:
            leftW=itemRP[0]-item[0]
        else: #如果存在满足相交条件的物品，则左移距离为allLeftW中的最小值
            leftW=min(allLeftW)
    else:
        leftW=itemRP[0]-item[0]
    return leftW

3.7 其他小功能的函数

from matplotlib.pyplot import axis
import numpy as np
# 矩形类，[x,y,width,height]左下角坐标、长和宽
class Rectangle:
    def __init__(self, x, y,w,h):
      self.x = x
      self.y = y
      self.width = w
      self.height = h

def Horizontal_Lines_Intersect(line1,line2):
    # 判断两条水平线段经过竖直移动后是否会相交，如果相交，计算两条水平线段竖直距离是多少
    # 思路：分5种情况：1）左方不相交；2）左方相交；3）右方相交；4）右方不相交；5）line1完全包含line2
    # 输入line1：  第一条线段[x1,y1,x2,y2]
    # 输入line2：  第二条线段[x1,y1,x2,y2]
    # 输出flag：  判断两条水平线段经过竖直移动后是否会相交，flag=1相交，flag=0不相交
    # 输出HD：  两条竖直线段距离是多少，如果平移动后相交，HD为正数，反之为负数
    #第一种情况，line1完全在line2左方，即line1右端顶点x坐标小于等于line2左端顶点x坐标，且两条线段经过竖直移动后不会相交
    if line1[2]<=line2[0]:
        flag=0
        HD=line1[1]-line2[1]
    #第二种情况，line1在line2左方，即line1右端顶点x坐标大于line2左端顶点x坐标且小于等于且line2右端顶点x坐标，但两条线段经过竖直移动后会相交
    elif (line1[2]>line2[0]) and (line1[2]<=line2[0]):
        flag=1
        HD=line1[1]-line2[1]
    #第三种情况，line1在line2右方，即line1左端顶点x坐标大于等于line2左端顶点x坐标且小于且line2右端顶点x坐标，但两条线段经过竖直移动后会相交
    elif (line1[0]>=line2[0]) and (line1[0]<line2[2]):
        flag=1
        HD=line1[1]-line2[1]
    #第四种情况，line1完全在line2右方，即line1左端顶点x坐标大于等于line2右端顶点x坐标，且两条线段经过竖直移动后不会相交
    elif line1[0]>=line2[2]:
        flag=0
        HD=line1[1]-line2[1]
    #第五种情况，line1完全包含line2，即line1左端顶点x坐标小于等于line2左端顶点x坐标，
    #line1右端顶点x坐标大于等于line2右端顶点x坐标，且两条线段经过竖直移动后会相交
    else:
        flag=1
        HD=line1[1]-line2[1]
    return flag,HD

# 根据物品右上角顶点坐标和物品宽度和高度，求出物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
# 输入item：  物品[宽度，高度]
# 输入RPXY：物品右上角顶点坐标[x,y]
# 输出leftLine：  物品下端水平线段左右两端坐标[leftx,lefty,rightx,righty]
def Point_Horizontal_Line(item,RPXY):
    。。。
    return bottomLine

# 判断两条竖直线段经过水平移动后是否会相交，如果相交，计算两条竖直线段水平距离是多少
# 思路：分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为正数，反之为负数
def Vertical_Lines_Intersect(line1,line2):
    # 第一种情况，line1完全在line2上方，且两条线段经过平移后不会相交
    if line1[3]>=line2[1]:
        flag=0
        HD=line1[0]-line2[0]
    # 第二种情况，line1在line2上方，但两条线段经过平移后会相交
    elif (line1[3]<line2[1])and (line1[3]>=line2[3]):
        flag=1
        HD=line1[0]-line2[0]
    # 第三种情况，line1在line2下方，但两条线段经过平移后会相交
    elif (line1[1]<=line2[1]) and (line1[1]>line2[3]):
        flag=1
        HD=line1[0]-line2[0]
    # 第四种情况，line1完全在line2下方，且两条线段经过平移后不会相交
    elif line1[1]<=line2[3]:
        flag=0
        HD=line1[0]-line2[0]
    else:
        flag=1
        HD=line1[0]-line2[0]
    return flag,HD

# 根据物品右上角顶点坐标和物品宽度和高度，求出物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
# 输入item：  物品[宽度，高度]
# 输入RPXY：物品右上角顶点坐标[x,y]
# 输出leftLine：  物品左端竖直线段上下两端坐标[topx,topy,bottomx,bottomy]
def Point_Vertical_Line(item,RPXY):
  。。。

# 计算两个矩形相交的面积，和MATLAB中rectint函数作用一样
def rectint(rect1, rect2):
    xl1, yb1, xr1, yt1 = rect1.x,rect1.y,rect1.x+rect1.width,rect1.y+rect1.height # （xl1, yb1）为矩形左下角坐标， （xr1, yt1）为右上角坐标
    xl2, yb2, xr2, yt2 = rect2.x,rect2.y,rect2.x+rect2.width,rect2.y+rect2.height # （xl2, yb2）为矩形左下角坐标， （xr2, yt2）为右上角坐标
    xmin = max(xl1, xl2)
    ymin = max(yb1, yb2)
    xmax = min(xr1, xr2)
    ymax = min(yt1, yt2)
    width = xmax - xmin
    height = ymax - ymin
    if width <= 0 or height <= 0:
        return 0
    cross_square = width * height
    return cross_square

4 缺点及改进

装箱顺序会影响占用率。比如会存在如下所示的装箱方案，物品4应该放置到物品2的上面。可以通过调整装箱顺序，让4和2调换一下装箱顺序，就可以达到更好的效果。

当矩阵数量庞大的时候，可以采用优化算法，来搜索最佳的排列组合，达到最大占用率。比如以人工蜂群算法实现。

import numpy as np
import random, math, copy
import matplotlib.pyplot as plt
from tools import *
import random


def fitness(Bin,AllItem,ran):
    # ran 是装箱顺序
    itemNum=AllItem.shape[0] #物品数目
    RPNXY=[];
    flagItem=np.zeros(itemNum) #标记物品是否被装入箱子，0没有装入，1装入
    # 开始装箱

    for i in range(itemNum):
        if flagItem[ran[i]]==0:
            item=AllItem[ran[i],:]
            itemRP=Bin  #起点全部在箱子右上角顶点
            flagOL=overlap(item,AllItem,itemRP,RPNXY) #如果重合flagOL=1；反之flagOL=0
            if flagOL==0:
                itemRP=finalPos(item,AllItem,itemRP,RPNXY) #更新物品从当前位置向下向左移动后到最终位置后右上角顶点坐标
                if len(itemRP)>0:
                    RPNXY.append([ran[i],itemRP[0],itemRP[1]])
                    flagItem[ran[i]]=1
    rect_area = 0
    bin_area = Bin[0]*Bin[1]
    for id in RPNXY:
        width,height = AllItem[id[0]]
        rect_area += width*height
    score = rect_area/bin_area
    print('利用率:{}'.format(score))
    return score

class ABSIndividual:
    def __init__(self,bin,item):
        self.score = 0.
        self.invalidCount = 0                      #无效次数（成绩没有更新的累积次数）
        self.bin = bin  #箱子宽度与高度
        self.allitem = item
        self.ran =  list(range(self.allitem.shape[0]))# 装箱顺序
        self.calculateFitness()        

    def calculateFitness(self):
        self.score = fitness(self.bin,self.allitem,self.ran)          #计算当前成绩

class ArtificialBeeSwarm:
    def __init__(self, foodCount, onlookerCount,Bin, item, maxIterCount=1000, maxInvalidCount=200):
        self.foodCount = foodCount                  #蜜源个数，等同于雇佣蜂数目
        self.onlookerCount = onlookerCount          #观察蜂个数 
        self.item = item                          #各参数上下界
        self.maxIterCount = maxIterCount            #迭代次数
        self.maxInvalidCount = maxInvalidCount      #最大无效次数
        self.Bin = Bin
        self.foodList = [ABSIndividual(self.Bin,self.item) for k in range(self.foodCount)]   #初始化各蜜源
        self.foodScore = [d.score for d in self.foodList]                             #各蜜源最佳成绩
        self.bestFood = self.foodList[np.argmax(self.foodScore)]                      #全局最佳蜜源

    def updateFood(self, i):                                                  #更新第i个蜜源
        vi = copy.deepcopy(self.foodList[i])
        order =list(range(vi.allitem.shape[0]))
        random.shuffle(order) #随机生成装箱序列
        vi.ran = order
        vi.calculateFitness()
        if vi.score > self.foodList[i].score:           #如果成绩比当前蜜源好
            self.foodList[i] = vi
            if vi.score > self.foodScore[i]:            #如果成绩比历史成绩好（如重新初始化，当前成绩可能低于历史成绩）
                self.foodScore[i] = vi.score
                if vi.score > self.bestFood.score:      #如果成绩全局最优
                    self.bestFood = vi
            self.foodList[i].invalidCount = 0
        else:
            self.foodList[i].invalidCount += 1

    def employedBeePhase(self):
        for i in range(0, self.foodCount):              #各蜜源依次更新
            self.updateFood(i)            

    def onlookerBeePhase(self):
        foodScore = [d.score for d in self.foodList]  
        maxScore = np.max(foodScore)        
        accuFitness = [(0.9*d/maxScore+0.1, k) for k,d in enumerate(foodScore)]        #得到各蜜源的 相对分数和索引号
        for k in range(0, self.onlookerCount):
            i = random.choice([d[1] for d in accuFitness if d[0] >= random.random()])  #随机从相对分数大于随机门限的蜜源中选择跟随
            self.updateFood(i)

    def scoutBeePhase(self):
        for i in range(0, self.foodCount):
            if self.foodList[i].invalidCount > self.maxInvalidCount:                    #如果该蜜源没有更新的次数超过指定门限，则重新初始化
                self.foodList[i] = ABSIndividual(self.bound)
                self.foodScore[i] = max(self.foodScore[i], self.foodList[i].score)

    def solve(self):
        trace = []
        trace.append((self.bestFood.score, np.mean(self.foodScore)))
        for k in range(self.maxIterCount):
            self.employedBeePhase()
            self.onlookerBeePhase()
            self.scoutBeePhase()
            trace.append((self.bestFood.score, np.mean(self.foodScore)))
        print(self.bestFood.score)
        self.printResult(np.array(trace))

    def printResult(self, trace):
        x = np.arange(0, trace.shape[0])
        plt.plot(x, [(1-d)/d for d in trace[:, 0]], 'r', label='optimal value')
        plt.plot(x, [(1-d)/d for d in trace[:, 1]], 'g', label='average value')
        plt.xlabel("Iteration")
        plt.ylabel("function value")
        plt.title("Artificial Bee Swarm algorithm for function optimization")
        plt.legend()
        plt.show()

if __name__ == "__main__":
    random.seed()
    itemNum = 1000
    AllItem=np.array([[random.randint(1, 5) for j in range(1, 3)] for i in range(1,itemNum+1)])  #随机生成30个物品，[width,height]
    Bin=[100,100] #箱子宽度与高度
    iternum = 100 # 迭代次数
    maxInvalidCount = 50
    abs = ArtificialBeeSwarm(30, 30, Bin,AllItem, iternum, maxInvalidCount)
    abs.solve()
    print()

5 完整代码下载

浏览器输入 betterbench.top/#/104/detail