Delivery volume optimization

This work is motivated by the need to solve the inventory routing problem when implementing a business practice called vendor managed inventory replenishment. With vendor managed inventory replenishment, vendors monitor their customers' inventories, and decide when and how much inventory should be replenished at each customer. The inventory routing problem attempts to coordinate inventory replenishment and transportation in such a way that the cost is minimized over the long run. In this paper, we develop a linear time algorithm for determining a delivery schedule for a route, i.e., a given sequence of customer visits, that maximizes the total amount of product that is delivered on the route. The problem is not as easy as it may seem at first glance because of delivery windows at customers and the two dueling effects of increased inventory holding capacity at customers as time progresses and increased delivery times as more product is delivered at customers. Efficiently constructing such delivery schedules is important because it has to be done numerous times in insertion heuristics and local search procedures employed in solution approaches for the inventory routing problem.