মোড়ক

প্যাকিং সমস্যাগুলির লক্ষ্য হল নির্দিষ্ট ক্ষমতা সহ পাত্রে প্রদত্ত আকারের আইটেমগুলির একটি সেট প্যাক করার সর্বোত্তম উপায় খুঁজে বের করা। একটি সাধারণ অ্যাপ্লিকেশন হল ডেলিভারি ট্রাকে দক্ষতার সাথে বাক্সগুলি লোড করা। প্রায়শই, ক্ষমতার সীমাবদ্ধতার কারণে সমস্ত আইটেম প্যাক করা সম্ভব হয় না। সেই ক্ষেত্রে, সমস্যাটি হল সর্বাধিক মোট আকারের আইটেমগুলির একটি উপসেট খুঁজে পাওয়া যা পাত্রে ফিট হবে।

অনেক ধরনের প্যাকিং সমস্যা আছে। সবচেয়ে গুরুত্বপূর্ণ দুটি হল ন্যাপস্যাক সমস্যা এবং বিন প্যাকিং ।

ন্যাপস্যাকের সমস্যা

সাধারণ ন্যাপস্যাক সমস্যায়, একটি একক ধারক (একটি ন্যাপস্যাক) আছে। আইটেমগুলির মানগুলির পাশাপাশি আকারও রয়েছে এবং লক্ষ্য হল আইটেমগুলির একটি উপসেট প্যাক করা যার সর্বাধিক মোট মান রয়েছে৷

বিশেষ ক্ষেত্রে যার মান আকারের সমান, লক্ষ্য হল প্যাক করা আইটেমগুলির মোট আকার সর্বাধিক করা।

OR-Tools এর অ্যালগরিদম লাইব্রেরিতে ন্যাপস্যাক সমস্যার জন্য বেশ কয়েকটি সমাধান প্রদান করে।

ন্যাপস্যাক সমস্যার আরও সাধারণ সংস্করণ রয়েছে। এখানে উদাহরণ তুলে ধরা হলো:

• বহুমাত্রিক ন্যাপস্যাকের সমস্যা , যেখানে আইটেমগুলির একাধিক শারীরিক পরিমাণ থাকে, যেমন ওজন এবং আয়তন, এবং ন্যাপস্যাকের প্রতিটি পরিমাণের জন্য একটি ক্ষমতা থাকে। এখানে, মাত্রা শব্দটি অগত্যা উচ্চতা, দৈর্ঘ্য এবং প্রস্থের স্বাভাবিক স্থানিক মাত্রাগুলিকে নির্দেশ করে না। যাইহোক, কিছু সমস্যা স্থানিক মাত্রা জড়িত হতে পারে, উদাহরণস্বরূপ, একটি আয়তক্ষেত্রাকার স্টোরেজ বিনে আয়তক্ষেত্রাকার বাক্স প্যাক করার সর্বোত্তম উপায় খুঁজে বের করা।

• একাধিক ন্যাপস্যাক সমস্যা , যেখানে একাধিক ন্যাপস্যাক রয়েছে এবং লক্ষ্য হল সমস্ত ন্যাপস্যাকে প্যাক করা আইটেমগুলির মোট মান সর্বাধিক করা।

মনে রাখবেন যে আপনার একটি একক ন্যাপস্যাকের সাথে একটি বহুমাত্রিক সমস্যা বা শুধুমাত্র একটি মাত্রার সাথে একাধিক ন্যাপস্যাকের সমস্যা হতে পারে৷

বিন প্যাকিং সমস্যা

সবচেয়ে সুপরিচিত প্যাকিং সমস্যাগুলির মধ্যে একটি হল বিন-প্যাকিং , যেখানে সমান ক্ষমতার একাধিক পাত্র ( বিন বলা হয়) থাকে। একাধিক ন্যাপস্যাক সমস্যার বিপরীতে, বিনের সংখ্যা স্থির নয়। পরিবর্তে, লক্ষ্য হল ক্ষুদ্রতম সংখ্যক বিন খুঁজে বের করা যা সমস্ত আইটেম ধারণ করবে।

একাধিক ন্যাপস্যাক সমস্যা এবং বিন-প্যাকিং সমস্যার মধ্যে পার্থক্য ব্যাখ্যা করার জন্য এখানে একটি সহজ উদাহরণ। ধরুন একটি কোম্পানীর ডেলিভারি ট্রাক আছে, যার প্রতিটির 18,000 পাউন্ড ওজন ক্ষমতা এবং 130,000 পাউন্ড আইটেম ডেলিভারি করতে হবে।

• একাধিক ন্যাপস্যাক: আপনার কাছে পাঁচটি ট্রাক আছে এবং আপনি আইটেমগুলির একটি উপসেট লোড করতে চান যার সর্বোচ্চ ওজন রয়েছে।

• বিন প্যাকিং: আপনার কাছে 20টি ট্রাক রয়েছে (সমস্ত আইটেম রাখার জন্য যথেষ্ট বেশি) এবং আপনি সবচেয়ে কম ট্রাকগুলি ব্যবহার করতে চান যা সেগুলিকে ধরে রাখবে।

নিম্নলিখিত বিভাগগুলি দেখায় কিভাবে OR-Tools দিয়ে বিভিন্ন ধরনের প্যাকিং সমস্যা সমাধান করা যায়, ন্যাপস্যাক সমস্যা থেকে শুরু করে।