روشی برای حل مساله بارگیری پالت توزیع‌کننده با استفاده از برنامه‌ریزی پویا

نوع مقاله : مقاله پژوهشی

نویسنده

دکتری مهندسی صنایع؛ دانشگاه علم و صنعت، عضو هیئت علمی پژوهشگاه صنعت نفت

چکیده

در مساله بارگیری پالت توزیع‌کننده، زیرمجموعه‌ای از مستطیل‌های مختلف (جعبه‌ها) با ارزش‌های وزنی متفاوت که روی یک فضای مستطیل‌شکل (پالت) چیده شوند مدنظراست، به‌طوری که مجموع ارزش وزنی جعبه‌های چیده شده، بیشینه شود. هم‌چنین برای کاربردی‌تر شدن طرح چیدمان به‌دست‌آمده، در قالب تابع هدف دوم مساله، مدنظر است که تا جای ممکن جعبه‌های هم‌نوع در کنار یکدیگر چیده شوند. مقاله حاضر روشی را برای حل این مساله ارائه می‌دهد که ایده‌ای جدید در به‌کارگیری برنامه‌ریزی پویا است. این روش شامل کالبدی حلقوی است به‌طوری که در هر دور از فرایند الگوریتم، بخشی از پالت، چیده می‌شود. تحلیل مقایسه‌ای انجام‌شده نشان می‌دهد که روش پیشنهادی، در شرایطی که زمان حل، مهم‌تر از ارزش وزنی چیدمان باشد، در موقعیت بهتری نسبت به‌روش‌های موجود قرار دارد. هم‌چنین مثال‌های حل ‌شده نشان می‌دهند که از نظر چیدمان جعبه‌های هم‌‌نوع در کنار یکدیگر، روش پیشنهادی نسبت به‌روش‌های موجود، بهتر است.

کلیدواژه‌ها

عنوان مقاله [English]

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

نویسنده [English]

  • Mohammad Ali Hatefi
چکیده [English]

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.

کلیدواژه‌ها [English]

  • Cutting & Packing (C&P) problems
  • Distributor’s Pallet Loading Problem (DPLP)
  • Dynamic programming

مراجع

[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.

فایل ها

هم رسانی

ارجاع به این مقاله

آمار