我在一家物流公司工作时写了一个类似的程序。这是一个 3 维装箱问题,比经典的 1 维装箱问题要棘手一些——我工作中编写我要替换的旧装箱程序的人犯了一个错误,即减少所有内容到一维装箱问题(盒子的体积和包裹的体积),但这不起作用:这个问题公式表明三个 8x8x8 的包裹可以装进一个 12x12x12 的盒子,但这会让你有重叠的包裹。
我的解决方案是使用所谓的断头台切割启发法:当您将包裹放入运输容器时,这会产生三个新的空子容器:假设您将包裹放在容器的左下角,那么您将拥有包前面的空间有一个新的空子容器,包右边的空间有一个新的空子容器,包顶部的空间有一个新的空子容器。一定不要为多个子容器分配相同的空白空间,例如,如果您不小心,则将容器右前部的部分分配给前子容器和右侧子容器,您只需要选择一个来分配它。这种启发式将排除一些最佳解决方案,但速度很快。(作为一个具体的例子,假设您有一个 12x12x12 的盒子,然后将一个 8x8x8 的包装放入其中 - 这将留下一个 4x12x12 的空子容器、一个 4x8x12 的空子容器和一个 4x8x8 的空子容器。请注意,分配可用空间的错误方法是拥有三个 4x12x12 空子容器 - 这将导致包重叠。如果盒子或包裹不是立方体,那么您将有不止一种方法来划分可用空间 - 您需要决定是最大化一个或两个子容器的大小,还是尝试创建三个或多或少相等的子容器。)您需要使用合理的标准来订购/选择子容器,否则子容器的数量将成倍增长;我通过首先填充最小的子容器并移除任何太小而无法容纳包裹的子容器来解决这个问题,从而将子容器的数量保持在合理的数量。
您有几个选项:使用什么容器,如何旋转进入容器的包裹(通常有六种旋转包裹的方法,但并非所有旋转对于某些包裹都是合法的,例如“this end up”包裹将只有两个旋转),如何划分子容器(例如,您将重叠空间分配给正确的子容器还是分配给前面的子容器),以及您以什么顺序包装容器。我使用了一种随机算法,该算法近似于最佳拟合递减启发式(使用体积作为启发式),并且倾向于创建一个大型子容器和两个小型子容器,而不是三个中型子容器,但我使用了随机数字生成器来混合(所以最大的可能性是我会先选择最大的包,但是我首先选择第二大包裹的可能性较小,依此类推,而我首先选择最小包裹的可能性最低;同样,我有可能更喜欢创建三个中型子容器而不是一个大两个小,有可能我会使用三个中型盒子而不是两个大盒子,等等)。然后我并行运行了几十次,并选择了成本最低的结果。d 使用三个中型盒子而不是两个大盒子等)。然后我并行运行了几十次,并选择了成本最低的结果。d 使用三个中型盒子而不是两个大盒子等)。然后我并行运行了几十次,并选择了成本最低的结果。
我考虑了其他启发式方法,例如极值启发式方法较慢(虽然仍在多项式时间内运行 - IIRC 它是一个三次时间解决方案,而断头台切割启发式方法是线性时间,而在另一个极端,分支定界算法发现最优解并在指数时间内运行)但更准确(具体来说,它会找到一些被断头台切割启发式排除的最优解);然而,我的用例是我应该产生一个快速的运输估计,所以极点启发式是不合适的(它太慢而且“太准确”——我需要增加 10% 或 20 % 以说明实际包装盒子的人不可避免地会做出次优选择)。
我不知道程序的名称,但可能有一些商业软件可以为你解决这个问题,这取决于一个好的解决方案对你来说价值多少。