Lagrangian Relaxation Method for the Step fixed-charge Transportation Problem

Document Type: research paper

Authors

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

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 is able to solve large sized problems with optimality gap compared to general-purpose solvers.

Keywords


Article Title [Persian]

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

Authors [Persian]

  • علی محمودی‌راد 1
  • صادق نیرومند 2
  • مسعود صانعی 3
  • عبدالرحمان ساجدی نژاد 1
1 استادیار، دانشگاه آزاد اسلامی واحد مسجد سلیمان، گروه ریاضی، مسجدسلیمان، ایران
2 استادیار، موسسه آموزش عالی فیروزآباد، گروه مهندسی صنایع، فیروزآباد، فارس، ایران
3 دانشیار، دانشگاه آزاد اسلامی واحد تهران مرکزی، گروه ریاضی، تهران، ایران
Abstract [Persian]

در این مقاله مساله حمل و نقل با هزینه ی ثابت مرحله­ای توسعه داده شده است که محصولات از مبداها با هزینه مستقیم و ثابت مرحله­ای به مقصدها فرستاده می­شوند. مدل پیشنهادی، مقدار حمل کالاها در آن مسیرها را با هدف مینیمم نمودن هزینه­ها (مجموع هزینه­های مستقیم و ثابت مرحله­ای) طوری تعیین می­نماید که تقاضای هر مشتری نیز برآورده شود. چون این مساله از نوع مسائل چند جمله ای سخت است، نرم­افزارهای بهینه­سازی قادر به حل این مسأله در اندازه­های کوچک و متوسط هستند.  به منظور حل مسأله در اندازهای بزرگ، روش­ آزاد­سازی لاگرانژ را پیشنهاد می­کنیم. نتایج محاسباتی نشان می­دهد که روش آزادسازی لاگرانژ با شکاف بهینگی قادر به حل مسایلی با ابعاد بالاتر در مقایسه با نرم افزارهای بهینه سازی است.

Keywords [Persian]

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