Constraint Programming approaches for the Inventory Routing Problem
Axel Delsol  1, *@  , Christophe Duhamel  1@  , Philippe Lacomme  1@  , Helene Toussaint  1@  
1 : Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes  (LIMOS)  -  Website
Université Clermont Auvergne : UMR6158, Centre National de la Recherche Scientifique : UMR6158
Bât ISIMA / Campus des Cézeaux BP 10025 / 63173 Aubière Cedex -  France
* : Corresponding author

The inventory routing problem (IRP) occurs in supply chains management when retailers' inventory levels are managed by the suppliers. The IRP consists of designing routes to replenish retailers' inventory level over a discrete time horizon. Quantities delivered are set by the supplier such that no stock-out occurs and retailers' demands are satisfied. The objective is to minimize transportation and inventory costs over the time horizon.

We consider a variant of the IRP where the supplier has a limited fleet of homogeneous vehicles (MIRP) for which we propose original Constraint Programming (CP) formulations. In each formulation, the replenish plan and the routing design are jointly defined such that subtours are implicitly forbidden. Moreover, our models use global constraints in order to prune infeasible solutions more efficiently in the CP propagation algorithm.

We use several well-known CP strategies to guide the variables domain exploration and improve constraints propagations. The numerical experiments have been carried out on the set of instances from (Archetti et al., 2007) and the results are compared with the matheuristic method of (Archetti et al., 2017). Our CP approach computes initial feasible solutions for instances with up to 50 customers over 3 periods in 2 seconds on average, which is significantly faster than most previous published methods. Our model also finds solutions for the largest instances of literature (200 customers, 6 periods, 5 vehicles) in 30 seconds. We are currently investigating the combination of CP with local searches and integer programming to quickly reach near-optimal solutions.

Online user: 1 RSS Feed