Lagrangian relaxation approach for multi-commodity distribution problem with fixed cost

In this paper, a multi- commodity planning problem with fixed-cost that is a special type of fixed charge transportation problem is developed. The proposed model determines the amount of products in the existing routes with the aim of minimizing the total cost to satisfy the demand of each customer. As the problem is NP-hard, a moderate sized instance of this problem becomes intractable for general-purpose solvers. In order to overcome this difficulty, a Lagrangian relaxation approach is proposed. The computational experiments show that the Lagrangian relaxation algorithm is able to solve large sized problems with optimality gap compared to general-purpose solvers.