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

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

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

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.