A new model and hybrid approach for large scale inventory routing problem

Y Yu, HX (Haoxun) Chen, F Chu

Research output: Contribution to journalArticleAcademicpeer-review

99 Citations (Scopus)


This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.
Original languageEnglish
Pages (from-to)1022-1040
Number of pages19
JournalEuropean Journal of Operational Research
Issue number3
Publication statusPublished - 2008


Dive into the research topics of 'A new model and hybrid approach for large scale inventory routing problem'. Together they form a unique fingerprint.

Cite this