玩具箱挑战 - 电子商务运输/集装箱拆分
Toy box challenge - E-commerce Shipment / Container splitting
编辑:我正在寻找一种高效的 Ruby、Java脚本、Java 或 Python 3D 装箱实现以下限制
我正在寻找一种有效的算法来正确识别存储项目列表所需的容器数量。上下文是围绕为电子商务订单生成准确数量和类型的运输标签。
鉴于:
- 物品具有已知的宽度、长度、深度和重量
- 物品的包装类型指定它们可以与同一容器中的其他物品合并 ("over-pack"),或者必须用它们自己的容器运输 ("ship-alone")
- 容器具有已知的宽度、长度、深度和承重能力
- 可提供多种不同尺寸和容量的容器
问题:
- 存在一个项目列表,可能具有不同的尺寸和包装类型,并且可能有多种数量。拆分项目列表,以便它们可以存储在尽可能少的容器中
我认为这是一个有趣的体积数学挑战,你们中的一些人可能会喜欢。我正在寻找对此的最佳编程解决方案。
很高兴收到偏爱 Java、JavaScript、Python 或 Ruby.
的任何语言的解决方案
提前致谢!
这正是 3D bin-packing problem。
"ship alone" 的要求简单地通过将这些元素放在外面并单独运输它们而减少,这让您与其他人在一起。
找到包装它们所需的最少容器数量现在是 3 维装箱问题 space。
不幸的是,这个问题是 NP-Hard 问题,因此与背包不同 - 没有已知的伪多项式最优解。
本文讨论问题:
The Three-Dimensional Bin Packing Problem (Martello et al)
编辑:我正在寻找一种高效的 Ruby、Java脚本、Java 或 Python 3D 装箱实现以下限制
我正在寻找一种有效的算法来正确识别存储项目列表所需的容器数量。上下文是围绕为电子商务订单生成准确数量和类型的运输标签。
鉴于:
- 物品具有已知的宽度、长度、深度和重量
- 物品的包装类型指定它们可以与同一容器中的其他物品合并 ("over-pack"),或者必须用它们自己的容器运输 ("ship-alone")
- 容器具有已知的宽度、长度、深度和承重能力
- 可提供多种不同尺寸和容量的容器
问题:
- 存在一个项目列表,可能具有不同的尺寸和包装类型,并且可能有多种数量。拆分项目列表,以便它们可以存储在尽可能少的容器中
我认为这是一个有趣的体积数学挑战,你们中的一些人可能会喜欢。我正在寻找对此的最佳编程解决方案。
很高兴收到偏爱 Java、JavaScript、Python 或 Ruby.
的任何语言的解决方案提前致谢!
这正是 3D bin-packing problem。
"ship alone" 的要求简单地通过将这些元素放在外面并单独运输它们而减少,这让您与其他人在一起。
找到包装它们所需的最少容器数量现在是 3 维装箱问题 space。
不幸的是,这个问题是 NP-Hard 问题,因此与背包不同 - 没有已知的伪多项式最优解。
本文讨论问题: The Three-Dimensional Bin Packing Problem (Martello et al)