(590g) Mixed-Integer Programming Solution Methods for Inventory Routing Problems

To reduce the distribution cost in supply chains (SCs), vendor managed inventory (VMI) policy is adopted in many chemical industries. Under this policy, the vendor can decide when and how much to serve each customer, on the condition that the inventories of customers are kept between the agreed minimum and maximum levels. To make the distribution decisions under a VMI policy, the inventory routing problem (IRP) needs to be solved, in which the vehicle routes and schedules are decided simultaneously with delivery amounts and visiting times. A wide range of constraints, which include access windows of customers, maximum working/driving time limit for drivers, and vehicle capacities, make IRP a hard problem. To address this challenge, we have developed advanced solution methods, including preprocessing and decomposition methods.

First, in the preprocessing algorithm, we eliminate some nodes and arcs in the SC network that are very unlikely to be visited or used in the current horizon. Based on the information of real-time inventory levels, estimated future consumption and customer locations, the preprocessing algorithm reduces the size of the SC network by removing some redundant nodes and arcs for the current horizon.

Second, the proposed decomposition method considers an upper level vehicle routing problem, and a lower level scheduling problem. The upper level vehicle routing problem determines the optimal routes and route-vehicle pairings to minimize the transportation cost while making sure that the minimum customer “demands” are satisfied (i.e., the inventory at the end of horizon is greater than a minimum terminal level). The upper level solution gives a lower bound on the minimization objective as it is a relaxation of the original problem. Using the solution of upper level problem as input, we solve the lower level distribution scheduling problem with customers, vehicles, drivers and all constraints. The lower level solution yields an upper bound, since it is a feasible solution for the IRP. The upper and lower subproblems are linked by an iterative algorithm. When the lower level scheduling problem is infeasible, or the lower bound is strictly less than the upper bound, integer cuts are generated and added to the upper level problem. The lower level infeasibility can be due to (1) an infeasible assignments of routes to a driver, (2) access window constraints, and (3) inventory level violations. The discrepancies between the upper and lower bounds can be due to longer working times or smaller delivery amounts found by the lower level problem compared to that of the upper level problem. The iterative algorithm terminates when the gap of the upper and lower bounds is closed.

Furthermore, we show how our methods account for various practical constraints. These constraints include the modeling of time-varying consumption profiles, truck-customer compatibility, serve-first requirements for some customers, and penalization of low inventory levels. Finally, we discuss instances with different products, which lead to distribution networks of various sizes.