A Branch-Price-and-Cut Algorithm for an Inventory Routing Problem

The inventory routing problem (IRP) is faced by distribution companies managing the inventory of their customers. Given one supplier producing a known quantity of a single product at each period of a finite planning horizon, a set of customers consuming a quantity of this product at each period and a homogeneous fleet of capacitated vehicles owned by the supplier, the IRP consists of building feasible delivery vehicle routes in each period such that no stockouts occur at the customers while respecting inventory capacity at each of them. The objective is to minimize the sum of the vehicle traveling costs and the inventory holding costs at the supplier and at the customers. We consider a maximum level replenishment policy that allows to deliver any quantity to a customer as long as the inventory does not exceed its maximum level. In this talk, we introduce a new formulation for this IRP variant and propose an exact branch-price-and-cut algorithm for solving it. In this algorithm, there is one subproblem per period that corresponds to an elementary shortest path problem with resource constraints combined with a bounded knapsack problem. It is solved by a labeling algorithm. Several families of valid inequalities are considered including rounded capacity cuts and cuts on the minimum number of deliveries to satisfy a subset of the demands. Computational results on benchmark instances will be reported and compared to those obtained by a state-of-the-art branch-and-cut algorithm.

This event is organised by the Econometric Institute.
Twitter: @MetricsSeminars