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

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

نویسندگان

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

چکیده

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

کلیدواژه‌ها

موضوعات


عنوان مقاله [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 engineering96, 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 science27(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 programming1(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 modelling37(4), 2028-2038.

Martin, C. H., Dent, D. C., & Eckhart, J. C. (1993). Integrated production, distribution, and inventory planning at Libbey-Owens-Ford. Interfaces23(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 modelling57(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 systems28(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 research94(1), 1-15.