Lagrangian Relaxation Method for the Step fixed-charge Transportation Problem

Subject Areas : Statistics

A. Mahmoodirad ¹ , S. Niroomand ² , M. Sanei ³ , A. Sajedinejad ⁴

1 - Department of Mathematics, Masjed-Soleiman Branch, Islamic Azad University, Masjed-Soleiman, Iran
2 - Department of Industrial Engineering, Firouzabad Institute of Higher Education, Firouzabad, Fars, Iran
3 - Department of Applied Mathematics, Central Tehran Branch, Islamic Azad University, Tehran, Iran
4 - Department of Mathematics, Masjed-Soleiman Branch, Islamic Azad University, Masjed-Soleiman, Iran

Received: 2017-02-03 Accepted : 2017-05-18 Published : 2017-05-01

Keywords: ثابت مرحله‌ای, مسأله حمل و نقل, آزادسازی لاگرانژ,

Abstract :

In this paper, a step fixed charge transportation problem is developed where the products are sent from the sources to the destinations in existence of both unit and step fixed-charges. The proposed model determines the amount of products in the existing routes with the aim of minimizing the total cost (sum of unit and step fixed-charges) 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 isable to solve large sized problems with optimality gap compared togeneral-purpose solvers.