Graph models for identifying robot-packable patterns of pallet loading

• Autorzy: Pieńkosz Krzysztof

Identyfikatory

DOI

10.37190/ord240409

• Języki publikacji: EN

Abstrakty

EN

In the logistics processes of trade business, goods delivered from warehouses to retailers are often transported on pallets. The paper concerns the issue of using a robot for automatic palletizing. In order to put an item in a given place on a partially loaded pallet, the robot must have free access to that place, i.e., the place must not be covered. A graph model and a formalized method for determining the sequence of putting goods on a pallet is proposed to avoid such collisions. It is also shown that not every packing pattern can be loaded by a robot. However, some pallet loading approaches have been identified that always guarantee a feasible robot packing.

Słowa kluczowe

EN

distributor’s pallet loading problem; robot packing; aggregated precedence graphs; extended topological sorting

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2024
• Tom: Vol. 34, No. 4
• Strony: 141--155
• Opis fizyczny: Bibliogr. 22 poz., rys.

Twórcy

autor

Pieńkosz Krzysztof

• Warsaw University of Technology, Institute of Control and Computation Engineering, Warsaw, Poland

• https://orcid.org/0000-0001-9437-7594

Bibliografia

• [1] Ali, S., Ramos, A. G., Carravilla, M. A., and Oliveira, J. F. On-line three-dimensional packing problems: A review of off-line and on-line solution approaches. Computers & Industrial Engineering 168 (2022), 108122.
• [2] Bonet Filella, G., Trivella, A., and Corman, F. Modeling soft unloading constraints in the multi-drop container loading problem. European Journal of Operational Research 308, 1 (2023), 336–352.
• [3] Bortfeldt, A., Gehring, H., and Mack, D. A parallel tabu search algorithm for solving the container loading problem.Parallel Computing 29, 5 (2003), 641–662.
• [4] Bortfeldt, A., and Wäscher, G. Constraints in container loading – a state-of-the-art review. European Journal of Operational Research 229, 1 (2013), 1–20.
• [5] Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. Introduction to Algorithms. The MIT Press, 2009.
• [6] Côté, J.-F., Gendreau, M., and Potvin, J.-Y. An exact algorithm for the two-dimensional orthogonal packing problem with unloading constraints. Operations Research 62, 5 (2014), 1126–1141.
• [7] Crainic, T. G., Perboli, G., and Tadei, R. Extreme point-based heuristics for three-dimensional bin packing. INFORMS Journal on Computing 20, 3 (2008), 368–384.
• [8] den Boef, E., Korst, J., Martello, S., Pisinger, D., and Vigo, D. Erratum to the three-dimensional bin packing problem: Robot-packable and orthogonal variants of packing problems. Operations Research 53, 4 (2005), 735–736.
• [9] Elhedhli, S., Gzara, F., and Yildiz, B. Three-dimensional bin packing and mixed-case palletization. INFORMS Journal on Optimization 1, 4 (2019), 323–352.
• [10] Fekete, S. P., and Schepers, J. A combinatorial characterization of higher-dimensional orthogonal packing. Mathematics of Operations Research 29, 2 (2004), 353–368.
• [11] Gzara, F., Elhedhli, S., and Yildiz, B. C. The pallet loading problem: three-dimensional bin packing with practical constraints. European Journal of Operational Research 287, 3 (2020), 1062–1074.
• [12] Lim, A., Rodrigues, B., and Wang, Y. A multi-faced buildup algorithm for three-dimensional packing problems. Omega 31, 6 (2003), 471–481.
• [13] Martello, S., Pisinger, D., and Vigo, D. The three-dimensional bin packing problem. Operations Research 48, 2 (2000), 256–267.
• [14] Martello, S., Pisinger, D., Vigo, D., den Boef, E., and Korst, J. Algorithm 864: General and robot-packable variants of the three-dimensional bin packing problem. ACM Transactions on Mathematical Software 33, 1 (2007), 7.
• [15] Martínez, D. A., Alvarez-Valdes, R., and Parreño, F. A grasp algorithm for the container loading problem with multi-drop constraints. Pesquisa Operacional 35, 1 (2015), 1–24.
• [16] Pollaris, H., Braekers, K., Caris, A., Janssens, G., and Limbourg, S. Vehicle routing problems with loading constraints: state-of-the-art and future directions. OR Spectrum 37, 2 (2015), 297–330.
• [17] Silva, E., Oliveira, J., and Wäscher, G. The pallet loading problem: a review of solution methods and computational experiments. International Transactions in Operational Research 23, 1-2 (2016), 147–172.
• [18] Silva, E. F., Toffolo, T. A. M., and Wauters, T. Exact methods for three-dimensional cutting and packing: A comparative study concerning single container problems. Computers & Operations Research 109 (2019), 12–27.
• [19] Wang, F., Tao, Y., and Shi, N. A survey on vehicle routing problem with loading constraints. In 2009 International Joint Conference on Computational Sciences and Optimization (Sanya, China, 2009), vol. 2, IEEE, pp. 602–606.
• [20] Zhao, X., Bennell, J. A., Bektas, T., and Dowsland, K. A comparative review of 3D container loading algorithms. International Transactions in Operational Research 23, 1-2 (2016), 287–320.
• [21] Zhu, W., Oon, W., Lim, A., and Weng, Y. The six elements to block-building approaches for the single container loading problem. Applied Intelligence 37 (2012), 431–445.
• [22] Zhu, W., Zhang, Z., Oon, W.-C., and Lim, A. Space defragmentation for packing problems. European Journal of Operational Research 222, 3 (2012), 452–463.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).