Python实现的可定制策略拟人式三维装箱算法源码+文档说明

# 可变策略的拟人式三维装箱算法实现 ## 问题 给定一个长方体容器和较多不同形态的长方体货物，需确定装箱策略，使货物尽可能多地装填到容器中。 ### 假设与约束 1. 货物可向上码放； 2. 货物必须完全包含在容器中； 3. 任意两个货物内的任意一点不可在空间中的同一位置； 4. 货物不可悬空放置，即货物下方必须有其他货物或容器底部支撑； 5. 货物与容器平行放置，即货物的边与容器的对应边平行； 6. 货物各个面都可以朝下放置，没有上下左右前后的区别。 ### 输入输出 输入为**容器**的**长宽高**数据和**货物**的**数量**及其**各自的长宽高**数据。 输出为以下三项： 1. 容器最终的利用率； 2. 容器中各个货物的位置和形态数据； 3. 结果示意图。 其中，设容器的容积为$V$，共有$n$个货物，第$i$个货物的体积为$s_j$，利用率$\eta$的计算方式为： $$ \eta = \frac{\sum_{i=1}^{n}s_i}{V}. $$ ## 程序目标与问题分析 程序需要在满足假设和约束条件的情况下，尽可能提高$\eta$的值。经分析不难发现，利用率的高低取决于以下三个方面： 1. **货物装载的顺序**； 2. **货物装载的位置**； 3. **货物摆放的方式**。 所谓装载策略，指的是分别说明上述三个方面的子算法。在本文中，**可变策略的**是指本算法仅确定货物装载位置的算法--**拟人式算法**，其他两个方面由算法复用者自行编写或使用遗传算法、模拟退火等启发式算法探索。当然，可变策略的算法设计也会给具体的程序编码设计带来一定的麻烦。 ### 装载顺序 装载顺序对最终的利用率影响很大。在其他策略一定的情况下，不同的装载顺序会的到不同的结果。假设一个简单的情况，有一空间有限的容器，有一大一小两种货物。如果先装载大货物，再装载小货物，可能的一种情况是：在大货物的空隙间填充入小货物，然后得到较高的利用率。反之，如果先装小货物，可能的一种情况是：装完小货物后的剩余空间的尺寸无法满足将大货物装入，利用率低。 ### 装载位置 在其他策略一定的情况下，不同装载位置也会有不同的结果。这个是显而易见的，可以通过调整小货物的位置提高利用率。再次考察“装载顺序”一节中先装小货物的情况，将平铺于底面的货物堆码起来放置，腾出放入大货物的空间，提高了利用率。 ### 摆放方式 摆放方式也会对结果造成很大的影响。由于题目中的货物为长方体而非正方体，即使在约束 4、5、6 的约束下依然有**六**种摆放方式。日常生活中，对一个物体的摆放方式一般有“竖着”、“横着”、“躺着”、“立着”等模糊的形容。但在本算法中，需要对货物的六种摆放方式有精确的描述。 一个货物的摆放方式是由空间中三个维度决定的：前后、左右、上下。一个长方体有六个面，这六个面可以根据尺寸分为三种。这三种面在三维空间中有$A_3^3=6$种的组合情况。这些组合情况的图示如下： 【】 图像来源[3] ## 数据结构 以下数据结构都是建立在三维坐标系的基础上设计的。一个基本的数据结构是坐标点，它是由三个整型数有序组成的。第一到三个数分别表示某点在$x$、$y$、$z$轴上面的投影值。一个点记为$(d_x,d_y,d_z)$。货物和容器都是长方形的，长、宽、高分别定义为平行于$x$、$y$、$z$轴的边长。 ### 容器（箱） 容器的长、宽、高由三个整型数有序组成：$(L,W,H)$。如图所示，从正面以俯视角度看，将底面的最左上方的点设为坐标原点$(0,0,0)$。 【】 除了基本的位置和尺寸信息外，容器还需要存储其中货物的信息。货物信息由一个有序列表组成，可对其进行增、删、查的操作。 ### 货物 由于货物的摆放方式可变，这就导致边长一样的货物会出现不同的表达，即货物的长宽高是动态的。显然，货物的尺寸是一定的，不应该以动态的结构来表示，故使用集合来表达一个货物的尺寸。一个货物的长宽高，也由三个整型数有序组成：$(l,w,h)$，但其尺寸信息由一个无需的三元集合来表示：$\{l,w,h\}$。为了方便更改摆放方式，货物信息中不单独存储长、宽、高数据，而是存储其尺寸数据和摆放标志。摆放标志的值域为$\{0,1,2,3,4,5\}$，分别表示上述的六种摆放方式。 同样的，货物在空间中的位置由从正面以俯视角度看，将底面的最左上方的点决定。设第$i$个货物的在$(x_i,y_i,z_i)$的位置，相关信息如图所示。 【】 其他的数据结构与题意不大相关，都是由于算法需要和程序实现需要所建立的数据结构，详情请查看后续算法和程序设计的相关内容。 ## 算法设计 在日常砌墙时，人们一般会先放置一块参考砖，并以参考砖的高度作为基准，规定每个物体的高度都不能超过参考砖的高度，当物体不能放入时，则提高参考砖的高度。受此思想的启发，在三维装箱过程中，在水平和垂直方向上同时引入参考砖来引导装填过程。本文使用记录可放置点的方法来查找装填位置，引入水平参考线和垂直参考线来引导装填过程[1]。本文认为，与其说为参考线，不如称其为参考面更为严谨。 ### 可放置点 可放置点指的是在向容器装入一个货物时，可以用来参考货物放置位置的点。可放置点以有序列表的形式存储在容器的数据结构中，称为**可放置点表**。 虽然这个点称作可放置点，但在放置之前仍然需要检测放入的货物是否满足上述的约束条件（除约束 4）。在初始的容器中，只有一个可放置点，即原点$(0,0,0)$。在放入货物$j$后，就需要更新可放置点：将货物$j$放置时参考的可放置点从可放置点表中删除，然后再将新的可放置点添加到可放置点表中。新加的可放置点分别为货物$j$前、上、右边的点，即$(x_j+l_j,y_j,z_j)$、$(x_j,y_j+w_j,z_j)$、$(x_j,y_j,z_j+h_j)$。如图所示，可放置点在图中加粗： 【】 图像来源[1]。 可放置点表需要保持有序，其中可放置点表的顺序为$y$坐标从小到大排序，$y$坐标相同的按$x$坐标从小到大，$x$、$y$坐标都相同的按$z$坐标从大到小[1]。其原因将在“参考面”一节解释。 ### 参考面 容器内是一个三维空间，使用两个参考面作为限制，将三维装箱问题分治为一个维度。设置$x$与$z$轴上两个参考面$P_h$和$P_v$，它们分别与$xy$面平行$xy$，在考虑将一个货物装入容器时，除了需要满足上述的约束条件（除约束 4），还需要满足摆放后不能超过参考面。故放置货物时选择可放置点的顺序应先从$y$方向选择，再考虑$x$和$z$方向。这个选择方式与“可放置点”一节中对可放置点表的排序相吻合。 初始状态下，$P_h$和$P_v$的值均为 0。当一个货物装入容器但不满足参考面限制时，需要调整参考面的值，然后再重新装入货物。具体的调整方法详见“伪代码”部分。如果调整参考面后依然无法放置，则认为该货物在当前容器状态下无法置入，考虑下一个货物。 ### 挪动 根据经验，放置的箱子靠边时，才能放入更多的箱子[1]。上述的所有算法步骤中均没有考虑到约束 4 的限制。为了考虑约束 4 并进一步提高空间利用率，需要在算法中增加**挪动**这一步骤。在使用参考面引导货物载入时，特别是在先装入小尺