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

It is proved 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.

Abstract

Although transportation costs can form more than 50% of the total logistics costs of a product, they are often neglected in lot-sizing research and modelling. Nonetheless, the body of research that does take transportation costs into account is gradually growing. The bulk of this type of research, however, assumes that freight rates decrease as shipping weights and/or volumes increase. Inspired by the situation with a large European manufacturing company, we study a multi-product lot-sizing model where, in any period, any portion of a reserved transportation capacity can be used in exchange for a guaranteed price. If the capacity is insufficient, then the shipper needs to contract additional transportation capacity on the spot market, where the prevailing price is higher. Accordingly, the freight rates are piece-wise linearly increasing in our model. 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.