Algorytmy heurystyczne w trójwymiarowym zagadnieniu pakowania

• Autorzy: Chmiel W. , Kadłuczka P. , Wala K. , Jędrusik S.

Warianty tytułu

EN

Heuristic algorithm for three-dimensional packing problem

• Języki publikacji: PL

Abstrakty

PL

W artykule zaprezentowano zagadnienie trójwymiarowego pakowania kontenera paczkami o regularnych wymiarach, ze współczynnikiem wypełnienia kontenera jako kryterium oceny. Przebadano zarówno procedury konstrukcyjne, jak i algorytm popraw bazujący na algorytmie symulowanego wyżarzania. Stosowane w algorytmach rozwiązanie problemu pakowania jest reprezentowane w postaci czterech sekwencji liczb. W przedstawionych wynikach eksperymentów wykorzystano instancje testowe zawierające do 400 paczek.

EN

In this paper we examine the problem of optimal packing of a three-dimensional container with rectangular boxes such that the volume of the packed boxes is maximized. We investigate fast constructive procedures and an approximation algorithm based on simulated annealing. In all developed algorithms solutions are represented in a form of four sequences. Extensive computational results involving various test instances up to 400 boxes, are presented.

Słowa kluczowe

PL

trójwymiarowe zagadnienie pakowania; algorytmy konstrukcyjne; dyskretna optymalizacja; wyżarzanie symulowane

EN

three-dimensional knapsack problem; constructive algorithm; discrete optimization; simulated annealing

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2010
• Tom: T. 14, z. 3/2
• Strony: 827--840
• Opis fizyczny: Bibliogr. 14 poz., rys., wykr., tab.

Twórcy

autor

Chmiel W.

• Katedra Automatyki, Wydział EAIiE, Akademia Górniczo-Hutnicza w Krakowie

autor

Kadłuczka P.

• Katedra Automatyki, Wydział EAIiE, Akademia Górniczo-Hutnicza w Krakowie

autor

Wala K.

• Wyższa Szkoła Biznesu, Dąbrowa Górnicza

autor

Jędrusik S.

• Katedra Informatyki Stosowanej, Wydział Zarządzania, Akademia Górniczo-Hutnicza w Krakowie

Bibliografia

• [1] Aarts E.H.L., Verhoeven M., Local search, in Annotated bibliographies in Comhinatorial Optimi-zation. (Dell'Amico M., Maffioli F., Martello S., eds.), 1997 163-180.
• [2] Ausiello G., Crescenzi P., Gambosi G., Kann V., Marchetti-Spaccamela A., Protasi M., Complexity and Approximation: Combinatorial Optimization Problems and their Approximability Properties. 1999.
• [3] Chan F.T.S., Au K.C., Chan L.Y., Lau T.L., Using genetic algorithms to solve ąuality-related bin packing problem. Robotics and Computer-Integrated, 23, 1, 2007, 71-81.
• [4] Filipowicz B., Chmiel W., Kadłuczka P., Wala K., Kontur wypukły w trójwymiarowym zagadnieniu pakowania. Automatyka (półrocznik AGH), t. 14, z. 3/2, 2010.
• [5] Hochbaum D.H., ed., Approximation Algorithms for NP-Hard problems. PWS Publishing Corapa-ny, r. 9, 1997.
• [6] Lodi A., Martello S., Vigo D., TSpack: A Unified Tabu Search Code for Multi-Dimensional Bin Packing Problems. Annals of Operations Research, 131, 2004, 203-213.
• [7] Matsumoto M., Nishimura T., Mersenne twister: a 623-dimensionally eąuidistributed uniform pseudorandom number generator. ACM Trans. Model. Comput. Simul., 8, 3, 1998.
• [8] Michalewicz Z., Fogel D.B., How to solve it: Modern Heuristics. Springer-Verlag, Berlin, Heidelberg, 2004.
• [9J Miyazawa F.K., Wakabayashi V., Polynomial approximation algorithms for the orthogonś z oriented 3D packing problem. Technical Report RT-MAC-9512, Instituto de Matematica e Estatica , Universidade de Sao Paulo, 1995.
• [10] Pisinger D., Heuristics for the container loading problem. European Journal of Operational Research, 141, 2, 2002, 382-392.
• [11] Pisinger D., Egeblad J., Heuristic approaches for the two- and three-dimensional knapsack packing problem. Computers & Operations Research, vol. 36, 4, 2009, 1026-1049.
• [12] Scheithauer G., A three dimensional bin packing algorithm. Journal of Information Processing and Cybernetics, 27, 1991, 263-271.
• [13] Vazirani V.V., Approximation Algorithms. Springer-Verlag, Berlin, 2003.
• [14] Yamada T., Takeoka T., An exact algorithm for the fixed-charge multiple knapsack problem. European Journal of Operational Research, 192, 2, 2009, 700-705.