好的家伙我有一个现实世界的问题,我需要一些算法来解决它.
我们有一堆订单等待发货,每个订单都有一个卷(以立方英尺为单位),比方说,V1,V2,V3,...,Vn
运输公司可以为我们提供四种类型的集装箱,集装箱的数量/价格如下:
容器类型1:2700 CuFt/$ 2500;
2号容器:2350 CuFt/2200美元;
3号容器:2050 CuFt/2170美元;
4号容器:1000 CuFt/1700美元;
没有单一订单将超过2700 CuFt但可能通过1000 CuFt.
现在我们需要一个程序来获得运费最优化的解决方案,即最低价格.
我感谢任何建议/想法.
编辑:
我目前的实现是首先使用最大的容器,应用第一个适合减少的bin包装算法来获得结果,然后解析所有容器并根据内容量调整容器大小...
Zim*_*oot 10
当我在一家物流公司工作时,我写了一个类似的程序.这是一个三维的装箱问题,比传统的一维装箱问题有点棘手 - 我工作的人写了我正在更换的旧箱子包装程序,犯了减少一切的错误一个二维打包问题(盒子的容量和包装的容量),但这不起作用:这个问题的公式表明三个8x8x8包装适合12x12x12盒子,但这会让你有重叠的包装.
我的解决方案是使用所谓的断头台切割启发式:当你将一个包裹放入运输容器中时,这会产生三个新的空子容器:假设你将包裹放在容器的左下方,那么你会有包中前面空格中的新空子容器,包右侧空间中的新空子容器,以及包顶部的新空子容器.确保不要将相同的空白空间分配给多个子容器,例如,如果您不小心,那么您将把容器右前方的部分分配给前子容器和右子容器,你需要选择一个分配它.这种启发式方法将排除一些最佳解决方案,但速度很快.(举一个具体的例子,假设你有一个12x12x12的盒子并且你把一个8x8x8的包放入其中 - 这将留下一个4x12x12的空子容器,一个4x8x12的空子容器和一个4x8x8的空子容器.划分自由空间的错误方法是有三个4x12x12空子容器 - 这将导致包装重叠.如果包装盒或包装不是立方体,那么你有多种方法来分割自由空间 - 您需要决定是否最大化一个或两个子容器的大小,或者尝试创建三个或多或少相等的子容器.)您需要使用合理的标准来排序/选择子容器 - 容器或子容器的数量将呈指数增长; 我通过首先填充最小的子容器并移除任何太小而不包含包的子容器来解决这个问题,这使得子容器的数量保持在合理的数量.
你有几个选择:使用什么容器,如何旋转进入容器的包(通常有六种旋转包的方法,但不是所有的旋转都适用于某些包,例如"这个最终"包将只有两个旋转),如何分区子容器(例如,您是否将重叠空间分配给右侧子容器或前子容器),以及您打包容器的顺序.我使用了一个随机算法来近似一个最适合减少的启发式(使用启发式的体积),并且有利于创建一个大的子容器和两个小的子容器而不是三个中型子容器,但我随机使用了数字生成器混合起来(所以最大的可能性是我首先选择最大的包,但是我首先选择第二大包的概率较小,依此类推,概率最低的是我首先选择最小的包装;同样,我有可能赞成创建三个中型子容器而不是一个大型和两个小型容器,我有可能使用三个中型盒子而不是两个大盒子等).然后,我并行地运行了几十次并选择了成本最低的结果.
我还考虑过其他启发式算法,例如极端点启发式算法较慢(同时仍然在多项式时间运行 - IIRC它是一个立方时间解决方案,而断头台切割启发式是线性时间,而在另一个极端,分支和绑定算法发现最佳解决方案并以指数时间运行)但更准确(具体而言,它找到了一些由断头台切割启发式排除的最佳解决方案); 但是,我的用例是我应该产生一个快速的运输估计,所以极端点启发式不合适(它太慢而且"太准确" - 我需要增加10%或20为了说明实际包装盒子的人不可避免地会做出次优选择这一事实的结果%.
我不知道程序的名称,但可能会有一些商业软件可以解决这个问题,具体取决于一个好的解决方案对你有多大价值.