روش آزادسازی لاگرانژ برای حل مسئله توزیع چند محصولی با هزینه ثابت

نوع مقاله: مقاله پژوهشی

نویسندگان

گروه ریاضی، دانشگاه آزاد اسلامی واحد مسجد سلیمان، ایران.

چکیده

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

کلیدواژه‌ها

موضوعات

عنوان مقاله [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

مراجع

محمودی راد، علی، صالحی دره باریک، مرضیه و تقاعدی، روح الله. (1396). مسئله حمل‌ونقل سه‌بعدی با هزینه ثابت با متغیر‌های فازی نوع-2. مجله تصمیم‌گیری و تحقیق در عملیات، 2(3)، 194-179.
Ardalan, Z., Karimi, S., Naderi, B., & Khamseh, A. A. (2016). Supply chain networks design with multi-mode demand satisfaction policy. Computers & industrial engineering, 96, 108-117.
Eskigun, E., Uzsoy, R., Preckel, P. V., Beaujon, G., Krishnan, S., & Tew, J. D. (2007). Outbound supply chain network design with mode selection and lead time considerations. Naval research logistics (NRL), 54(3), 282-300.
Fisher, M. L. (1981). The Lagrangian relaxation method for solving integer programming problems. Management science, 27(1), 1-18.
Gendron, B. (in press). Revisiting Lagrangian relaxation for network design. Discrete applied mathematics.doi: https://doi.org/10.1016/j.dam.2018.07.003
Held, M., & Karp, R. M. (1971). The traveling-salesman problem and minimum spanning trees: Part II. Mathematical programming, 1(1), 6-25.
Jalil, S. A., Javaid, S., & Muneeb, S. M. A decentralized multi-level decision making model for solid transportation problem with uncertainty. International journal of system assurance engineering and management, 1-12.
Heidari-Fathian, H., & Pasandideh, S. H. R. (2018). Green-Blood supply chain network design: Robust optimization, Bounded Objective Function & Lagrangian relaxation. Computers & industrial engineering. 12, 95-105.
Kundu, P., Kar, S., & Maiti, M. (2013). Multi-objective multi-item solid transportation problem in fuzzy environment. Applied mathematical modelling, 37(4), 2028-2038.
Martin, C. H., Dent, D. C., & Eckhart, J. C. (1993). Integrated production, distribution, and inventory planning at Libbey-Owens-Ford. Interfaces, 23(3), 68-78.
Molla-Alizadeh-Zavardehi, S., Nezhad, S. S., Tavakkoli-Moghaddam, R., & Yazdani, M. (2013). Solving a fuzzy fixed charge solid transportation problem by metaheuristics. Mathematical and computer modelling, 57(5-6), 1543-1558.
Pramanik, S., Jana, D. K., & Maiti, M. (2015). A fixed charge multi-objective solid transportation problem in random fuzzy environment. Journal of intelligent & fuzzy systems, 28(6), 2643-2654.
Sanei, M. Mahmoodirad, A. Molla-Alizadeh-Zavardehi, S.  (2013), An Electromagnetism-like algorithm for fixed charge solid transportation problem, International journal of mathematical modelling & computations, 3(4), 345-354.
Sanei, M., Mahmoodirad, A., Niroomand, S., Jamalian, A., & Gelareh, S. (2017). Step fixed-charge solid transportation problem: a Lagrangian relaxation heuristic approach. Computational and applied mathematics, 36(3), 1217-1237.
Thomas, D. J., & Griffin, P. M. (1996). Coordinated supply chain management. European journal of operational research, 94(1), 1-15.
تصمیم گیری و تحقیق در عملیات

دوره 3، شماره 2
تابستان 1397
صفحه 128-137

فایل ها

سابقه مقاله

  • تاریخ دریافت: 01 اردیبهشت 1397
  • تاریخ بازنگری: 13 تیر 1397
  • تاریخ پذیرش: 10 مرداد 1397

اشتراک گذاری

ارجاع به این مقاله

آمار