算法的集装箱规划 [英] Algorithm for container planning

问题描述

确定家伙，我有一个现实世界的问题，我需要一些算法计算出来。
我们有一大堆的订单等待发运，每个订单将有一个体积（立方米），让我们说，V1，V2，V3，...，Vn的

OK guys I have a real world problem, and I need some algorithm to figure it out.
We have a bunch of orders waiting to be shipped, each order will have a volume (in cubic feet), let's say, V1, V2, V3, ..., Vn

的运输载体可以为我们提供四种类型的容器，并且容器的体积/价格如下：

The shipping carrier can provide us four types of containers, and the volume/price of the containers are listed below:

集装箱类型1：2700立方英尺/ $ 2500个;
集装箱类型2：2350立方英尺/ $ 2200;
集装箱类型3 2050立方英尺/ $ 2170;
集装箱类型4：1000立方英尺/ $ 1700年;

Container Type 1: 2700 CuFt / $2500;
Container Type 2: 2350 CuFt / $2200;
Container Type 3: 2050 CuFt / $2170;
Container Type 4: 1000 CuFt / $1700;

没有单一的订单将超过2700立方英尺，但可能通过1000立方英尺。

No single order will exceed 2700 CuFt but likely to pass 1000 CuFt.

现在，我们需要一个程序，以获取有关运费，也就是最低的价格优化的解决方案。
我AP preciate任何建议/意见。

Now we need a program to get an optimized solution on freight charges, that is, minimum prices.
I appreciate any suggestions/ideas.

编辑：
我目前的实现是用最大的集装箱在第一，申请的第一个适合下降算法装箱根据内容量得到的结果，然后通过分析所有的容器和调整容器尺寸...

My current implementation is using biggest container at first, apply the first fit decreasing algorithm for bin packing to get result, then parse through all containers and adjust container sizes according to the content volume...

推荐答案

我写了一个类似的计划时，我所工作的一家物流公司。这是一个三维装箱问题，这比一个经典的一维装箱问题有点棘手 - 此人在我的工作是谁写的，我是装做降低了一切错误的旧箱包装程序以一维装箱问题（卷箱，包卷），但这并不工作：​​这个问题的提法州三个8x8x8包将放入一个12x12x12中，但这将留给你重叠包。

I wrote a similar program when I was working for a logistics company. This is a 3-dimensional bin-packing problem, which is a bit trickier than a classic 1-dimensional bin-packing problem - the person at my job who wrote the old box-packing program that I was replacing made the mistake of reducing everything to a 1-dimensional bin-packing problem (volumes of boxes and volumes of packages), but this doesn't work: this problem formulation states that three 8x8x8 packages would fit into a 12x12x12 box, but this would leave you with overlapping packages.

我的解决方案是使用什么叫做铡切启发：当你把一个包放入运输容器那么这会产生三个新的空分容器：假设你在容器的背面左下角放置在包中，然后你将有一个新的空副容纳在包中，一个新的空副容纳在该空间的包的右前方的空间，并在封装的顶部上的新的空的子容器。肯定不会分配相同的空到多个子容器，如：如果你不小心的话，你会在指定容器前副容器和右子容器的前部右侧的部分，你需要只选择一个要分配给它。这种启发式将排除一些优化的解决方案，但它的速度快。 （作为一个具体的例子，假设你有一个12x12x12框，你把一个8x8x8包进去 - 这将留给你一个4x12x12空的子容器，4x8x12空的子容器和4x8x8空的子容器注意。在错误的方式来划分的自由空间是有三个4x12x12空子容器 - 这将导致重叠的包装如果包装盒或包装不立方体，那么你就会有更多的以上的方式来划分的自由空间 - 你需要决定是否最大化的一个或两个子容器的大小或代替尝试创建三个或更少的平等子容器），您需要使用合理的。标准排序/选择所述子容器或其他子容器将成倍增长的数目;我先填最小的子容器和删除所有子容器太小，无法容纳一个包，里面存放子容器的数量在合理数量的解决了这个问题。

