Skip to Main content Skip to Navigation
Journal articles

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

Abstract : 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.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02478671
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, February 14, 2020 - 9:25:50 AM
Last modification on : Saturday, February 15, 2020 - 1:36:24 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Yugang Yu, Haoxun Chen, Feng Chu. A new model and hybrid approach for large scale inventory routing problems. European Journal of Operational Research, Elsevier, 2008, 189 (3), pp.1022-1040. ⟨10.1016/j.ejor.2007.02.061⟩. ⟨hal-02478671⟩

Share

Metrics

Record views

48