A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, which determines delivery volumes to the customers that the depot serves in each period, and vehicle routes to deliver the volumes. This paper aims to solve a large scale multi-period SIRP with split delivery (SIRPSD) where a customer’s delivery in each period can be split and satisfied by multiple vehicle routes if necessary. This paper considers SIRPSD under the multi-criteria of the total inventory and transportation costs, and the service levels of customers. The total inventory and transportation cost is considered as the objective of the problem to minimize, while the service levels of the warehouses and the customers are satisfied by some imposed constraints and can be adjusted according to practical requests. In order to tackle the SIRPSD with notorious computational complexity, we first propose an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We then develop a hybrid approach that combines the linearization of nonlinear constraints, the decomposition of the model into sub-models with Lagrangian relaxation, and a partial linearization approach for a sub model. A near optimal solution of the model found by the approach is used to construct a near optimal solution of the SIRPSD. Randomly generated instances of the problem with up to 200 customers and 5 periods and about 400 thousands decision variables where half of them are integer are examined by numerical experiments. Our approach can obtain high quality near optimal solutions within a reasonable amount of computation time on an ordinary PC.

Lagrangian relaxation, inventory routing problem, partial linearization , split delivery, stochastic demand, vehicle routing problem
dx.doi.org/10.1007/s10479-010-0772-4, hdl.handle.net/1765/20321
ERIM Article Series (EAS)
Annals of Operations Research
Article in press, Online First, 23 July 2010
Erasmus Research Institute of Management

Yu, Y, Chu, C, Chen, H.X, & Chu, F. (2012). Large scale stochastic inventory routing problems with split delivery and service level constraints. Annals of Operations Research, 197(1), 135–158. doi:10.1007/s10479-010-0772-4