容器规划算法

Question

好吧伙计们，我有一个现实世界的问题，我需要一些算法来解决它。
我们有一堆订单等待发货，每个订单都有一个体积(立方英尺)，比方说，V1、V2、V3、...、Vn

承运商可以为我们提供四种类型的容器，容器的体积/价格如下:

容器类型 1:2700 立方英尺/2500 美元；
容器类型 2:2350 立方英尺/2200 美元；
容器类型 3:2050 立方英尺/2170 美元；
容器类型 4:1000 立方英尺/1700 美元；

没有单笔订单会超过 2700 CuFt，但可能会超过 1000 CuFt。

现在我们需要一个程序来获得运费的优化解决方案，即最低价格。
我感谢任何建议/想法。

编辑:
我目前的实现是首先使用最大的容器，应用第一个拟合递减算法进行装箱以获得结果，然后解析所有容器并根据内容量调整容器大小......

Answer 1

我在一家物流公司工作的时候写过一个类似的程序。这是一个 3 维装箱问题，它比经典的 1 维装箱问题要棘手一些 - 我工作的那个编写我正在替换的旧装箱程序的人犯了减少一切的错误到一维装箱问题(盒子的体积和包裹的体积)，但这不起作用:这个问题公式指出三个 8x8x8 包裹可以放入一个 12x12x12 盒子，但这会让你有重叠的包裹。

我的解决方案是使用所谓的断头台切割启发式:当您将包裹放入运输容器时，这会产生三个新的空子容器:假设您将包裹放置在容器的后左下角，那么您将有在包裹前面的空间中放置一个新的空子容器，在包裹右侧的空间中放置一个新的空子容器，并在包裹顶部放置一个新的空子容器。一定不要将相同的空白空间分配给多个子容器，例如如果您不小心，那么您会将容器右前方的部分分配给前面的子容器和右侧的子容器，您只需选择一个分配给它。这种启发式将排除一些最佳解决方案，但速度很快。 (举一个具体的例子，假设你有一个 12x12x12 的盒子，你把一个 8x8x8 的包裹放进去——这会给你一个 4x12x12 的空子容器、一个 4x8x12 的空子容器和一个 4x8x8 的空子容器。请注意 错误 划分可用空间的方法是拥有三个 4x12x12 的空子容器 - 这将导致包裹重叠。如果盒子或包裹不是立方体，那么您将拥有超过一种划分可用空间的方法 - 您需要决定是最大化一个或两个子容器的大小，还是尝试创建三个或多或少相等的子容器。)您需要使用合理的标准用于订购/选择子容器，否则子容器的数量将呈指数增长；我通过首先填充最小的子容器并移除任何太小而无法容纳包裹的子容器来解决这个问题，从而将子容器的数量保持在合理的数量。

您有几种选择:使用什么容器，如何旋转进入容器的包裹(通常有六种方法可以旋转包裹，但并非所有旋转对于某些包裹都是合法的，例如“这个最终”包裹将只有两个旋转)，如何划分子容器(例如，您是将重叠空间分配给右侧子容器还是前子容器)，以及包装容器的顺序。我使用了一种随机算法，该算法近似于最佳拟合递减启发式(使用体积作为启发式)并且倾向于创建一个大子容器和两个小子容器而不是三个中型子容器，但我使用了随机数字生成器来混合(所以最大的可能性是我首先选择最大的包，但我首先选择第二大的包的可能性较小，依此类推，最低的概率是我会先选择最小的包；同样，我有可能更喜欢创建三个中型子容器，而不是一个大两个小，也有可能我会使用三个中型子容器盒子而不是两个大盒子等)。然后我并行运行了几十次，并选择了成本最低的结果。

我还考虑了其​​他启发式方法，例如极点启发式方法较慢(虽然仍在多项式时间内运行 - IIRC 它是三次时间解，而断头台启发式方法是线性时间，而在另一个极端，分支定界算法发现最优解并在指数时间内运行)但更准确(具体来说，它找到了一些被断头台启发式排除的最优解)；然而，我的用例是我应该产生一个快速的运输估计，所以极值启发式是不合适的(它太慢而且“太准确” - 我需要添加 10% 或 20 % 以说明实际包装盒子的人将不可避免地做出次优选择的事实)。

我不知道一个程序的名称，但是可能有一些商业软件可以为您解决这个问题，这取决于一个好的解决方案对您的值(value)有多大。