What is known:

There are $b_i$ boxes of type $i$, where $i=1, \ldots, n$.

There are $3$ types of truck, each can carry at most $K_1$, $K_2$, and $K_3$ boxes respectively. Each type of truck has unlimited supply.

The costs of using each type of truck are $C_1, C_2, C_3$ respectively. In addition, each truck can only carry at most $2$ types of boxes without paying additional fee.

If the type $i$ truck carries $x$, where $x > 2$, type of boxes, the cost is $C_i + a*(x-2)$.

Assume that $n$ is small.

What is being asked:

The minimum cost of carrying all the boxes.

I've been spending hours on this problem. I tried to formulate this as LP problem, but it seems impossible.

It seems this looks like bin packing problem. However, in the standard problem, there is only one type of bin of size V. But here, we have 3 types of bin.

Any direction or hint to solve the problem is appreciated. Thank you.

nb: This is not homework problem. I've encountered this problem in real life.


Just pick the truck with the lowest cost ( $min(C_1,C_2,C_3)$ ) and use only that type. If it is cheaper ($2a<C_i$) to completely fill each truck (of that type), do so, otherwise, take as many trucks needed and put only $2$ boxes in each truck.

I am assuming you are allowed to send trucks without filling them (with $2$ boxes only).

  • $\begingroup$ Why only 2 boxes? $\endgroup$ – hans-t Jan 15 '15 at 12:47
  • $\begingroup$ If the additonal fee is more than the base fee per truck, it's best to take a new truck for every 2 boxes. $\endgroup$ – ghosts_in_the_code Jan 15 '15 at 15:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.