Lagrangian relaxation approach for multi-commodity distribution problem with fixed cost

Mahmoodirad, Ali; Ansory Savary, Hamed

doi:10.22105/dmor.2018.67220

Document Type : Original Article

Authors

Department of Mathematics, Islamic Azad University, Masjed-Soleiman Branch, Masjed-Soleiman, Iran.

https://doi.org/10.22105/dmor.2018.67220

Abstract

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.

Keywords

Main Subjects

Transportation

References

محمودی راد، علی، صالحی دره باریک، مرضیه و تقاعدی، روح الله. (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.

Journal of Decisions and Operations Research

Lagrangian relaxation approach for multi-commodity distribution problem with fixed cost

References

References

Volume 3, Issue 2
September 2018
Pages 128-137

Lagrangian relaxation approach for multi-commodity distribution problem with fixed cost

References

References

Volume 3, Issue 2September 2018Pages 128-137

Volume 3, Issue 2
September 2018
Pages 128-137