A Lagrangian relaxation approach to multi-period inventory/distribution planning

Abstract

We consider a multi-period inventory/distribution planning problem (MPIDP) in a one-warehouse multiretailer distribution system where a fleet of heterogeneous vehicles delivers products from a warehouse to several retailers. The objective of the MPIDP is to minimise transportation costs for product delivery and inventory holding costs at retailers over the planning horizon. In this research, the problem is formulated as a mixed integer linear programme and solved by a Lagrangian relaxation approach. A subgradient optimisation method is employed to obtain lower bounds. We develop a Lagrangian heuristic algorithm to find a good feasible solution of the MPIDP. Computational experiments on randomly generated test problems showed that the suggested algorithm gave relatively good solutions in a reasonable amount of computation time.