Different solution methods are developed to solve an inventory routing problem for a perishable product with stochastic demands. The solution methods are empirically compared in terms of average profit, service level, and actual freshness. The benefits of explicitly considering demand uncertainty are quantified. The computational study highlights that in certain situations although a simple ordering policy can achieve very good performance, statistically and economically significant improvements are achieved when using more advanced solution methods. Managerial insights concerning the impact of shelf life and store capacity on profit are also obtained.