An inventory routing problem with perishable goods

An Inventory Routing Problem (IRP) is a transportation problem in which inventory and routing decisions are determined simultaneously over a given planning time horizon. The objective of IRP is to find (1) when to deliver to a customer, (2) how much to deliver to a customer in a time period, and (3) how to route vehicles such that the sum of transportation and inventory costs is minimized while still meeting customer demands. We study a variation of IRP in which goods delivered to customers from the warehouse are perishable (PIRP). This work was motivated from the food distribution of the Academic Model for the Prevention and Treatment of HIV (AMPATH) program, a partnership between the medical school of Indian University and Moi University in Kenya. Our research explores modeling issues, solution approaches and potential benefits for IRP models with perishable goods. The main contributions exist in four areas: (1) PIRP is formulated a large scale mixed integer problem. This model, to our best knowledge, is the first IRP model with perishable goods. (2) We introduce an innovative column generation approach which can obtain good solutions of PIRP within reasonable time. As a result of solving LP relaxation by column generation, we obtain the strong lower bound on the optimal solution of PIRP. (3) By studying the polyhedral structure of PIRP, we develop three families of valid inequalities for PIRP. The computational results showed that these valid inequalities are effective to strengthen PIRP. (4) We propose a Tabu search algorithm to solve large-scale PIRPs in which the search is done on routing binary variables and continuous variables, the quantities of goods delivered to customers, are determined through a linear programming problem. The computational results showed that the Tabu search algorithm can provide a good heuristic solution