Multi-product lot-sizing with a transportation capacity reservation contract

We prove that the problem of determining transportation lot-sizes so as to meet warehouse demand with no backlogging allowed and to minimize total costs, that is, the sum of inventory carrying, ordering, and transportation costs, is NP-hard in the strong sense. Furthermore, we present a Lagrangean relaxation algorithm to compute lower and upper bounds, of which comprehensive computational experiments show the compelling performance in terms of quality and speed.