Case study: The inventory routing for vending machines

In this paper, we present an integrated vendor managed inventory system currently being developed for large soft drink firms in Japan. The heart of our system is a heuristic algorithm for the inventory routing problem that is concerned with the supply of a set of products from a single depot to a set of customers over a given planning horizon. The objective is to minimize the sum of distribution, inventory, and shortage costs during the planning periods. Our two-phase algorithm determines the set of customers to be supplied each day and finds routes for vehicles to serve those customers. The first phase of the algorithm constructs an initial feasible solution using an insertion method, and the second improves the initial solution using a local search based on Cross-opt neighborhood. Due to the size and complexity of our real application, we adopt sophisticated data structures and speed-up techniques. Typical problems involve a depot and about 700 vending machines. For the problems, the system has been saving about 40% of total working hours and the number of routes.