Comparing Heuristics, Constraint Optimization, and Reinforcement
  Learning for an Industrial 2D Packing Problem
  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.