My solution was to use what's called a guillotine cut heuristic: when you put a package into the shipping container then this produces three new empty sub-containers: assuming that you placed the package in the back bottom left of the container, then you would have a new empty sub-container in the space in front of the package, a new empty sub-container in the space to the right of the package, and a new empty sub-container on top of the package. Be certain not to assign the same empty space to multiple sub-containers, e.g. if you're not careful then you'll assign the section in the front-right of the container to the front sub-container and to the right sub-container, you'll need to pick just one to which to assign it. This heuristic will rule out some optimal solutions, but it's fast. (As a concrete example, say you have a 12x12x12 box and you put an 8x8x8 package into it - this would leave you with a 4x12x12 empty sub-container, a 4x8x12 empty sub-container, and a 4x8x8 empty sub-container. Note that the wrong way to divide up the free space is to have three 4x12x12 empty sub-containers - this is going to result in overlapping packages. If the box or package weren't cubes then you'd have more than one way to divide up the free space - you'd need to decide whether to maximize the size of one or two sub-containers or to instead try to create three more or less equal sub-containers.) You need to use a reasonable criteria for ordering/selecting the sub-containers or else the number of sub-containers will grow exponentially; I solved this problem by filling the smallest sub-containers first and removing any sub-container that was too small to contain a package, which kept the quantity of sub-containers to a reasonable number.

有，你有几种选择：用什么容器，如何旋转包进入容器（通常有六种方式旋转的包，但不是所有的旋转是法律对一些软件包，例如一个为此起来包只会有两次旋转），如何分割子容器（例如，你指定的重叠空间到右子容器或到前副容器），以及以什么顺序你包的容器。我用随机算法近似的最佳拟合减少启发式（使用量为启发式）和一种有利于创建一个大的子容器和两个小子容器而不是三个中型子容器，但我用一个随机数发生器混为一谈（所以最大的可能性是，我会先选择大包，但仍然会有，我会首先选择第二大封装的概率较小，等等，最低的概率是我会首先选择最小的封装;同样，有一个，我会赞成创建三个中型子容器，而不是一大两小，有一个机会，我会使用机会三个中等规模箱，而不是两个大箱子，等）。然后我跑这个并行数十倍，并选择了成本最低的结果。

There are several options you have: what containers to use, how to rotate the packages going into the container (there are usually six ways to rotate a package, but not all rotations are legal for some packages e.g. a "this end up" package will only have two rotations), how to partition the sub-containers (e.g. do you assign the overlapping space to the right sub-container or to the front sub-container), and in what order you pack the container. I used a randomized algorithm that approximated a best-fit decreasing heuristic (using volume for the heuristic) and that favored creating one large sub-container and two small sub-containers rather than three medium-sized sub-containers, but I used a random number generator to mix things up (so the greatest probability is that I'd select the largest package first, but there would be a lesser probability that I'd select the second-largest package first, and so on, with the lowest probability being that I'd select the smallest package first; likewise, there was a chance that I'd favor creating three medium-sized sub-containers instead of one large and two small, there was a chance that I'd use three medium-sized boxes instead of two large boxes, etc). I then ran this in parallel several dozen times and selected the result that cost the least.

有其他启发式予考虑，例如端点启发式较慢（同时仍然运行在多项式时间 - IIRC它是一个立方体时间的解决方案，而铡切启发式是线性的时间，并在另一个极端的分支和界算法找到最优解和运行在指数时间），但更准确的（具体而言，它发现排除​​了用截切启发式）一些最优解;然而，我的用例是，我本来是要产生一个快速出货的估计的，因此极端一点启发是不恰当的（这是太慢了，这是太准确 - 我会需要10％或20％添加到它的结果考虑到一个事实，即实际上包装盒中的人会不可避免地使亚最佳选择）。

There are other heuristics I considered, for example the extreme point heuristic is slower (while still running in polynomial time - IIRC it's a cubic time solution, whereas the guillotine cut heuristic is linear time, and at the other extreme the branch and bound algorithm finds the optimal solution and runs in exponential time) but more accurate (specifically, it finds some optimal solutions that are ruled out by the guillotine cut heuristic); however, my use case was that I was supposed to produce a fast shipping estimate, and so the extreme point heuristic wasn't appropriate (it was too slow and it was "too accurate" - I would have needed to add 10% or 20% to its results to account for the fact that the people actually packing the boxes would inevitably make sub-optimal choices).

我不知道一个程序副手的名字，但有可能是一些商业软件，将解决这个问题对你来说，这取决于有多少一个好的解决方案是值得你。

I don't know the name of a program offhand, but there's probably some commercial software that would solve this for you, depending on how much a good solution is worth to you.

这篇关于算法的集装箱规划的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！