Wyznaczanie sposobu pakowania palet dla robota

pol Article in Polish DOI: 10.14313/PAR_240/11

send Krzysztof Pieńkosz Politechnika Warszawska, Instytut Automatyki i Informatyki Stosowanej, ul. Nowowiejska 15/19, 00-665 Warszawa

Download Article

Streszczenie

Artykuł dotyczy zagadnienia automatycznego pakowania palet przez robota. W procesach logistycznych branży handlowej towary dostarczane z magazynów do sklepów sprzedaży detalicznej są transportowane na paletach. W artykule analizowane są sposoby układania i rozmieszczenia towarów na palecie pod kątem możliwości realizacji takich upakowań przez robota. Żeby robot mógł umieścić towar w danym miejscu na częściowo załadowanej palecie, musi mieć do tego miejsca swobodny dostęp, tzn. miejsce to nie może być zasłonięte. Zaproponowano grafowy model reprezentacji upakowań i sformalizowaną metodę wyznaczania kolejności ustawiania towarów na palecie przez robota. Pokazano też, że nie każdy wzór upakowania da się ułożyć przy użyciu robota.

Słowa kluczowe

grafy poprzedzania, pakowanie robotowe, sortowanie topologiczne, trójwymiarowy problem pakowania pojemników, załadunek palet

Sequencing of Robot Packing

Abstract

In the paper the problem of an automatic pallet loading with the usage of a robot is considered. In the logistic processes of trade business commodities are distributed from stores to retailers on pallets. In the paper the methods of pallet loading are analyzed in terms of the robot packing abilities. In order to put an item in a given place in a partially loaded pallet, robot needs to have free access to this place, so it cannot be blocked. A graph model is proposed to represent the relative positions of items on pallets and a method for sequencing of robot packing operations is formulated. It is also shown that not all patterns of pallet packing can be realized by a robot.

Keywords

comparability graphs, container loading problem, robot packing, three-dimensional bin packing, topological sort

Bibliography

  1. Cormen T., Leiserson C., Rivest R., Wprowadzenie do algorytmów, WNT, Warszawa 1997.
  2. Crainic T., Perboli G., Tadei R., Extreme pointbased heuristics for three-dimensional bin packing, “INFORMS Journal on Computing”, Vol. 20, No. 3, 2008, 368–384, DOI: 10.1287/ijoc.1070.0250.
  3. den Boef E., Korst J., Martello S., Pisinger D., Vigo D., Erratum to “The three-dimensional bin packing problem”: Robot-packable and orthogonal variants of packing problems, “Operations Research”, Vol. 53, No. 4, 2005, 735–736, DOI: 10.1287/opre.1050.0210.
  4. He K., Huang W., An efficient placement heuristic for three- -dimensional rectangular packing, “Computers & Operations Research”, Vol. 38, No. 1, 2011, 227–233, DOI: 10.1016/j.cor.2010.04.015.
  5. Lim A., Ma H., Xu J., Zang X., An iterated construction approach with dynamic prioritization for solving the container loading problem, “Expert Systems with Applications”, Vol. 39, No. 4, 2012, 4292–4305, DOI: 10.1016/j.eswa.2011.09.103.
  6. Martello S., Pisinger D., Vigo D., The three-dimensional bin packing problem, “Operations Research”, Vol. 48, No. 2, 2000, 256–267, DOI: 10.1287/opre.48.2.256.12386.
  7. Silva E., Oliveira J., Wascher G., The pallet loading problem: a review of solution methods and computational experiments, “International Transactions in Operational Research”, Vol. 23, 2016, 147–172, DOI: 10.1111/itor.12099.
  8. Zhao X., Bennell J., Bektas T., Dowsland K., Comparative review of 3D container loading algorithms, “International Transactions in Operational Research”, Vol. 23, No. 1-2, 2016, 287–320, DOI: 10.1111/itor.12094.
  9. Zhu W. Lim A., A new iterative-doubling Greedy–Lookahead algorithm for the single container loading problem, “European Journal of Operational Research”, Vol. 222, No. 3, 2012, 408–417, DOI: 10.1016/j.ejor.2012.04.036.
  10. Zhu W., Oon W., Lim A., Weng Y., The six elements to block-building approaches for the single container loading problem, “Applied Intelligence”, Vol. 37, 2012, 431–445, DOI: 10.1007/s10489-012-0337-0.
  11. Zhu W., Zhang Z., Oon W., Lim A., Space defragmentation for packing problems, ”European Journal of Operational Research”, Vol. 222, No. 3, 2012, 452–463, DOI: 10.1016/j.ejor.2012.05.031.