A two-phase algorithm for the cyclic inventory routing problem

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.