هدف از مشکلات بسته بندی یافتن بهترین راه برای بسته بندی مجموعه ای از اقلام با اندازه های معین در ظروف با ظرفیت های ثابت است. یک برنامه معمولی بارگیری جعبه ها بر روی کامیون های تحویل کارآمد است. اغلب، به دلیل محدودیت ظرفیت، امکان بسته بندی همه اقلام وجود ندارد. در آن صورت، مشکل پیدا کردن زیرمجموعه ای از اقلام با حداکثر اندازه کل است که در ظروف جا می شود.
مشکلات بسته بندی انواع مختلفی دارد. دو مورد از مهمترین آنها مشکلات کوله پشتی و بسته بندی سطل هستند.
مشکلات کوله پشتی
در مسئله کوله پشتی ساده، یک ظرف (یک کوله پشتی) وجود دارد. اقلام دارای مقادیر و همچنین اندازه هستند و هدف این است که زیرمجموعه ای از آیتم ها را بسته بندی کنیم که دارای حداکثر ارزش کل باشد.
در مورد خاصی که در آن مقدار برابر با اندازه است، هدف حداکثر کردن اندازه کل اقلام بسته بندی شده است.
OR-Tools چندین حل کننده برای مسائل کوله پشتی در کتابخانه الگوریتم های خود ارائه می دهد.
همچنین نسخه های کلی تری از مشکل کوله پشتی وجود دارد. در اینجا چند نمونه وجود دارد:
مسائل کوله پشتی چند بعدی که در آن اقلام دارای بیش از یک کمیت فیزیکی مانند وزن و حجم هستند و کوله پشتی برای هر کمیت ظرفیت دارد. در اینجا، اصطلاح بعد لزوماً به ابعاد فضایی معمول ارتفاع، طول و عرض اشاره نمی کند. با این حال، برخی از مشکلات ممکن است شامل ابعاد فضایی باشد، به عنوان مثال، یافتن راه بهینه برای بسته بندی جعبه های مستطیلی در یک سطل ذخیره سازی مستطیلی.
مشکلات چندگانه کوله پشتی ، که در آن چند کوله پشتی وجود دارد و هدف این است که ارزش کل اقلام بسته بندی شده در همه کوله ها را به حداکثر برسانید.
توجه داشته باشید که شما می توانید یک مشکل چند بعدی با یک کوله پشتی یا یک مشکل چند بعدی فقط با یک بعد داشته باشید.
مشکل سطل بسته بندی
یکی از شناخته شده ترین مشکلات بسته بندی، بسته بندی بن است که در آن چندین ظروف (به نام سطل ) با ظرفیت یکسان وجود دارد. بر خلاف مشکل چند کوله پشتی، تعداد سطل ها ثابت نیست. در عوض، هدف یافتن کمترین تعداد سطل‌هایی است که همه موارد را در خود جای دهد.
در اینجا یک مثال ساده برای نشان دادن تفاوت بین مشکل کوله پشتی چندگانه و مشکل بسته بندی زباله وجود دارد. فرض کنید یک شرکت کامیون های حمل و نقل دارد که هر کدام از آنها ظرفیت وزنی 18000 پوندی و 130000 پوند اقلام برای تحویل دارند.
کوله پشتی چندگانه: شما پنج کامیون دارید و می خواهید زیرمجموعه ای از اقلامی را که حداکثر وزن را دارند روی آن ها بارگیری کنید.
بسته بندی سطل زباله: شما 20 کامیون دارید (بیش از اندازه کافی برای نگهداری همه وسایل) و می خواهید از کمترین کامیونی استفاده کنید که همه آنها را در خود جای دهد.
بخش‌های زیر نحوه حل انواع مشکلات بسته‌بندی با OR-Tools را نشان می‌دهند، که با مشکل کوله پشتی شروع می‌شود.