ABSTRACT
 
An Inventory Routing Problem (IRP) is among transportation problems 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 of goods 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 as 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 that obtains good solutions of PIRP within reasonable time. As a result of solving the LP relaxation of PIRP by column generation, we obtain a 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 proposed a Tabu search algorithm to solve a large-scale PIRP in which the search is done on routing binary variables and continuous variables, which are 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 for PIRP.