A new model and hybrid approach for large scale inventory routing problems - Archive ouverte HAL Access content directly
Journal Articles European Journal of Operational Research Year : 2008

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

(1) , (1) , (1)
1

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.

Dates and versions

hal-02478671 , version 1 (14-02-2020)

Identifiers

Cite

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

Collections

CNRS UTT LOSI
14 View
0 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More