Inventory routing for perishable products

We explore three problems in this thesis and develop solution methods for each problem. First, an inventory routing problem for a perishable product with stochastic demands is considered and different approximate solution methods are developed to solve. Based on computational experiments, the solution methods are compared in terms of average profit, service level, and actual freshness. The impact of relevant parameters on the performance of the solution methods is investigated. Managerial insights are drawn by analyzing the impact of shelf life and store capacity on the profit. The value of considering uncertainty and the value of accessing full information are measured. The computational results highlight that a simple ordering policy can often replace a more sophisticated solution method, while preserving the same efficacy. Second, we introduce a vehicle routing problem (VRP) where a set of stores places deterministic orders to a logistics service provider (LSP) for two successive periods. Deliveries requested in each period can be shifted by the LSP to the other period, possibly with modified quantities. The LSP incurs a penalty for any diversion from the initial delivery period. The data regarding shifted delivery quantities and penalties are provided by the stores. From the perspective of the LSP, diversions could be beneficial if savings in the routing costs outweigh the penalties. In this work, we introduce a new two-period VRP model where the LSP seeks to improve its total cost, compared to solving two independent VRPs with fixed delivery periods, by allowing deliveries to be shifted. We solve this model to optimality by an efficient branch-and-price algorithm implementing several cutting-edge techniques. We draw algorithmic and managerial insights based on our test instances. Third, a two-period VRP is considered where the orders placed by stores for each period can be partially shifted to the other period, given that the sum of the delivery quantities in two periods to each customer is fixed. A linear penalization of delivery shifts is assumed based on the quantity shifted. We represent two mixed integer linear programming (MILP) formulations for the problem. A column-row generation algorithm to solve the LP-relaxation of the first formulation is developed. To solve the LP-relaxation of the second formulation, we develop a column generation algorithm. Details of two label-setting algorithms to solve the pricing problems of the column-row generation and column generation algorithms are discussed. Numerical results can be compared with a similar model in which only full delivery shifts are allowed