Groupe d’études et de recherche en analyse des décisions

Inventory routing problems

Maria Grazia Speranza Università degli Studi di Brescia, Italie

In this talk the class of inventory routing problems (IRPs) will be introduced. After a review of the literature, with motivations to study this class of problems, the focus will be on the class of discrete time IRPs that include in the objective function transportation and inventory costs. The simple case of one origin and one destination will be presented first. Then, the case of a general distribution network will be considered. A product is distributed from a central facility to several customers and a maximum level of the inventory is given for each customer. The central facility monitors the inventory of each customer and decides when to serve each customer and how much to deliver, guaranteeing that no stock-out occurs. The problem is to determine for each discrete time instant of a given time period which customers to serve, the quantity to deliver to each customer and the route of the vehicles. The objective is the minimization of the sum of the cost of the inventory and of the cost of the routing. A mixed integer linear programming model will be presented together with valid inequalities used to strengthen the continuous relaxation of the model. A branch-and-cut algorithm to optimally solve the model and a hybrid heuristic will be described. Computational results will be presented for a set of randomly generated problem instances. An extension of the model to the case where production is also included will be discussed. Different inventory management policies will be compared.