המטרה של בעיות packing היא למצוא את הדרך הטובה ביותר לארוז קבוצות פריטים בגדלים מסוימים בקונטיינרים עם packing קבועה. אפליקציה אופיינית היא העמסה יעילה של ארגזים על משאיות אספקה. לעיתים קרובות אי אפשר לארוז את כל הפריטים בגלל מגבלות הקיבולת. במקרה כזה, הבעיה היא למצוא קבוצת משנה של הפריטים עם הגודל הכולל המקסימלי שיתאימו לקונטיינרים.
יש סוגים רבים של בעיות אריזה. שתיים מהבעיות החשובות ביותר הן בעיות באיסוף עצמי והכנסת סלים.
בעיות ב-Knapsack
בבעיה הפשוטה של תיק הנשיאה, יש מכל אחד (תיק נשיאה אחד). לפריטים יש ערכים וגם מידות, והמטרה היא לדחוס קבוצת משנה של הפריטים עם הערך הכולל המקסימלי.
במקרה המיוחד שבו הערך שווה לגודל, המטרה היא למקסם את הגודל הכולל של הפריטים הארוזים.
OR-Tools מספק כמה פתרונות לבעיות תיקי גב בספריית האלגוריתמים שלו.
קיימות גם גרסאות כלליות יותר של בעיית תיקי האחיזה. הנה כמה דוגמאות:
בעיות רב-ממדיות בתיק גב, שבהן יש לפריטים יותר מכמות פיזית אחת, כמו משקל ונפח, ויש גם קיבולת לכל כמות. במקרה זה, המונח מאפיין לא מתייחס בהכרח לממדים המרחביים הרגילים של גובה, אורך ורוחב. עם זאת, חלק מהבעיות עשויות לכלול מימדים מרחביים, למשל, מציאת הדרך האופטימלית לארוז תיבות מלבניות בפח אחסון מלבני.
בעיות רבות באיסוף עצמי, שבהן יש כמה תיקי יד, והמטרה היא למקסם את הערך הכולל של הפריטים הארוזים בכל הפריטים.
שימו לב שיכולה להיות בעיה רב-מימדית בתיק יחיד, או בעיה גדולה בתיק יחיד, או בעיה גדולה במימד אחד בלבד.
הבעיה באריזה של סל (bin-packing)
אחת מהבעיות הידועות ביותר לאריזה היא bin-packing, שבה יש כמה קונטיינרים (שנקראים bins) עם קיבולת זהה. בניגוד לבעיה של ריבוי תיקי נשיאה, מספר הפולים לא קבוע. במקום זאת, המטרה היא למצוא את המספר הקטן ביותר של סלים שמכילים את כל הפריטים.
הדוגמה הבאה ממחישה את ההבדל בין ריבוי תיקי נשיאה לבין בעיית אריזת סלים. נניח שלחברה מסוימת יש משאיות אספקה, שלכל אחת מהן יש משקל של 18,000 ק"ג ו-130,000 ק"ג של פריטים.
תרמיל גב: יש לכם חמש משאיות וברצונכם להעמיס חלק מהפריטים עם המשקל המקסימלי.
אריזה לפח: יש לכם 20 משאיות (יותר מ-20 משאיות) ואתם רוצים להשתמש בכמות קטנה ככל האפשר של משאיות.
בקטעים הבאים מוסבר איך לפתור סוגים שונים של בעיות אריזה עם OR-Tools, החל מבעיית תיקי האחיזה.