Cyclical Inventory Routing with Unsplittable Pick-Up and Deliveries

We address a milk run logistics problem in which goods must be transferred between facilities on a regular basis to support a company’s production. The resulting optimization problem is a form of cyclical, multi-commodity inventory routing problem with pick-ups and deliveries. This problem becomes particularly challenging when either all available cargo of a particular commodity must be picked up or none of it, so as to simplify internal logistics procedures. We model the problem mathematically and introduce a two-phase heuristic to solve the problem. The first phase consists of an adaptive large neighborhood search (ALNS), and the second phase uses a relaxed version of the mathematical model to improve the routes for the vehicles. We present experimental results on a dataset based on real-world data from a company in Germany and show that our two-phase procedure can find high quality solutions even to real-world sized problems in reasonable amounts of computation time.