/ClothCutting

天池2019广东工业智造创新大赛,布料切割方案算法设计

Primary LanguageC++GNU General Public License v3.0GPL-3.0

ClothCutting

天池2019广东工业智造创新大赛,布料切割方案算法设计

环境依赖

  • Microsoft Visual Studio 2017
  • Lib/
    • Boost Geometry 1.65.1:header-only-library,附加包含目录已追踪,下载 boost.zip 并解压至 Lib/ 目录
    • Clipper:附加包含目录已追踪
    • libnfporb:用于生成 nfp 的 header-only-library,附加包含目录已追踪
  • Cmake

TODO

  • 检查算例中零件方向,统一为按照逆时针方向旋转;
  • 使用 clipper 放大、简化多边形的顺序和必要性?
  • libnfporb 实现有问题?
  • 添加瑕疵,将瑕疵转换为多边形,同时也要参加差集运算;
  • 改写为 cmake 工程,适配 Linux 平台,最终打包成 docker 镜像。

参考

Nest4J:https://github.com/Yisaer/Nest4J

libnfporb 参考论文:E.K. Burke et al. 2006

基于可行解(贪心、模拟退火):Solving Irregular Strip Packing problems by hybridising simulated annealing and linear programming

基于不可行解(重叠消除):An iterated local search algorithm based on nonlinear programming for the irregular strip packing problem

Ps:目前实现的是基于可行解的贪心放置策略,几何运算开销较大,理论上基于不可行解的重叠消除效果可能更好。