Deep learning-based initialization for object packing

Maciej Wołczyk


One of the most important optimization tasks in the industry at the current time is the object packing problem. Although several methods have been developed for the purpose of solving it, they are usually only able to optimize placement locally and as such are heavily dependent on the choice of the initial setting -- hence the need for trying out multiple possible starting points, which impacts algorithm running time. In this paper we present a neural network-based model which provides sensible starting points in a linear time.

Słowa kluczowe: cutting & packing, optimization, object packing problem, phi-functions, deep learning

[1] Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. arXiv preprint arXiv:1409.0473, 2014.

[2] Julia A Bennell and Jose F Oliveira. The geometry of nesting problems: A tutorial. European Journal of Operational Research, 184(2):397-415, 2008.

[3] N Chernov, Yu Stoyan, and Tatiana Romanova. Mathematical model and ecient algorithms for object packing problem. Computational Geometry, 43(5):535-553, 2010. 

[4] N Chernov, Yu Stoyan, Tatiana Romanova, and Aleksandr Pankratov. Phifunctions for 2d objects formed by line segments and circular arcs. Advances in Operations Research, 2012, 2012.

[5] A Miguel Gomes and Jose F Oliveira. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3):811-829, 2006.

[6] E Hopper and B Turton. A genetic algorithm for a 2d industrial packing problem. Computers & Industrial Engineering, 37(1-2):375-378, 1999.

[7] Haoyuan Hu, Xiaodong Zhang, Xiaowei Yan, Longfei Wang, and Yinghui Xu. Solving a new 3d bin packing problem with deep reinforcement learning method. arXiv preprint arXiv:1708.05930, 2017.

[8] Hiroyuki Okano. A scanline-based algorithm for the 2d free-form bin packing problem. Journal of the Operations Research Society of Japan, 45(2):145-161, 2002.

[9] Ilya Sutskever, Oriol Vinyals, and Quoc V Le. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104-3112, 2014.

[10] Gerhard Wascher, Heike Hauner, and Holger Schumann. An improved typology of cutting and packing problems. European journal of operational research, 183(3):1109-1130, 2007.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.

Wersja papierowa czasopisma dostępna na