三维装箱——启发式装箱策略

科技 2021-05-11 09:25

在之前的文章中

真的是小马啊，公众号：小马过河啊基于启发式方法的含多类型箱体的三维装箱问题求解

介绍了要解决的一类包含多类型箱体的三维装箱问题，以及基于遗传算法的求解框架（Xueping Li等人，2014）。文主要介绍解码过程——根据得到的物品序列（BPS）和容器序列（CLS）来得到具体的装箱方案。

1 最大剩余空间

首先介绍箱子最大剩余空间的概念（empty maximal spaces,EMSs）,它表示当前箱子在各方向上可放置物品的最大体积，如下图所示，其中蓝色立方体表示我们放入的物品占用的空间，黄色立方体表示各方向上我们可利用的最大空间。最大剩余空间可用两个角点的坐标来表示，左下角（具有最小的x,y,z）和右上角（具有最大的x,y,z）

最大剩余空间的概念另一方面，对于这些剩余空间，我们定义了它们的优先级便于在执行算法时进行选取。优先级的定义规则如下：对于两个最大剩余空间左下角坐标（）和（），首先分别取出两个坐标中某方向坐标值的最小值进行比较，若相同则取次小值，具有较小坐标值的剩余空间具有更高的优先级。假设两个坐标分别是剩余空间1（3，5，4）和剩余空间2（6，3，3），首先我们比较空间1最小值（3）和空间2最小值（3），由于二者相等，所以继续比较次小值4和3，此时发现空间二的值更小，所以空间二具有更高的优先级。这种设置优先级的原理是：我们把一个物品放入箱子时，首先应放到箱子的一个角上以及紧贴箱子的边上然后才考虑箱子的内部空间，这样有助于提高箱子的装载率。

2 摆放位置的选择

在之前的文章中介绍过，将一个物品放入箱子中时一共有六种摆放方式，如下图所示。

那么在实际装箱过程中，我们应该选择哪种方式呢？与最大剩余空间的优先级的确定方式类似，我们定义一种“边际长度”，箱子的长、宽、高分别是（L，W，H），物品在按照某种方式旋转放入后的长、宽、高分别是（l,w,h），那么某种放置方式的边际长度为（L-l,W-w,H-h），然后选取选具有最小边际长度的放置方式放置。以一个二维装箱的例子进行说明，比如物品有图a和图b两种放置方式，它们的边际长度分别是（1.75，1.45）和（3.25，0），那么此时我们就应该选择图b中的放置方式，因为0<1.45。

3 启发式装箱算法框架

输入：物品装箱顺序序列（BPS）和不同类型箱体的选择序列（CLS）

输出：装箱方案（物品摆放在哪种类型箱体的什么位置）若无可行解则返回NULL

BestMatchHeuristicPackingProcedure(BPS,CLS):Let OC be the list of opened containers0C=list()while BPS is not empty do:    Let P be priority queue of candidate placements    boxplaced=False    for each opend container c in OC do:        let EMSs be the empty maximal spaces in c        j=1        while j<=EMSs.size() and boxplaced=false do:            k=j+ke  #ke是按照优先级选出的最大剩余空间            while j<k and j<=EMSs.size() do                for i=1 to kb and i<=BPS.size() do:                    for all 6 orientations bo do:                        if Box BPS_i can be placed in EMSs_j with orientation bo then:                            Add this placement combination to P                j=j+1
            if P is not empty then:                Make the placement indicated by P1 (the first element of priority queue)                Update EMSs                boxplaced=True        if boxplaced=True then:            break    while CLS is not empty and boxplaced=False do:        let EMSs be the initial empty space in CLS1        OC.append(CLS1)        CLS.remove(CLS1)        for i=1 to kb and i<=BPS.size() do:            for all 6 orientations bo do:                if Box BPS_i can be placed in EMS with orientation bo then:                    add this placement combination to P        if P is not empty then:            Make the placement indicated by P1 (the first element of priority queue)            Update EMSs            boxplaced=True    if boxplaced=false then:        return nullreturn Packing solution

4 代码实现

对于启发式装箱方案的代码地址：https://github.com/Janet-19/3d-bin-packing-problem）。本次先对bin（箱子）这个类进行解读，箱子需要实现的基本功能包括:自身参数，当前装载物品的重量，箱子的满载率，其中decimal类用于保证数值在计算过程中精度不损失。

class Bin:    def __init__(self, size, length, width, height, capacity):        self.size = size         self.length = length        self.width = width        self.height = height        self.capacity = capacity        self.total_items = 0 # number of total items in one bin        self.items = [] # item in one bin -- a blank list initially        self.unplaced_items = []        self.unfitted_items = [] # unfitted item in one bin -- a blank list initially        self.number_of_decimals = DEFAULT_NUMBER_OF_DECIMALS        def format_numbers(self, number_of_decimals):        self.length = set_to_decimal(self.length, number_of_decimals)        self.height = set_to_decimal(self.height, number_of_decimals)        self.width = set_to_decimal(self.width, number_of_decimals)        self.capacity = set_to_decimal(self.capacity, number_of_decimals)        self.number_of_decimals = number_of_decimals        def get_volume(self):        return set_to_decimal(            self.length * self.height * self.width, self.number_of_decimals)         def get_total_weight(self):        total_weight = 0                for item in self.items:            total_weight += item.weight                return set_to_decimal(total_weight, self.number_of_decimals)        def get_filling_ratio(self):        total_filling_volume = 0        total_filling_ratio = 0                for item in self.items:            total_filling_volume += item.get_volume()                    total_filling_ratio = total_filling_volume / self.get_volume()        return set_to_decimal(total_filling_ratio, self.number_of_decimals)

