การบรรจุหีบห่อ

เป้าหมายของปัญหาpackingคือการค้นหาวิธีที่ดีที่สุดในการบรรจุชุดสินค้าตามขนาดที่กำหนดลงในคอนเทนเนอร์ที่มีpackingคงที่ การใช้งานทั่วไปคือการโหลดกล่องขึ้นรถบรรทุกอย่างมีประสิทธิภาพ โดยส่วนใหญ่แล้ว จะไม่สามารถบรรจุสินค้าได้ทั้งหมดเนื่องจากข้อจำกัดด้านความจุ ในกรณีดังกล่าว ปัญหาคือการค้นหาสินค้าบางส่วนที่มีขนาดรวมสูงสุดซึ่งพอดีกับคอนเทนเนอร์

ปัญหาในการบรรจุหีบห่อมีหลายประเภท สิ่งสำคัญที่สุด 2 ประการคือ ปัญหาของกระเป๋าเป้และการบรรจุหีบห่อ

ปัญหาเกี่ยวกับ Knapsack

ในโจทย์กระเป๋าเป้สะพายหลังที่เรียบง่ายจะมีคอนเทนเนอร์เดียว (กระเป๋าสะพายข้าง) สินค้าต่างๆ จะมีค่าและขนาด โดยมีเป้าหมายคือการรวมสินค้าบางส่วนที่มีมูลค่ารวมสูงสุด

ในกรณีพิเศษที่ค่าเท่ากับขนาด เป้าหมายคือการเพิ่มขนาดรวมของสินค้าที่บรรจุให้สูงสุด

OR-Tools จะช่วยแก้ปัญหาต่างๆ เกี่ยวกับ Knapsack ได้ในคลังอัลกอริทึม

นอกจากนี้ยังมีโจทย์ปัญหาสะพายหลังเวอร์ชันทั่วไปเพิ่มเติมด้วย ลองดูตัวอย่างต่อไปนี้

• ปัญหากระเป๋าสะพายหลังที่มีหลายมิติ ซึ่งสินค้ามีปริมาณที่จับต้องได้มากกว่า 1 รายการ เช่น น้ำหนักและปริมาณ และกระเป๋าบรรจุมีความจุสำหรับแต่ละจำนวน ในที่นี้ คำว่า ส่วนข้อมูล ไม่จำเป็นต้องหมายถึงมิติเชิงพื้นที่ อย่างปกติของความสูง ความยาว และความกว้าง แต่ปัญหาบางอย่างอาจเกี่ยวข้องกับมิติเชิงพื้นที่ เช่น การค้นหาวิธีที่เหมาะสมที่สุดในการบรรจุกล่องสี่เหลี่ยมผืนผ้าลงในถังเก็บของทรงสี่เหลี่ยมผืนผ้า

• โจทย์เกี่ยวกับกระเป๋าเป้หลายใบ ซึ่งมีกระเป๋าสะพายข้างอยู่หลายใบ และ เป้าหมายคือการเพิ่มมูลค่าของสินค้าในแพ็กทั้งหมดให้ได้สูงสุด

โปรดทราบว่าคุณสามารถมีปัญหาหลายมิติกับกระเป๋าสะพายใบเดียว หรือปัญหาเกี่ยวกับกระเป๋าเป้สะพายหลังหลายมิติที่มีมิติข้อมูลเพียงมิติเดียว

ปัญหาเกี่ยวกับการบรรจุหีบห่อ

ปัญหาด้านการบรรจุหีบห่อที่เป็นที่รู้จักมากที่สุดอย่างหนึ่งคือbin-packing ซึ่งจะมีคอนเทนเนอร์หลายใบ (เรียกว่าbin-packing) ที่ความจุเท่ากัน จำนวนถังไม่ได้รับการแก้ไข ซึ่งต่างจากปัญหากระเป๋าสะพายหลังจำนวนมาก แต่ให้หาถังขยะที่น้อยที่สุดที่จะเก็บสินค้าทุกชิ้นไว้

ต่อไปนี้เป็นตัวอย่างง่ายๆ เพื่อแสดงให้เห็นความแตกต่างระหว่างปัญหากระเป๋าสะพายข้างจำนวนมากและปัญหาการบรรจุหีบห่อ สมมติว่าบริษัทหนึ่งมีรถบรรทุก แต่ละคันมีน้ำหนัก 18,000 ปอนด์และสินค้าต้องส่งหนัก 130,000 ปอนด์

• กระเป๋าเป้หลายใบ: คุณมีรถบรรทุก 5 คัน และคุณต้องการโหลดสินค้าส่วนหนึ่งที่มีน้ำหนักสูงสุดลงในรถบรรทุกเหล่านั้น

• การบรรจุหีบห่อ: คุณมีรถบรรทุก 20 คัน (มากเกินพอที่จะเก็บของได้ทั้งหมด) และคุณต้องการใช้รถบรรทุกให้น้อยที่สุดที่จะจุได้ทั้งหมด

ส่วนต่อไปนี้จะแสดงวิธีแก้ปัญหาการบรรจุหีบห่อประเภทต่างๆ ด้วย "หรือ" เครื่องมือ โดยเริ่มจากปัญหาเกี่ยวกับกล่องบรรจุหีบห่อ