We study an inventory routing problem in which it has to be determined an optimal distribution plan to replenish a set of customers, by routing a limited fleet of capacitated vehicles over a discrete planning horizon. Each customer consumes a per period quantity of products and have a maximum inventory capacity. Products can be distributed by a supplier to the customers in advance compared to their consumption, provided that their inventory capacity is not violated. The goal is to minimize the total distribution cost, that comprises the routing and the inventory costs. We develop a novel matheuristic approach to solve this problem. The algorithm is based on Kernel Search (KS), a heuristic framework that has been shown to find high-quality solutions for a number of combinatorial optimization problems. The basic idea of KS is to identify subsets of the decision variables and then solving, using a general-purpose solver, a sequence of Mixed-Integer linear Programs, each one restricted to a subset of variables. Extensive computational experiments are conducted on a very large set of benchmark instances. The results show that KS outperforms state-of-the-art algorithms, finding 51 new best-known solutions out of 640 small-size instances, and 102 new best-known solutions out of 240 large-size instances.