A dynamical constraint-generating algorithm for the Single-Vehicle Cyclic Inventory-Routing Problem

摘要

The Single-Vehicle Cyclic Inventory-Routing Problem (SVCIRP) is a variant of the Inventory-Routing Problem (IRP) in which the replenishment decisions of a recurring distribution plan are optimized. In this paper, we investigate the current formulation of the SVCIRP and propose a number of improvements for it. First, we introduce a new binary variable in the model to distinguish tours in which only one retailer is visited. Additionally, we formulate three new sets of valid inequalities. Because one of the sets contains an exponential number of inequalities, we develop a procedure to insert only the violated inequalities. We present an algorithm, based on this procedure, to solve the SVCIRP effectively. Our computational results show that our algorithm outperforms the other exact methods in literature. We obtain 25 new best bounds and we find 13 improved solutions.