Over the last decade there has been a growing amount of interest towards the integration of various elements of the Supply Chain Management. The category of problems arising from the combination of distribution and inventory management decisions is possibly the most typical example of that notion and is known as inventory routing problems (IRP). IRP for a single product deals with the distribution of the product, from a single depot to a set of n customers over a specific number of time periods, using a fleet of homogenous vehicles. The objective is to minimise the average daily cost for the planning period, while ensuring that no stock outs will occur. In this work a two-phase approach is examined. The epicentre of the first phase is a Mathematical Programming model used to provide an accurate description of the problem. At the second phase a Genetic Algorithm (GA) with suitably designed genetic operators, is employed in order to obtain near optimal solutions.