A two-phase algorithm for the cyclic inventory routing problem

The Cyclic Inventory Routing Problem (CIRP) is concerned with finding a cyclic schedule for the distribution of a single product to a number of customers. The problem involves multiple vehicles that can be dispatched several times during their shift. Each customer has a local inventory capacity, a constant consumption rate and stockouts are not allowed. The goal is to compose multiple trips which serve all customers and minimize the combination of transportation, inventory and vehicle costs, in a cyclic distribution pattern. Each trip can have a different frequency in the vehicle schedule. This is an important aspect that makes this so called CIRP, with its non-linear non-convex objective function and a set of non-linear constraints, more complex than the basic Inventory Routing Problem (IRP). Our solution approach decomposes the problem into two subproblems: routing and scheduling, which are dealt with in an iterative way. For each subproblem, we propose a new heuristic. Our first heuristic composes trips, based on the cost estimation of moving customers from one trip to another (routing). The second heuristic tries to combine these trips in an acceptable cyclic schedule (scheduling). In order to search the feasible area efficiently, our heuristic branches one-by-one on the edges of obtained local optima. The proposed algorithm is capable of finding high quality solutions in a reasonable time. When the algorithm is tested on 80 available benchmark instances, the best known solution is improved for 60 of these instances and on average a 3.5 percent improvement is obtained compared to previously best known results. (C) 2016 Elsevier B.V. All rights reserved.