Packing

算法原理

针对在线三维装箱问题，设计了2种底层装箱逻辑和3种位置选择策略。其中，底层装箱逻辑注重于满足算法约束，位置选择策略注重于提升填充率。根据底层装箱逻辑和位置选择策略之间的不同组合，设计并实现了4种装箱算法。

1.约束

（1）在线算法实现

箱子按照随机顺序到达，先到达先摆放

（2）摆放顺序

箱子从内到外、从下向上摆放

（3）摆放姿势

根据箱子长宽高（l,w,h）的组合，共6种摆放姿势

（4）空间约束

箱子在容器空间内摆放，箱子在容器空间中不发生重叠

（5）物理规则

考虑重力，即箱子底部必须有支撑

不考虑稳定性，即不对箱子作力矩分析

2.底层装箱逻辑

（1）空间切割

1）初始

初始化空间列表，将容器本身视为一个空间并加入到空间列表中。

2）单个箱子的装箱流程

a.每当箱子到达时，根据箱子对应的6种长宽高组合，遍历空间列表，找出可装入该箱子的空间，同时记录放置姿势； b.根据位置选择策略，从可放入该箱子的所有空间中选择一个空间，按对应的放置姿势进行装箱； c.将箱子装入选中的空间后，根据箱子暴露出来的三个面将当前空间划分为三个子空间，并根据子空间大小从小到大排序加入空间列表； d.删除原空间。

3）结束标志

当空间列表中的所有空间均无法装入所有种类的箱子时，装箱结束。

（2）放置点+重叠检测+挪动

1）初始

初始化放置点列表，将容器的原点加入到放置点列表中。

2）单个箱子的装箱流程

a.每当箱子达到时，根据箱子对应的6种长宽高组合，遍历放置点列表，依次尝试将箱子放在放置点列表中的每一个放置点上，并根据已装入箱子的位置进行重叠检测，从而找出所有不会发生箱体重叠的放置点以及对应的放置姿势； b.根据位置选择策略，从不会发生箱体重叠的放置点中选择一个放置点，按对应的放置姿势进行装箱； c.在满足约束条件的前提下，尝试将箱子朝x、y、z三个方向进行挪动，最大程度减少箱子间的间隙； d.根据放置点和挪动结果，将箱子的三个顶点(0,0,h) 、(l,0,0)、 (0,w,0)加入到放置点列表中。 e.删除使用的放置点。

3）结束条件

当放置点列表中所有的放置点均无法放入箱子时，装箱结束。

3.位置选择策略

（1）降序最佳适应

在操作系统内存分配中，最佳适应算法从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。 基于以上思想，设计了降序最佳适应策略（仅与底层装箱逻辑中的“空间切割”方法兼容）。在该策略中，每当选择放置箱子的空间时，在可放入该箱子的空间中，优先选择体积最小的空间进行装箱。

（2）局部最佳适应

提出局部填充率的概念：在当前箱子加入之后，所有已装箱子的体积之和占当前已装箱子占用的最小长方体空间的比例即为局部填充率，其对应的计算公式如公式（1）所示。

其中，(x,y,z)为箱子的放置点坐标，(l,w,h)为箱子在对应放置姿势下的长、宽、高。 在局部最佳适应策略中，每当选择放置箱子的空间时，在可放入该箱子的空间中，优选选择放置后最小的空间进行装箱。 选择放置点的方法与选择空间类似，不再赘述。

（3）限制面约束

为了尽可能整齐地摆放箱子，即使得放置位置属于同一水平面或垂直面的箱子的形状尽可能相似，提出了限制面约束策略（仅与底层装箱逻辑中的“放置点+重叠检测+挪动”兼容）。 在该策略中，新增两个限制面约束，从而将三维装箱问题分治为一个维度。在2个限制面约束中，一个限制面与xOy平行，记为xy限制面，另一个限制面与yOz平行，记为yz限制面。在选择放置点时，应尽可能地满足两个限制面约束，即箱子以的长宽高组合在放置点放置后，的值小于xy限制面的 值， 的值小于yz限制面的 值。若在某次装箱中，现有的放置点均不满足两个限制面约束，则优先扩展yz限制面，再考虑扩展xy限制面。当yz限制面和xy限制面扩展为容器本身，即两个限制面约束等效于容器本身的约束时，便停止扩展。

4.装箱算法

（1）基于空间切割的降序最佳适应算法

使用的底层装箱逻辑：空间切割 使用的位置选择策略：降序最佳适应

分支：feature/space-division/best-fit

（2）基于空间切割的局部最佳适应算法

使用的底层装箱逻辑：空间切割 使用的位置选择策略：局部最佳适应

分支：feature/space-division/local-best-fit

（3）基于重叠检测的限制面约束算法

使用的底层装箱逻辑：放置点+重叠检测+挪动 使用的位置选择策略：限制面约束

分支：feature/overlap-detection/surface-constriction

（4）基于重叠检测的局部最佳适应算法

使用的底层装箱逻辑：放置点+重叠检测+挪动 使用的位置选择策略：局部最佳适应

分支：feature/overlap-detection/local-best-fit

5.代码运行说明

切换到算法对应的分支，运行main.py即可。

python版本要求：3.10及以上

定义容器大小

container = Container(length, width, height)

定义箱子的长、宽、高、数量（可连续定义多种箱子）

manager = BoxManager()
    .add_box_type(length1, width1, height1, number1)
    .add_box_type(length2, width2, height2, number2)
    .add_box_type(length3, width3, height3, number3)