نوع مقاله : مقاله پژوهشی
نویسندگان
گروه ریاضی، دانشگاه آزاد اسلامی واحد مسجد سلیمان، ایران.
چکیده
در این مقاله، مسئله توزیع چند محصولی با هزینه ثابت که نوع خاصی از مسئله حمل‌ونقل با هزینه ثابت می‌باشد، توسعه داده‌شده است. در مسئله توزیع چند محصولی با هزینه ثابت، محصولات از مبدأ با هزینه مستقیم و ثابت حمل و باحالت حمل مختلف به مقصدها ارسال میشوند. این مدل، به‌منظور تأمین تقاضای هر مشتری، مقدار حمل کالاها در این مسیرها را طوری تعیین میکند که مجموع هزینههای مستقیم و ثابت حمل کمینه شود. چون این مسئله از نوع مسائل چندجمله‌ای سخت است، نرمافزارهای بهینهسازی قادر به حل این مسئله در اندازههای کوچک و تا حدی متوسط هستند. به‌منظور حل مسئله در اندازه های متوسط و بزرگ، روش آزادسازی لاگرانژ را پیشنهاد میکنیم. نتایج محاسباتی نشان میدهد که روش آزادسازی لاگرانژ با شکاف بهینگی، قادر به حل مسایلی با ابعاد بالاتر در مقایسه با جواب حاصل از نرمافزارهای بهینهسازی است.
کلیدواژه‌ها
موضوعات
عنوان مقاله [English]
Lagrangian relaxation approach for multi-commodity distribution problem with fixed cost
نویسندگان [English]
- Ali Mahmoodirad
- Hamed Ansory Savary
Department of Mathematics, Islamic Azad University, Masjed-Soleiman Branch, Masjed-Soleiman, Iran.
چکیده [English]
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.
کلیدواژه‌ها [English]
- multi-commodity planning problem
- NP-hard problems
- Lagrangean relaxation
- Fixed-cost
)