物流公司在流通过程中，需要将打包完毕的箱子装入到一个货车的车厢中，为了提高物流效率，需要将车厢尽量填满，显然，车厢如果能被100%填满是最优的，但通常认为，车厢能够填满85%，可认为装箱是比较优化的。

设车厢为长方形，其长宽高分别为$L，W，H$；共有$n$个箱子，箱子也为长方形，第$i$个箱子的长宽高为$li，wi，hi$（$n$个箱子的体积总和是要远远大于车厢的体积），做以下假设和要求：

1. 长方形的车厢共有8个角，并设靠近驾驶室并位于下端的一个角的坐标为（0,0,0），车厢共6个面，其中长的4个面，以及靠近驾驶室的面是封闭的，只有一个面是开着的，用于工人搬运箱子；

2. 需要计算出每个箱子在车厢中的坐标，即每个箱子摆放后，其和车厢坐标为（0,0,0）的角相对应的角在车厢中的坐标，并计算车厢的填充率。

通过问题建模，定义块、块表、剩余空间堆栈和剩余需放箱子的数据结构。采用启发式算法的思想来对问题进行求解。主要的算法流程如下：

1. 取出当前可行块
2. 取出剩余空间堆栈中的栈顶剩余空间
3. 尝试放置当前可行块至栈顶剩余空间中
4. 评估当前的状态，并将此评估值作为被选块的适应度面
5. 从当前状态移除当前可行块
6. 判断可行块列表是否遍历完成，若是则选取适应度最高的块作为结果，若否则返回步骤1再次执行

块放置算法将块和栈顶空间结合成一个放置加入当前放置方案，移除栈顶空间，扣除已使用物品，然后切割未填充空间并加入剩余空间堆栈。

块移除算法从当前部分放置方案中移除当前块所属的放置，恢复已使用物品，移除空间堆栈栈顶的三个切割出来的剩余空间，并将已使用剩余空间重新插入栈顶。

除了块放置和块移除算法，另一个极其重要的算法是部分放置方案补全算法。评估当前的部分放置方案好坏的最直接的方法是用某种方式补全它，并以最终结果的填充率作为当前状态的评估值。该算法实际上是整体基本启发式算法的一个简化版本，区别在于每个装载阶段算法都选择可行块列表中体积最大的块进行放置。由于可行块列表已经按照体积降序排列，实际上算法选择的块总是列表的第一个元素。算法不改变输入的部分放置方案，只是把最终补全的结果记录在此状态的$v o l u m e _ {c o m p l e t e}$域作为该状态的评估值。

在块的选择算法过程中，可以采用贪心算法，直接返回填充体积最大的块，由于可行块列表已经按照体积降序排列，实际上算法选择的块总是列表的第一个元素。

采用深度优先搜索算法扩展当前放置方案，算法的输入为一个部分放置方案，深度限制和最大分支数。该算法从一个部分放置方案出发，递归的尝试可行块列表中的块，在到达深度限制的时候调用补全函数得到当前方案的评估值，并记录整个搜索过程找到的最优的评估值作为输入部分放置方案的评估。

项目分为三个模块，main、function、classes。

• main：主函数，其中包含了实验的数据信息，如果需要修改实验数据则在其中修改。运行其可得到实验结果。
• function：定义了算法所需要的各种功能函数。
• classes：包含了求解问题所定义的各种数据结构。

实验数据如下：

实验结果如下：

如上表所示，可以看出最终的载荷情况，在第一次实验中，由于箱子数量不足，最终全部装入的情况下填充率仍然只有87.5%，而之后的两次实验中，箱子总体积大于货车的最大载荷，而使用算法进行装箱，填充率分别到达100%和87.6%。证明装箱的效果较优。