Cutting and Packing problems are occurring in different industries with a direct impact on the revenue of businesses. Generally, the goal in Cutting and Packing is to assign a set of smaller objects to a set of larger objects. To solve Cutting and Packing problems, practitioners can resort to heuristic and exact methodologies. Lately, machine learning is increasingly used for solving such problems. This paper considers a 2D packing problem from the furniture industry, where a set of wooden workpieces must be assigned to different modules of a trolley in the most space-saving way. We present an experimental setup to compare heuristics, constraint optimization, and deep reinforcement learning for the given problem. The used methodologies and their results get collated in terms of their solution quality and runtime. In the given use case a greedy heuristic produces optimal results and outperforms the other approaches in terms of runtime. Constraint optimization also produces optimal results but requires more time to perform. The deep reinforcement learning approach did not always produce optimal or even feasible solutions. While we assume this could be remedied with more training, considering the good results with the heuristic, deep reinforcement learning seems to be a bad fit for the given use case.
翻译:切割和包装问题发生在对商业收入有直接影响的不同行业。一般而言,切割和包装的目标是为一组更大的对象分配一组较小的物体。为了解决切割和包装问题,从业人员可以采用超速和精确的方法。最近,机器学习越来越多地用于解决这类问题。本文考虑了家具行业的2D包装问题,在这个行业中,必须用最节省空间的方式将一组木制工作机件分配给电车的不同模块。我们提出了一个实验装置,以比较超速、限制优化和对特定问题的深度强化学习。用过的方法及其结果根据解决方案质量和运行时间加以整理。在特定情况下,贪婪的超值产生最佳结果,在运行时间方面优于其他方法。控制优化也会产生最佳效果,但需要更多的时间来完成。深层强化学习方法并不总是产生最佳或甚至可行的解决办法。我们假设,用更多的培训来纠正这一方法,因为有了超值、深层强化学习的良好结果,因此似乎不合适。