(655f) Mixed-Integer Programming Methods for Inventory Routing

To reduce the distribution cost in manufacturing supply chains (SCs), customers and vendors adopt vendor managed inventory (VMI) policies, where the vendor decides when and how much to serve each customer (as long as the inventories of customers are kept within an acceptable range). To implement a VMI policy, the vendor has to repeatedly solve the inventory routing problem (IRP), which, in essence, is the integration of inventory control and distribution scheduling – the vendor decides the vehicle routes and schedules simultaneously with delivery amounts and visiting times. A wide range of constraints, including customer access windows, maximum working and driving time limits, and heterogeneous fleet, makes IRP a very hard problem. Recently, we proposed the first mixed-integer programming (MIP) model that accounts for all restrictions and characteristics of practical IRP problems^[1]. While general and easily extendable to handle other features, the proposed model is computationally expensive. To address this challenge, in this work, we develop advanced solution methods, including (1) preprocessing methods and (2) a decomposition algorithm.

First, in the preprocessing phase, we eliminate some nodes and arcs in the SC network that are unlikely to be visited or used in (an optimal solution for) the current planning horizon, since IRP is a detailed scheduling problem with relatively short horizon. Based on inventory level information, consumption profiles, and geographical information, our preprocessing methods generate a much smaller SC network which is then used to formulate smaller MIP models. We also present preprocessing methods that allow us to identify infeasible or suboptimal routes which are excluded from the current formulation.

Second, we design a decomposition algorithm which considers a vehicle routing problem at the higher (first) level, and a detailed scheduling problem at the lower (second) level. For the higher level vehicle routing problem, we find the optimal routes and route-vehicle pairings to minimize transportation cost while ensuring that the minimum demand of each customer is satisfied (i.e., the inventory at the end of horizon is above a minimum terminal level). The first level solution gives a lower bound on the overall objective (of the minimization problem) as it is essentially a relaxation of the full IRP problem. Using the solution of the first level subproblem as input, we solve the detailed lower level distribution scheduling problem with customers, vehicles, drivers and all related constraints. The lower level solution gives an upper bound, since it is a feasible solution for the IRP. The two subproblems are solved iteratively until the gap between the two bounds is closed. We also present methods for the reduction of iterations. 

Finally, we present computational results based on real instances. We show that the proposed methods yield very good solutions fast, which means that they can be used in practice. While the case studies we discuss are from an industrial gas company (Praxair), the models and solution methods we propose are applicable in SCs in various sectors.

[1] Dong, Y.; Sundaramoorthy, A.; Pinto, J.M.; Maravelias, C. T. A MIP Model for Inventory Routing in Industrial Gases Supply Chain. Industrial & Engineering Chemistry Research, submitted for publication.