此外箱子需要判断某个物品它的六种摆放方式，有哪些是可行的

def can_hold_item_with_rotation(self, item, pivot):         """Evaluate whether one item can be placed into bin with all optional orientations.        Args:            item: any item in item list.            pivot: an (x, y, z) coordinate, the back-lower-left corner of the item will be placed at the pivot.        Returns:            a list containing all optional orientations. If not, return an empty list.        """                fit = False         valid_item_position = [0, 0, 0]        item.position = pivot         rotation_type_list = []                         for i in range(0, len(RotationType.ALL)):             item.rotation_type = i             dimension = item.get_dimension()             if (                pivot[0] + dimension[0] <= self.length and  # x-axis                pivot[1] + dimension[1] <= self.width and  # y-axis                pivot[2] + dimension[2] <= self.height     # z-axis            ):                            fit = True                                for current_item_in_bin in self.items:                     if intersect(current_item_in_bin, item):                         fit = False                        item.position = [0, 0, 0]                        break                                 if fit:                     if self.get_total_weight() + item.weight > self.capacity: # estimate whether bin reaches its capacity                        fit = False                        item.position = [0, 0, 0]                        continue                                         else:                         rotation_type_list.append(item.rotation_type)                         else:                continue                 return rotation_type_list

以及有多种摆放方式可选时，按照之前设定的优先级判断将物品放入箱子中

def put_item(self, item, pivot, distance_3d):         """Evaluate whether an item can be placed into a certain bin with which orientation. If yes, perform put action.        Args:            item: any item in item list.            pivot: an (x, y, z) coordinate, the back-lower-left corner of the item will be placed at the pivot.            distance_3d: a 3D parameter to determine which orientation should be chosen.        Returns:            Boolean variable: False when an item couldn't be placed into the bin; True when an item could be placed and perform put action.        """                fit = False         rotation_type_list = self.can_hold_item_with_rotation(item, pivot)        margins_3d_list = []        margins_3d_list_temp = []        margin_3d = []        margin_2d = []        margin_1d = []                n = 0        m = 0        p = 0                if not rotation_type_list:            return fit                 else:            fit = True                         rotation_type_number = len(rotation_type_list)                        if rotation_type_number == 1:                 item.rotation_type = rotation_type_list[0]                 self.items.append(item)                self.total_items += 1                return fit                         else:                 for rotation in rotation_type_list:                     item.rotation_type = rotation                    dimension = item.get_dimension()                    margins_3d = [distance_3d[0] - dimension[0],                                  distance_3d[1] - dimension[1],                                  distance_3d[2] - dimension[2]]                    margins_3d_temp = sorted(margins_3d)                    margins_3d_list.append(margins_3d)                    margins_3d_list_temp.append(margins_3d_temp)                                while p < len(margins_3d_list_temp):                    margin_3d.append(margins_3d_list_temp[p][0])                    p += 1                                p = 0                while p < len(margins_3d_list_temp):                    if margins_3d_list_temp[p][0] == min(margin_3d):                        n += 1                        margin_2d.append(margins_3d_list_temp[p][1])                                        p += 1                                if n == 1:                    p = 0                    while p < len(margins_3d_list_temp):                        if margins_3d_list_temp[p][0] == min(margin_3d):                            item.rotation_type = rotation_type_list[p]                            self.items.append(item)                            self.total_items += 1                            return fit                                                 p += 1                                else:                    p = 0                    while p < len(margins_3d_list_temp):                        if (                            margins_3d_list_temp[p][0] == min(margin_3d) and                            margins_3d_list_temp[p][1] == min(margin_2d)                        ):                            m += 1                            margin_1d.append(margins_3d_list_temp[p][2])                                                p += 1                                if m == 1:                    p = 0                    while p < len(margins_3d_list_temp):                        if (                            margins_3d_list_temp[p][0] == min(margin_3d) and                            margins_3d_list_temp[p][1] == min(margin_2d)                        ):                            item.rotation_type = rotation_type_list[p]                            self.items.append(item)                            self.total_items += 1                            return fit                                                 p += 1                                else:                    p = 0                    while p < len(margins_3d_list_temp):                        if (                            margins_3d_list_temp[p][0] == min(margin_3d) and                            margins_3d_list_temp[p][1] == min(margin_2d) and                            margins_3d_list_temp[p][2] == min(margin_1d)                        ):                            item.rotation_type = rotation_type_list[p]                            self.items.append(item)                            self.total_items += 1                            return fit                                                 p += 1

以上就是bin这个类所需的方法，更详细的整个算法框架实现在后续进行介绍

http://mp.weixin.qq.com/s?__biz=MzU2Nzc4MTc3MQ==&mid=2247483778&idx=1&sn=3a7e8e44bdf2e6be3601d3006d9b5a15

小马过河啊

要好好学习呀!