A Branch-and-Price Algorithm for the Two-Echelon Inventory-Routing Problem

The two-echelon inventory-routing problem (2E-IRP) addresses the coordination of inventory management and freight transportation throughout a two-echelon supply network. The latter consists of geographically widespread customers whose demand over a discrete planning horizon can be met from their local inventory, or from intermediate facilities’ inventory. Intermediate facilities are located in the city outskirts and are supplied by distant suppliers. Assuming a vendor-managed inventory system, the 2E-IRP aims to minimize transportation and inventory costs while meeting customers’ demands. To solve this problem, we propose a route-based formulation and develop a branch-and-price algorithm. A labeling algorithm solves one pricing subproblem for each combination of time period and intermediate facility. We generate 400 instances and obtain optimal solutions for 149 of them. We provide an upper bound for another 77 instances with a gap of less than 5% (with an average of 2.79%) and an upper bound for the rest of the instances with an average gap of 11.33%. We provide comprehensive analyses to evaluate the performance of our solution approach.