빈 포장/배낭 2d/4d

Question

하루 500 개 이상의 주문이 있다고 가정 해 보겠습니다. 각 주문은 공간적 차원과 무게가 다른 평균 30 개의 제품으로 구성됩니다. 최소 포장 상자를 사용하여 제품을 포장하고 싶습니다. 상자의 제약 조건은 무게와 볼륨입니다. 두 제약 조건은 고정되어 있으며 모든 상자에서 동일합니다.

이 글은 4d binpacking/napsack 문제처럼 보였습니다.이 문제를 해결할 수있는 몇 가지 알고리즘에 대해 읽었습니다. 이 문제를 해결할 수있는 파이썬 패키지가 있습니까?

또한 3 차원 공간에 대해 너무 걱정하지 않으므로 2 차원 빈 패킹 알고리즘에 만족할 것입니다. 여기서 2 차원은 볼륨과 무게를 의미하며 사각형 상자는 아닙니다.

미리 감사드립니다!

Answer 1

4D에서 2D로 줄 이도록 해 주셔서 감사합니다. 그런데 2 차원 문제가 1D보다 딱딱하다는 것은 나에게 분명하지 않습니다. 매스와 볼륨은 자연스럽게 밀도를 통해 관련되어 있기 때문입니다. 치수가 (기계, 시간) 인 작업장 예약과는 매우 다릅니다. 상품의 밀도가 다르지만 여전히 질량이 &이면 양의 상관 관계가 나타납니다.

대상 밀도에 대한 휴리스틱은 bin_weight_limit/bin_volume입니다. 더 나은 추정치는 입력 집합이 질량 또는 부피에 의해 제한되는지 여부를 고려할 것이고, 항목 혼합이 매일 바뀌지 않는 경우 어제 출하 한 밀도를 사용할 수도 있습니다. 밀도 추적을 사용하여 표준 1D 욕심 접근법을 사용하는 것이 좋습니다. 지금까지 포장 된 항목이 목표 밀도보다 높으면 "욕심 많은"은 덜 밀도가 높은 항목을 선택하는 것을 의미하고 그 반대도 마찬가지입니다.

가중치순으로 정렬 된 항목 목록과 볼륨 순서로 정렬 된 항목 목록을 저장하여 구현할 수 있습니다. 목록에 포인터를 유지하고 현재 또는 목표 밀도보다 낮은지 여부에 따라 하나의 목록 또는 다른 목록에서 선택하십시오. 거의 불충분 한 밀도가 "큰"양으로 변하는 것을 확인하기 위해 몇 가지 후보 항목을 건너 뛴다 고 주장하여 거의 불충분하거나 불균형이 클 때 선택 프로세스를 더 복잡하게 만드는 기능을 정의하십시오. 각 항목이 추가 될 때 대상 밀도의 위아래 사이에서 빈 농도를 교대로 시도 할 수 있습니다.