A stochastic inventory routing problem (SIRP) is typically the combination of stochastic inventory control problems and NP-hard vehicle routing problems, for a depot to determine delivery volumes to its customers in each period, and vehicle routes to distribute the delivery 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 vehicles if necessary. The objective of the problem is to minimize the total inventory and transportation cost while some constraints are given to satisfy other criteria, such as the service level to limit the stockout probability at each customer and the service level to limit the overfilling probability of the warehouse of each customer. In order to tackle the SIRPSD with notorious computational complexity, we propose for it an approximate model, which significantly reduces the number of decision variables compared to its corresponding exact model. We 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 can be found by the approach, and then be used to construct a near optimal solution of the SIRPSD. Numerical examples show that, for an instance of the problem with 200 customers and 5 periods that contains about 400 thousands decision variables where half of them are integer, our approach can obtain high quality near optimal solutions with a reasonable computational time on an ordinary PC.

HB141, L23, P41, inventory routing problem, split delivery, stochastic demand, vehicle routing
Organization of Production (jel L23), Industrial Policy; Sectoral Planning Methods (jel L52), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)
Erasmus Research Institute of Management
hdl.handle.net/1765/18041
ERIM Report Series Research in Management
ERIM report series research in management Erasmus Research Institute of Management
Erasmus Research Institute of Management

Yu, Y, Chu, C, Chen, H.X, & Chu, F. (2010). Linearization and Decomposition Methods for Large Scale Stochastic Inventory Routing Problem with Service Level Constraints (No. ERS-2010-008-LIS). ERIM report series research in management Erasmus Research Institute of Management. Erasmus Research Institute of Management. Retrieved from http://hdl.handle.net/1765/18041