Mục tiêu của các vấn đề về packing là tìm ra cách tốt nhất để đóng gói một tập hợp các mục có kích thước nhất định vào các vùng chứa có packing cố định. Một ứng dụng điển hình là chất tải các thùng lên xe tải giao hàng một cách hiệu quả. Thông thường, bạn không thể đóng gói tất cả các mặt hàng do những hạn chế về dung lượng. Trong trường hợp đó, vấn đề là phải tìm một tập hợp con các mục có tổng kích thước tối đa sẽ vừa với vùng chứa.
Có nhiều loại vấn đề về đóng gói. Hai trong số các vấn đề quan trọng nhất là vấn đề về ba lô và việc đóng gói thùng rác.
Bài toán về Knapsack
Trong bài toán đơn giản về chiếc ba lô, có một vật chứa duy nhất (ba lô). Các mục có giá trị cũng như kích thước và mục tiêu là đóng gói một tập hợp con các mục có tổng giá trị tối đa.
Đối với trường hợp đặc biệt khi giá trị bằng kích thước, mục tiêu là tối đa hoá tổng kích thước của các mặt hàng được đóng gói.
OR-Tools cung cấp một số cách giải quyết cho các vấn đề về túi ba lô trong thư viện thuật toán.
Ngoài ra, còn có nhiều phiên bản chung hơn của vấn đề đeo ba lô. Dưới đây là một số ví dụ:
Vấn đề ba lô đa chiều, trong đó các mặt hàng có nhiều hơn một số lượng vật lý, chẳng hạn như trọng lượng và thể tích, đồng thời chiếc ba lô có sức chứa cho mỗi số lượng. Ở đây, thuật ngữ phương diện không nhất thiết đề cập đến các kích thước không gian thông thường như chiều cao, chiều dài và chiều rộng. Tuy nhiên, một số vấn đề có thể liên quan đến kích thước không gian, ví dụ: tìm cách tối ưu để đóng gói các hộp hình chữ nhật vào thùng chứa hình chữ nhật.
Nhiều vấn đề về ba lô, trong đó có nhiều ba lô và mục tiêu là tăng tối đa tổng giá trị của các mặt hàng được đóng gói trong tất cả các ba lô.
Xin lưu ý rằng bạn có thể gặp vấn đề đa chiều với một chiếc ba lô duy nhất hoặc vấn đề về nhiều ba lô chỉ với một chiều.
Vấn đề về việc đóng gói thùng rác
Một trong những vấn đề đóng gói phổ biến nhất là bin-packing, trong đó có nhiều vùng chứa (gọi là bin-packing) có dung lượng bằng nhau. Không giống như vấn đề nhiều chiếc ba lô, số lượng túi không được cố định. Thay vào đó, mục tiêu là tìm số lượng thùng nhỏ nhất có thể chứa tất cả các mục.
Dưới đây là ví dụ đơn giản để minh hoạ sự khác biệt giữa vấn đề nhiều túi knapsack và vấn đề đóng gói thùng rác. Giả sử một công ty có xe tải giao hàng, mỗi chiếc có tải trọng 18.000 pound và 130.000 pound các mặt hàng cần giao.
Nhiều ba lô: Bạn có 5 chiếc xe tải và muốn tải một nhóm nhỏ các món hàng có trọng lượng tối đa lên chúng.
Đóng thùng: Bạn có 20 xe tải (đủ để chứa tất cả các mặt hàng) và bạn muốn sử dụng ít xe tải nhất có thể chứa được tất cả các mặt hàng đó.
Các phần sau đây cho biết cách giải quyết các loại vấn đề đóng gói bằng OR-Tools, bắt đầu từ vấn đề ba lô.