A Hybrid Algorithm for an Inventory Routing Problem

M. Grazia Speranza 1, Claudia Archetti 1, Luca Bertazzi 1, and Alain Hertz 2

1 University of Brescia, Department of Quantitative Methods, Brescia, Italy
farchetti, bertazzi, speranzag@eco.unibs.it

2 Ecole Polytechnique and GERAD, Montreal, Canada
alain.hertz@gerad.ca

Abstract. We consider an inventory routing problem in discrete time
where a supplier has to serve a set of customers over a time horizon.
A capacity constraint for the inventory is given for each customer and
the service cannot cause any stock-out situation. Two diŽerent replen-
ishment policies are considered, the order-up-to level and the maximum
level policies. A single vehicle with a given capacity is available. The
transportation cost is proportional to the distance traveled, whereas the
inventory holding cost is proportional to the level of the inventory at the
customers and at the supplier. The objective is the minimization of the
sum of the inventory and transportation costs. We present a metaheuris-
tic that combines a tabu search scheme with ad hoc designed mixed
integer programming models. The eŽectiveness of the metaheuristic is
proved over a set of benchmark instances for which the optimal solution
is known.