A Technique for Solving Distributor’s Pallet Loading Problem (DPLP), Using Dynamic Programming

Document Type : Research Article

Author

Abstract

The Distributor’s Pallet Loading Problem consists of packing a fixed rectangular space (so-called pallet) with a subset of smaller rectangular shapes (so-called pieces) of different dimensions, which have different utility values, in such a way as to maximize the sum of the utility values of the packed pieces. Moreover,  as the further objective function; it requires to as possible pack identical pieces as side by side, by means of applicability of the packing patterns. The present paper introduces a technique to solve the problem, in the way that includes a new idea to apply the dynamic programming and, as a matter of the second objective function. In each round of the proposed packing procedure loop, a part of pallet space is packed. The experimental results show that the proposed technique is better than the present methods in the state-of-the art, one the one hand, if solving time were better than packing value, on the other hand, as for packing identical pieces as side by side.

Keywords

References

[1] Beasley, J.E.; “An exact two-dimensional non-guillotine cutting tree search procedure”, Operations Research, vol. 33, p.p. 49-64, 1985.
[2] Cui, Y.; Yang, Y.; “A heuristic for the one-dimensional cutting stock problem with usable leftover”, European Journal of Operational Research, vol. 204(2), p.p. 245-250, 2010.
[3] Bishoff, E.E.; Dowsland, W.B.; “An application of the micro to product design and distribution”, Journal of Operational Research Society, vol. 33, p.p. 271-280, 1982.
[4] Browne, D.J.; “An improved BL lower bound”, Information Process Letters, vol. 11, p.p. 37-39, 1980.
[5] Caprara, A.; Monaci, M.; “On the two-dimensional knapsack problem”, Operations Research Letters, vol. 32, p.p. 5–14, 2004.
[6] Chen, C.S.; Sarin, S.; Ram, B.; “The pallet packing for un-uniform box sizes”, International Journal of Production Research, vol. 29, p.p. 1963-1968, 1991.
[7] Dychoff, H.; “A typology of cutting and packing problems”, European Journal of Operational Research, vol. 44, p.p. 145-159, 1990.
[8] George, J.A.; Rabinson, D.F.; “A heuristic for packing boxes into a container”, Computers & Operation Research, vol. 7, p.p. 147-156, 1980.
[9] Hertz, J.; “A recursive computing procedure for two-dimensional stock-cutting”, IBM Journal of Research, vol. 16, p.p. 462-469, 1972.
[10] Glaydston, M.R.; Luiz, A.N.L.; “Lagrangean relaxation with clusters and column generation for the manufacturer's pallet loading problem Generating unconstrained two-dimensional non-guillotine cutting patterns by a recursive partitioning algorithm”, Computers and Operations Research, vol. 34(9), p.p. 2695-2708, 2007.
[11] Lipnitskij, A.A.; “Use of genetic algorithms for solution of the rectangle-packing problem”, Cybernetics and Systems Analysis, vol. 38(6), p.p. 943–946, 2002.
[12] Dereliand, T.; Sena, D.; “A hybrid bee(s) algorithm for solving container loading problems”, Applied Soft Computing, vol. 11(2), p.p. 2854–2862, 2011.
[13] Scheithauer, G.; Sommerweiss, U.; “4-Block heuristic for the rectangle-packing problem”, European Journal of Operational Research, vol. 108, p.p. 529–526, 1998.
[14] Shigehiro, Y.; Koshiyama, S.; Masuda, T.; “New approach to rectangle packing problem based on stochastic tabu search”, Transactions of the Society of Instrument and Control Engineers, vol. 40(7), p.p. 747-754, 2004.
[15] Tsai, R.D.; Maelstrom, E.M.; Kuo, W.; “Three-dimensional palletization of mixed box sizes”, IIE Transactions, vol. 25(4), p.p. 64-75, 1993.
[16] Tsai, R.D.; Maelstrom, E.M.; & Meeks, H.D.; “A two-dimensional palletizing procedure for warehouse loading operations”, IIE Transactions, vol. 20, p.p. 418-425, 1998.
[17] Macedo, R.; Alves, C.; Decarvalho, V.; “Arc-flow model for the two-dimensional guillotine cutting stock problem”, Computers and Operations Research, vol. 37(6), p.p. 991–1001, 2010.
[18] Wascher, G.; Haubner, H.; Schumann H. “An improved typology of cutting and packing problems”, European Journal of Operational Research, vol. 183, p.p. 1109–1130, 2007.
[19] Chen, M.; Huang, W.; “A two-level search algorithm for 2D rectangular packing problem”, Computers and Industrial Engineering, vol. 53, p.p. 123–136, 2007.
Amirkabir Journal of Mechanical Engineering
Volume 44, Issue 2 - Serial Number 2
February 2013
Pages 121-130

Files

Share

How to cite

Statistics