Heuristic algorithms for inventory replenishment with perishable products and multiple transportation modes

This study extends classic economic lot-sizing problems to permit the replenishment of age-dependent perishable inventories via multiple transportation modes. Inventory replenishment costs include a multiple-setup cost function that considers order setup, purchase, and cargo container costs. The objective is to identify the timing of orders, order quantities, and a choice from among I transportation modes that minimizes the cost of replenishing perishable inventories during a planning horizon of length T. We present a mixed-integer programming formulation of this problem and characterize properties of optimal solutions. We propose a primal-dual heuristic algorithm that runs in O(IT2). In addition, we provide heuristic algorithms for two special cases of the problem involving one or two replenishment modes. For the single replenishment mode problem, we propose (i) a dynamic programming algorithm that explores solutions that satisfy the Zero Inventory Ordering Policy and runs in O(T-2) and (ii) a dynamic programming algorithm that explores solutions that satisfy the Less-than-Truckload first positioning property and runs in O(T 3). For the two replenishment mode problem, we present a knapsack-based algorithm that identifies the minimum number of cargo containers required to meet demand. The running time of this algorithm is O(T-2). We evaluate the quality of the solutions generated by these different approaches via extensive numerical analyses.