Thuật toán cho quy hoạch vùng chứa

Question

OK các bạn có vấn đề thực tế, và tôi cần một số thuật toán để tìm ra.
Chúng tôi có một loạt các đơn đặt hàng chờ đợi để được vận chuyển, mỗi đơn hàng sẽ có một khối lượng (trong feet khối), chúng ta hãy nói, V1, V2, V3, ..., Vn

Hãng vận chuyển có thể cung cấp cho chúng bốn loại thùng chứa và khối lượng/giá của các vùng chứa được liệt kê bên dưới:

Loại thùng chứa 1: 2700 CuFt/$ 2500;
Loại vùng chứa 2: 2350 CuFt/$ 2200;
Loại vùng chứa 3: 2050 CuFt/$ 2170;
Loại vùng chứa 4: 1000 CuFt/$ 1700;

Không có đơn đặt hàng nào vượt quá 2700 CuFt nhưng có khả năng vượt qua 1000 CuFt.

Bây giờ, chúng tôi cần một chương trình để có được giải pháp tối ưu hóa về chi phí vận chuyển, tức là, giá tối thiểu.
Tôi đánh giá cao mọi đề xuất/ý tưởng.

EDIT:
thực hiện hiện tại của tôi đang sử dụng container lớn nhất lúc đầu, áp dụng phù hợp đầu tiên giảm thuật toán để đóng gói bin để có được kết quả, sau đó phân tích cú pháp thông qua tất cả các container và điều chỉnh kích thước thùng chứa theo khối lượng nội dung ...

Answer 1

Tôi đã viết một chương trình tương tự khi tôi đang làm việc cho một công ty hậu cần. Đây là một vấn đề đóng gói thùng rác 3 chiều, phức tạp hơn một vấn đề đóng gói thùng rác 1 chiều cổ điển - người trong công việc của tôi đã viết chương trình đóng gói hộp cũ mà tôi đã thay thế làm sai lầm của việc giảm mọi thứ đối với vấn đề đóng gói thùng rác 1 chiều (khối lượng hộp và khối lượng gói), nhưng điều này không hiệu quả: công thức vấn đề này nói rằng ba gói 8x8x8 sẽ vừa với hộp 12x12x12, nhưng điều này sẽ khiến bạn bị chồng chéo gói.

Giải pháp của tôi là sử dụng cái gọi là cắt xén heuristic: khi bạn đặt một gói vào container vận chuyển thì điều này tạo ra ba thùng chứa trống mới: giả sử bạn đặt gói ở phía dưới bên trái của thùng chứa, sau đó bạn sẽ có một thùng chứa con trống mới trong không gian trước gói, một vùng chứa con trống mới trong không gian ở bên phải của gói và một thùng chứa con trống mới ở trên cùng của gói. Hãy chắc chắn không chỉ định cùng một không gian trống cho nhiều vùng chứa phụ, ví dụ: nếu bạn không cẩn thận thì bạn sẽ chỉ định phần ở phía trước bên phải của vùng chứa cho vùng chứa con phía trước và tới vùng chứa bên phải, bạn sẽ cần phải chọn một mục để chỉ định nó. Điều này heuristic sẽ loại trừ một số giải pháp tối ưu, nhưng nó nhanh. (Ví dụ cụ thể, giả sử bạn có một hộp 12x12x12 và bạn đặt một gói 8x8x8 vào nó - điều này sẽ để lại cho bạn một thùng chứa trống rỗng 4x12x12, thùng chứa trống rỗng 4x8x12 và hộp chứa phụ rỗng 4x8x8. sai cách để chia không gian trống là có ba vùng chứa trống rỗng 4x12x12 - điều này sẽ dẫn đến các gói chồng chéo. Nếu hộp hoặc gói không phải là hình khối thì bạn có nhiều cách để chia tăng dung lượng trống - bạn cần phải quyết định xem có tối đa hóa kích thước của một hoặc hai vùng chứa phụ hay thay vì cố tạo ba thùng chứa nhỏ hơn hoặc bằng nhau.) Bạn cần sử dụng tiêu chí hợp lý để đặt hàng/chọn các thùng chứa phụ hoặc số khác của các thùng chứa phụ sẽ tăng theo cấp số nhân; Tôi đã giải quyết vấn đề này bằng cách điền vào các vùng chứa con nhỏ nhất trước và loại bỏ bất kỳ vùng chứa con nào quá nhỏ để chứa gói, giữ số lượng các thùng chứa con với một số hợp lý.

