CARE: Heuristics for two-stage multi-product inventory routing problems with replenishments

• We consider a two-stage, multi-product capacitated inventory routing problem (CIRP).
• An integer linear programming (ILP) model is developed for the problem.
• A three-phase heuristics called CARE (Clustering, Allocation, Routing) is proposed.
• Computational results show that the heuristics is efficient for large network sizes.
• Heuristics results are better than ILP upper bounds with less computational effort.

The integration of distribution and routing constitutes the Inventory Routing Problem (IRP), an important aspect of Vendor Managed Inventory (VMI) systems. IRP involves decisions on timing of deliveries, sizes of shipments and routing of vehicles. In the context of supply chain collaboration, the scope of IRP expands to include replenishments at the depot. This paper studies an IRP involving multiple products from different suppliers, a central depot (CD) and a set of warehouses. We develop an integrated Integer Linear Programming (ILP) model to determine the optimal replenishments from suppliers to the CD as well as the routing schedules of vehicles from CD to the multiple warehouses over the defined time horizon. We propose an extended three-phase heuristic called CARE (Clustering, Allocation, Routing -Extended). In the heuristic, the replenishment schedules, from suppliers to the CD (for multiple products in the defined time horizon), is solved using a dynamic programming (DP) model. The routing schedules of vehicles from CD to the multiple warehouses is then modeled and solved as a capacitated IRP (CIRP) problem. With the replenishment schedules as an input from the DP model, the CIRP is solved in three-phases: Cluster the nodes, Allocate to these nodes and Route delivery vehicles through clusters of nodes. Three variants of heuristics are proposed based on the changes to the routing phase – CARE1, CARE2, and CARE3. Computational results for a broad range of test instances yield promising results and show usefulness of the solution approaches. Particularly, the proposed heuristics outperformed CPLEX upper bounds for larger problems with lesser computational effort. The average improvement obtained by the heuristics over CPLEX upper bounds for 15 and 20 warehouse problems, respectively, are: CARE1 – 0.94% and 3.6%, CARE2 – 1.36% and 4.26%, CARE3 – 2.87% and 6.08%. We also show that the results from the proposed heuristic are statistically better than the CPLEX upper bounds. The proposed approaches can easily be implemented into existing VMI systems.