الهدف من مسائل packing هو العثور على أفضل طريقة لتجميع مجموعة من العناصر ذات الأحجام المحدّدة في حاويات ذات packing ثابتة. التطبيق النموذجي هو تحميل الصناديق على شاحنات التوصيل بكفاءة. غالبًا ما لا يمكن تعبئة جميع العناصر بسبب قيود السعة. في هذه الحالة، تكمن المشكلة في العثور على مجموعة فرعية من العناصر ذات الحد الأقصى للحجم الإجمالي الذي يتناسب مع الحاويات.
هناك أنواع عديدة من مشاكل التغليف. اثنان من الحالات الأكثر أهمية هما مشاكل الحقائب الرأسية وتعبئة السلال.
مشاكل في الظهر
في مشكلة حقيبة الظهر البسيطة، توجد حاوية واحدة (حقيبة ظهر). تحتوي السلع على قيم بالإضافة إلى مقاسات، والهدف من ذلك هو تجميع مجموعة فرعية من السلع التي تم بلوغ أقصى قيمة إجمالية لها.
بالنسبة للحالة الخاصة التي تكون فيها القيمة تساوي الحجم، يكون الهدف هو زيادة الحجم الإجمالي للسلع المعبأة.
توفّر OR-Tools العديد من أدوات حلّ مسائل الوجبات السريعة في مكتبة الخوارزميات.
هناك أيضًا إصدارات أكثر عمومية من مشكلة حقيبة الظهر. فيما يلي بعض الأمثلة:
مشاكل حقيبة الظهر المتعدّدة الأبعاد: تتضمّن البضائع أكثر من كمية واحدة، مثل الوزن والحجم، وتتّسع الحقيبة لكل كمية منها. في هذه الحالة، لا يشير مصطلح البُعد بالضرورة إلى الأبعاد المكانية المعتادة للطول والطول والعرض. مع ذلك، قد تتضمن بعض المشاكل الأبعاد المكانية، على سبيل المثال، إيجاد الطريقة الأمثل لوضع الصناديق المستطيلة في سلة تخزين مستطيلة.
مشاكل متعددة في حقيبة الظهر: يتم فيها عرض العديد من الحقائب، والهدف من ذلك هو زيادة القيمة الإجمالية للحقيبة في جميع الحقائب.
لاحظ أنه قد يكون لديك مشكلة متعددة الأبعاد في حقيبة ظهر واحدة، أو مشكلة في حقيبة ظهر متعددة ذات بُعد واحد فقط.
مشكلة في تغليف السلال
تُعدّ عملية bin-packing من أبرز مشاكل التغليف التي تتضمّن حاويات متعددة (تُسمّى bin-packing) ذات سعة متساوية. بخلاف مشكلة حقائب الظهر المتعددة، لا يتم إصلاح عدد السلال. بدلاً من ذلك، فإن الهدف هو العثور على أصغر عدد من السلال التي ستحمل جميع العناصر.
فيما يلي مثال بسيط لتوضيح الفرق بين مشكلة حقيبة الظهر المتعددة ومشكلة تغليف السلال. لنفترض أن شركة لديها شاحنات توصيل، ولكل منها وزن يبلغ 18000 رطل، و130000 رطل من العناصر للتسليم.
حقيبة ظهر متعددة: لديك خمس شاحنات وتريد تحميل مجموعة فرعية من العناصر التي لها أقصى وزن عليها.
تعبئة الصناديق: لديك 20 شاحنة (أكثر من كافية لاستيعاب جميع العناصر) وتريد استخدام أقل عدد من الشاحنات التي ستحملها جميعًا.
توضّح الأقسام التالية طريقة حل أنواع مختلفة من مشاكل التعبئة باستخدام OR-Tools، بدءًا من مشكلة حقيبة الظهر.