Deep learning-based initialization for object packing

• Autorzy: Wołczyk Maciej

Identyfikatory

DOI

10.4467/20838476SI.18.001.10406

• Języki publikacji: EN

Abstrakty

EN

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 networkbased model which provides sensible starting points in a linear time.

Słowa kluczowe

EN

cutting; packing; optimization; object packing problem; phi-function; deep learning

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Schedae Informaticae
• Rocznik: 2018
• Tom: Vol. 27
• Strony: 9--17
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Wołczyk Maciej

• Faculty of Mathematics and Computer Science Jagiellonian University, Lojasiewicza 6, 30-348 Kraków, Poland

Bibliografia

• [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 efficient 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 Jos´e 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 W¨ascher, Heike Haußner, and Holger Schumann. An improved typology of cutting and packing problems. European journal of operational research, 183(3):1109–1130, 2007.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).