Large Scale Inventory Routing Problem with Split Delivery: a New Model and Algorithm

Inventory routing problem (IRP) is an integration of inventory and vehicle routing problem (VRP), which aims at reducing the total inventory and transportation cost by coordinating inventory and transportation activities. However, due to the complexity of IRP, it is very difficult to give an optimal solution. In this paper, we give a new model and algorithm to give approximate optimal policy for a deterministic IRP with large scale as follows. Firstly, we propose an integrated approximate IRP model with split delivery and multi-period. A new subtour elimination constraint is given to the IRP with split delivery in which no variable is related to a specific vehicle since the vehicles are homogeneous. Secondly, Lagrangian relaxation is used to solve the lower bound of the proposed model. Thirdly, based on the result of Lagrangian relaxation, minimum cost flow (MCF) method is used to construct a feasible solution of the proposed model. Fourthly, assignment problem is adopted to construct every specific route for every vehicle. Fifthly, an algorithm is given to make the routes feasible and improved. Lastly, numerical examples are given for the problem with 100 customers and 10 periods in which there are approximate 200000 variables and nearly half of them are integral. The numerical example demonstrates that our proposed approach not only can obtain high quality solutions, with the average gap of 2.72% for randomly generated 100 customers' problem, but also can solve problems of realistic sizes in a reasonable computational time in an ordinary personal computer. Information: René de Koster, rkoster@rsm.nl.