A Model and Algorithm for Large Scale Stochastic Inventory Routing Problem

Yugang Yu (1) , Feng Chu (1) , Haoxun Chen (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

Inventory routing problem (IRP) is an integration of inventory planning and vehicle routing. In this paper, we consider stochastic IRP (SIRP) where customer demands are stochastic. Due to the complexity of SIRP, an approximate stochastic model is proposed for SIRP with split delivery (SIRPSD) in which no variable is related to a specific vehicle since the vehicles considered are homogeneous. The stochastic model is transformed into an equivalent deterministic model by imposing a service level constraint for each customer and by analytically eliminating the stochastic components in the model. Lagrangian relaxation is used to decompose the deterministic model into inventory and routing subproblems. Based on the solution of the Lagrangian relaxed problem, a near-optimal feasible solution of the SIRPSD is constructed. Numerical testing shows that randomly generated problems with 100 customers and 5 periods can be solved near optimally using our proposed approach in a reasonable computation time.

Keywords: Large-scale systems; Stochastic processes; Routing; Vehicles; Lagrangian functions; Costs; Transportation; Inventory control; Integrated circuit modeling; Virtual reality; Inventory routing problem; stochastic demand; split delivery; vehicle routing problem; Lagrangian relaxation

Domains: Operations Research [cs.RO]; Data Structures and Algorithms [cs.DS]

Yugang Yu, Feng Chu, Haoxun Chen. A Model and Algorithm for Large Scale Stochastic Inventory Routing Problem. 2006 International Conference on Service Systems and Service Management, Oct 2006, Troyes, France. pp.355-360, ⟨10.1109/ICSSSM.2006.320640⟩. ⟨hal-02477600⟩