Two-phase algorithm for the lot-sizing problem with backlogging for stepwise transportation cost without speculative motives

In this paper we consider the lot-sizing problem with backlogging under stepwise transportation costs. Inventory is carried over or backlogged in a trade-off with costs for production setup and transportation. Specifically, inventory is the main source for consolidating demand over periods to increase the chance of Full-Truck-Load (FTL) delivery. We assume that there are no speculative motives in production, which yields an important property for Less-Than-Load (LTL) delivery that the LTL cargo does not contain any unit carried over from the previous period or backlogged for the next period. We solve the problem in two phases. In phase one, we use a geometric technique to preprocess necessary functional values for FTL delivery. In phase two, we provide a residual zoning algorithm, involving not only FTL delivery but also LTL delivery, to obtain an optimal solution. The computational complexity is shown to be O(T²logT) where T is the length of the planning horizon.