2D装箱算法

Question

我花费了一些时间研究2D装箱算法。虽然我对算法和高级数学没有广泛的经验，但我会编程 :)

完美的例子是这里展示的http://www.cutlistoptimizer.com。它可以工作，但我无法弄清楚它使用了哪个算法。

我尝试了许多方法，其中一些非常简单，例如https://codeincomplete.com/posts/bin-packing/此处有演示，但它不支持旋转，这是必要的。

对我来说最有前途的是https://ssbothwell.github.io/greedypacker-react/。我不确定我是否做错了什么，但它没有为我计算出最佳拟合。我已经尝试了不同算法的不同组合。

演示数据： 纸张大小：w:2655，h:2100

{ w: 900, h: 320 },
 { w: 320, h: 900 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 900, h: 320 },
 { w: 386, h: 310},
 { w: 386, h: 310},
 { w: 386, h: 310},
 { w: 386, h: 310},
 { w: 386, h: 310},
 { w: 860,  h: 320},
 { w: 860,  h: 320},
 { w: 564,  h: 310 },
 { w: 452,  h: 293},
 { w: 720,  h: 530},
 { w: 720,  h: 530},
 { w: 696,  h: 530},
 { w: 696,  h: 100 }

这些零件应该可以放在一张纸上。

参考图片

经过一段时间的研究，我已经发现可能应该使用遗传算法来演化这些启发式方法。这有意义吗？

- Colin

---

为什么不提前旋转项目以获得 w >= h？ - Nina Scholz

我可以做到，但不确定是否能优化打包。我会尝试并告诉你。 - Colin

@NinaScholz 由于某些部分需要不同的旋转，因此无法达到最佳结果，例如w<h。我已经更新了原始问题，并附上了解释这种行为的图片。 - Colin

Answer 1

你可以在文献中找到这个问题被称为2KP，或者二维背包问题。在你的具体情况下，这是没有方向约束的2KP（即物体可以旋转）。

不幸的是，这个问题属于NP-Hard问题的范畴，这意味着目前没有已知的多项式时间解法。

根据你的使用情况，训练遗传算法可能是一个很好的解决方案，可能与其他研究过的启发式方法相结合。一些常见的启发式方法包括：从左下角开始填充，找到最大的空白空间并用最佳适配的零件填充，按层次排序等。由于你还考虑了物体的旋转，一个合理的启发式方法是限制可能的旋转（例如只能以45度的步长旋转）。

两篇相关论文：

《具有矩形零件的二维背包问题的遗传算法》。Andreas Bortfeldt, Tobias Winter

《关于二维背包问题》。Alberto Caprara, Michele Monaci

- user2566976