Distribution of shipments on containers problem

user_15701717 0
Viewed 36

The problem is that I have shipments to be sent to customers, and these shipments must be in containers, where each container contains only ONE shipment. I want to determine what is the best container sizes and the number of containers from each size to put these shipments in them? The maximum container size equals the maximum shipment volume. So, I need to specify the sizes of the other containers that maximize the utilized space of these containers. Assume that I have 50 shipments and I should have 3 container sizes. So, the solution should be 50 containers, the three container sizes, and the number of containers from each size.

Objective function:

Maximize the average utilization of the containers

Subjected to:

Each container has one shipment only

The maximum container size equals the maximum shipment volume

Expected solution:

The container sizes

The number of containers from each size enter image description here

algorithm
1 Answers

There's an O(k n²)-time dynamic program where n is the number of shipments and k is the number of different container sizes.

Let the shipment sizes be s1 ≤ s2 ≤ ... ≤ sn. Let W(i, j) be the minimum wasted space in using i different container sizes to pack shipments s1, s2, ... sj. The base case

W(1, j) = sumi∈{1,...,j} (sj − si)

is hopefully clear. For i > 1, the recurrence

W(i, j) = minℓ∈{1,...,j} (W(i−1, ℓ) + sumi∈{ℓ+1,...,j} (sj − si))

says that we should find the optimal division between the largest container (of size sj) and the smaller containers.

The only trick is in evaluating the sums in the recurrence, where it behooves us to iterate ℓ downward so that we can reuse the partial sums.

To actually recover the optimal sizes, we remember the minimum argument to each W(i, j) and work backward from W(n, k).

user_21446690
Related