Có một số tùy chọn bạn có: sử dụng vùng chứa nào, cách xoay các gói đi vào vùng chứa (thường có sáu cách để xoay gói, nhưng không phải tất cả các phép quay đều hợp pháp đối với một số gói, ví dụ:gói "này kết thúc" sẽ chỉ có hai vòng quay), cách phân vùng các vùng chứa con (ví dụ: bạn gán không gian chồng lấp cho vùng chứa bên phải hoặc vùng con phía trước) và theo thứ tự bạn đóng gói thùng chứa. Tôi đã sử dụng một thuật toán ngẫu nhiên gần bằng phương pháp giảm heuristic phù hợp nhất (sử dụng khối lượng cho heuristic) và ưu tiên tạo một thùng chứa lớn và hai thùng chứa nhỏ thay vì ba thùng chứa cỡ trung bình, nhưng tôi đã sử dụng ngẫu nhiên bộ tạo số để trộn mọi thứ (vì vậy xác suất lớn nhất là tôi sẽ chọn gói lớn nhất trước, nhưng sẽ có xác suất thấp hơn mà tôi muốn chọn gói lớn thứ hai trước tiên, v.v., với xác suất thấp nhất là rằng tôi muốn chọn gói nhỏ nhất trước, tương tự như vậy, có một cơ hội mà tôi muốn tạo ra ba thùng chứa cỡ trung thay vì một lớn và hai thùng nhỏ, có một cơ hội mà tôi muốn sử dụng ba kích thước trung bình hộp thay vì hai hộp lớn, vv). Sau đó tôi chạy điều này song song vài chục lần và chọn kết quả chi phí ít nhất. Có những phỏng đoán khác mà tôi xem xét, ví dụ heuristic cực điểm chậm hơn (trong khi vẫn chạy trong thời gian đa thức - IIRC nó là một giải pháp thời gian khối, trong khi chém cắt heuristic là thời gian tuyến tính, và ở cực khác nhánh và thuật toán liên kết tìm ra giải pháp tối ưu và chạy theo thời gian theo cấp số nhân) nhưng chính xác hơn (đặc biệt, nó tìm ra một số giải pháp tối ưu được loại bỏ bởi chém cắt heuristic); tuy nhiên, trường hợp sử dụng của tôi là tôi phải sản xuất một khoản phí vận chuyển nhanh ước tính và do đó điểm cực đoan không phù hợp (quá chậm và quá "chính xác" - tôi cần thêm 10% hoặc 20% cho kết quả của nó để tính đến thực tế là những người thực sự đóng gói các hộp chắc chắn sẽ làm cho sự lựa chọn tối ưu phụ).

Tôi không biết tên chương trình, nhưng có thể một số phần mềm thương mại sẽ giải quyết vấn đề này cho bạn, tùy thuộc vào giải pháp tốt cho bạn. câu trả lời

Answer 2

Zim Zam là tốt cho các hộp lớn, nhưng giả sử hộp tương đối nhỏ, bạn có thể sử dụng một thuật toán đơn giản hơn nhiều mà số tiền để giải quyết một phương trình tuyến tính không thể thiếu với một hạn chế:

đâu a, b, c và d là số nguyên được số lượng từng loại của container được sử dụng:

Given,

2700a + 2350b + 2050c + 1000D < = V (trong đó V là tổng khối lượng các đơn đặt hàng)

Bạn muốn fi nd a, b, c, và d sao cho hàm sau được giảm thiểu:

Tổng chi phí C = 2500a + 2200b + 2170c + 1700d

Có vẻ như bạn có thể brute force vấn đề này (đó là NP cứng). Tính toán mọi kết hợp khả thi khả thi của a, b, c và d, và tính toán tổng chi phí cho mỗi kết hợp. Lưu ý rằng không có giải pháp nào sẽ sử dụng nhiều hơn 1 vùng chứa loại d, để giảm số lượng kết hợp có thể có.

Tôi giả định các đơn đặt hàng có thể được phân chia giữa các vùng chứa.