Title: Large scale inventory routing problem with split delivery: a new model and Lagrangian relaxation approach

Authors: Yugang Yu, Haoxun Chen, Feng Chu

Addresses: Industrial System Optimization Group, Institute of Computer Science and Engineering of Troyes, University of Technology of Troyes, 12 rue Marie Curie, BP 2060, Troyes 10010, France. ' Industrial System Optimization Group, Institute of Computer Science and Engineering of Troyes, University of Technology of Troyes, 12 rue Marie Curie, BP 2060, Troyes 10010, France. ' Industrial System Optimization Group, Institute of Computer Science and Engineering of Troyes, University of Technology of Troyes, 12 rue Marie Curie, BP 2060, Troyes 10010, France

Abstract: The Inventory Routing Problem (IRP) integrates inventory planning with vehicle routing to minimise total logistics cost by coordinating inventory and transportation activities. Due to its complexity, an approximate model with new subtour elimination constraints is proposed for IRP with split delivery. Lagrangian Relaxation (LR) is used to decompose the model into subproblems that are solved by linear programming and Minimum Cost Flow (MCF) algorithms. A near-optimal solution of the model is constructed from the solution of the relaxed problem using a heuristic. The solution, which defines for each period the delivery volume for each customer, the number of times traversed by vehicles and the total quantity transported on each directed arc in the corresponding transportation network, is repaired to a feasible solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed approach can find near-optimal solutions for the IRP with up to 200 customers in a reasonable computation time.

Keywords: logistics; inventory routing problem; IRP; transportation; Lagrangian relaxation; services operations; split delivery; inventory planning; vehicle routing.

DOI: 10.1504/IJSOI.2006.011018

International Journal of Services Operations and Informatics, 2006 Vol.1 No.3, pp.304 - 320

Published online: 03 Oct 2006 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article