Kontur wypukły w trójwymiarowym zagadnieniu pakowania

• Autorzy: Filipowicz B. , Chmiel W. , Kadłuczka P. , Wala K.

Warianty tytułu

EN

Convex contour for 3D bin packing problem

• Języki publikacji: PL

Abstrakty

PL

W pracy przedstawiono uniwersalną metodę opisu konturu i zbioru punktów wstawienia, która może być stosowana dla szerokiej klasy zagadnień pakowania paczek do kontenera w ujęciu dwu- i trójwymiarowym, przy zadanym punkcie "centralnym". Punkt ten określa miejsce wstawienia pierwszej paczki i daje możliwość stworzenia szeregu algorytmów zachłannych działających odmiennie od tych, które rozpoczynają pakowanie od lewego, dolnego, tylnego rogu kontenera. Pozwala to w trakcie załadunku rozwiązywać dodatkowo istotny problem wyważenia kontenera.

EN

The paper presents an universal method for describing of contour and insertion points that can be applied do wide class of packing problems including two and three dimensional problems with a fixed central point. The central point speeifies a place of insertion of a first package. This gives the opportunity to create several greedy algorithms acting differently from the standard algorithm, which starts packing from the left, bottom, rear corner of the container. Moreover it allows to solve container balancing problem.

Słowa kluczowe

PL

trójwymiarowe zagadnienie pakowania; kontur wypukły

EN

3D bin packing problem; convex contour

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

Twórcy

autor

Filipowicz B.

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

autor

Chmiel W.

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

autor

Kadłuczka P.

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

autor

Wala K.

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

Bibliografia

• [1] Bansal N., Sviridenko M., New approximability and inapproximability results for 2-dimensional Bin Packing. Proc. of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, 2004.
• [2] Bischoff E., Ratcliff M.S.W., Loading multiple pallets. The Journal of the Operational Research Society, vol. 46, 11, 1995, 1322-1336.
• [3] Bischoff E., Janetz F., Ratcliff M.S.W., Loading pallets with non-identical items. European Journal of Operational Research 84, 1995, 681-692.
• [4] Chen C.S., Lee S.M., Shen Q.S., An analytical model for the container loading problem. Euro pean Journal of Operational Research, 80, 1, 1995, 68-76.
• [5] Dembo R.S., Hammer P.L., A reduction algorithm for knapsack problems. Methods of Operations Research, 36, 1980, 49-60.
• [6] Dyckhoff H., A typology ofcutting and packing problems. European Journal of Operational Research, 44, 1990, 145-159.
• [7] Dyckhoff H., Scheithauer G., Terno J., Cutting and Packing {C&P). In: M. Dell'Amico, F. Maffioli, and S. Martello, editors, Annotated Bibliographies in Combinatorial Optimization. John Wiley & Sons, Chichester, 1997.
• [8] Faroe O., Pisinger D., Zachariasen M., Cuided Local Search for the Three-Dimensional Bin Packing Problem. INFORMS Journal on Computing, 1999.
• [9] Gehring H., Bortfeld A., A genetic algorithm for solving the container loading problem. International Transactions of Operational Research, 4, 1997.
• [10] Gehring M., Menscher K. Meyer M., A computer-based heuristics for packing poole shipment containers. EJOR, 44, 1990, 277-288.
• [11] Marello S., Toth P., Knapsack Problem: Algorithms and computer implementation. Wiley, Chichester, 1990.
• [12] Martello S., Pisinger S., Vigo D., The Three-Dimensional Bin Packing Problem. Operations Research, 48, 2, 2000, 256-267.
• [13] Pisinger D., An exact algorithm for large multiple knapsack problems. European Journal of Operational Research, 114, 1999, 528-541.
• [14] Pisinger D., Heuristics for the container loading problem. European Journal of Operational Research, 141, 2, 2002, 382-392.
• [15] Scheithauer G., Heuristics for the container loading problem. European Journal of Operational Research, Springer-Verlag, 1991.
• [16] Scheithauer G., A three dimensional bin packing algorithm. Journal of Information Processing and Cybernetics, 27, 1991, 263-271.
• [17] Yamada T., Takeoka T., An exact algorithm for the fixed-charge multiple knapsack problem. European Journal of Operational Research, 192, 2, 2009, 700-705.