Avoid maximum cost method for determining the initial basic feasible solution of the transportation problem

Abstract

The transportation problem is an optimization problem related to determining the transportation plan that will ensure the transportation of products from supply points to demand points with minimum total cost. Although this problem can be modeled as a linear programming model because of its special structure, it is usually solved in two phases: finding the initial basic solution and finding the optimal solution. Thus, finding a good initial solution is important, especially in large problems since it will reduce the number of steps required in the second phase. To date, many approaches have been developed to find the initial basic solution. In this study, a new method called avoid maximum cost method is proposed for determining the initial basic solution of the transportation problem. The advantage of this algorithm is that it is easy to understand and implement. The avoid maximum cost method is applied to test problems and compared with six well-known initial solution methods. The results show that the proposed method produces a consistent and very good initial basic feasible solution. In addition, because of its simplicity, this method can be used as an alternative method for an initial basic feasible solution besides well-known methods in teaching.

Keywords

• Transportation
• Initial solution
• Approximation method

Ulaştırma probleminin başlangıç uygun çözümünün belirlenmesi için en büyük maliyetten kaçınma yöntemi

Öz

Ulaştırma Problemi, ürünlerin arz noktalarından talep noktalarına minimum toplam maliyetle taşınmasını sağlayacak taşıma planının belirlenmesi ile ilgili bir optimizasyon problemidir. Bu problem, özel yapısı nedeniyle bir doğrusal programlama modeli olarak modellenebilse de genellikle başlangıç temel çözümünü bulma ve en uygun çözümü bulma olmak üzere iki aşamada çözülür. Bu nedenle, özellikle büyük problemlerde, ikinci aşamada gereken adım sayısını azaltacağından, iyi bir başlangıç çözümü bulmak önemlidir. Bugüne kadar başlangıç temel çözümünü bulmak için birçok yaklaşım geliştirilmiştir. Bu çalışmada, ulaştırma probleminin başlangıç çözümünün belirlenmesi için maksimum maliyetten kaçınma yöntemi adı verilen yeni bir yöntem önerilmiştir. Bu algoritmanın avantajı, anlaşılması ve uygulanmasının kolay olmasıdır. Maksimum maliyetten kaçınma yöntemi test problemlerine uygulanmış ve iyi bilen altı başlangıç çözüm yöntemi ile karşılaştırılmıştır. Sonuçlar önerilen yöntemin tutarlı ve iyi başlangıç uygun çözümler ürettiğini göstermektedir. Ayrıca, çok basit olması nedeniyle bu yöntem öğretimde çok bilinen yöntemlerle birlikte başlangıç uygun çözümlerin bulunmasında alternatif olarak kullanılabilir

Anahtar Kelimeler

• Ulaştırma
• Başlangıç çözüm
• Yaklaşım yöntemi

Kaynakça

1. [1] Şahin Y. Concurrent Optimization of Warehouse Operations and Order Distribution Activities Using Heuristic Methods. Doctoral Dissertation, Süleyman Demirel University, Isparta, Turkey, 2014.
2. [2] Karagul K, Sahin, Y. “A novel approximation method to obtain initial basic feasible solution of transportation problem”. Journal of King Saud University-Engineering Sciences, 32(3), 211-218, 2020.
3. [3] Bazaraa MS, Jarvis JJ, Sherali HH. Linear Programming and Network Flows. 4th ed. New Jersey, USA, John Willey & Sons, 2010.
4. [4] Hosseini E. “Three new methods to find initial basic feasible solution of transportation problems”. Applied Mathematical Sciences, 11(37), 1803-1814, 2017.
5. [5] Yılmaz Soydan NT, Çilingirtürk AM, Can T. “Simulation for appropriate mean selection in can's approximation method in transportation models”. International Congress of Management Economy and Policy, Istanbul, Turkey, 2-3 November 2019.
6. [6] Kirca Ö, Şatir, A. “A heuristic for obtaining an initial solution for the transportation problem”. Journal of the Operational Research Society, 41(9), 865-871, 1990.
7. [7] Mathirajan M, Meenakshi B. “Experimental analysis of some variants of Vogel's approximation method”. Asia-Pacific Journal of Operational Research, 21(4), 447-462, 2004.
8. [8] Korukoglu S, Ballı S. “An improved vogel's approximation method for the transportation problem”. Mathematical and Computational Applications, 16(2), 370-381, 2011.

9. [9] Khan AR. “A resolution of the transportation problem: an algorithmic approach”. Cell, 4(6), 49-62, 2011.
10. [10] Islam MA, Haque MM, Uddin MS. “Extremum difference formula on total opportunity cost: a transportation cost minimization technique”. Prime University Journal of Multidisciplinary Quest, 6(1), 125-130, 2012.
11. [11] Khan AR, Vilcu A, Sultana N, Ahmed SS. “Determination of initial basic feasible solution of a transportation problem: a TOCM-SUM approach”. Buletinul Institutului Politehnic Din Iasi, Romania, Secţia Automatica si Calculatoare, 61(1), 39-49, 2015.
12. [12] Amaliah B, Fatichah C, Suryani E. “A new heuristic method of finding the initial basic feasible solution to solve the transportation problem”. Journal of King Saud UniversityComputer and Information Sciences, 2020. https://doi.org/10.1016/j.jksuci.2020.07.007
13. [13] Amaliah B, Fatichah C, Suryani E, Muswar A. “Total opportunity cost matrix-supreme cell: a new method to obtain initial basic feasible solution of transportation problems”. The 8th International Conference on Computer and Communications Management, Singapore, Singapore, 17-19 July 2020.
14. [14] Mhlanga A, Nduna IS, Matarise F, Machisvo A. “Innovative application of Dantzig’s North-West Corner rule to solve a transportation problem”. International Journal of Education and Research, 2(2), 1-12, 2014.
15. [15] Das UK, Babu MA, Rahman A, Sharif M. “Advanced vogel’s approximation method (AVAM): A new approach to determine penalty cost for better feasible solution of transportation problem”. International Journal of Engineering, 3(1), 182-187, 2014.
16. [16] Can T, Koçak H. “Tuncay can’s approximation method to obtain initial basic feasible solution to transport problem”. Applied and Computational Mathematics, 5(2), 78-82, 2016.
17. [17] Ahmed MM, Khan AR, Ahmed F, Uddin MS. “Incessant allocation method for solving transportation problems”. American Journal of Operations Research, 6(3), 236-244, 2016.
18. [18] Öztürk A, Yöneylem Araştırmasına Giriş. 4. baskı. Bursa, Türkiye, Ekin Kitabevi, 2007.
19. [19] Taha HA. Operational Research-An Introduction. 10th ed. Essex, England, Pearson Education Limited, 2017.
20. [20] Dantzig, GB, Thapa MN. Linear Programming 1- Introduction. 1st ed.New York, USA, Springer-Verlag, 1997.
21. [21] Khan AR, Vilcu A, Sultana N, Ahmed SS. “Determination of initial basic feasible solution of a transportation problem: a TOCM-SUM approach”. Buletinul Institutului Politehnic Din Iasi, Romania, Secţia Automatica si Calculatoare, 61(1), 39-49, 2015.
22. [22] Babu MA, Hoque MA, Uddin MS. “A heuristic for obtaining better initial feasible solution to the transportation problem”. Opsearch, 57(1), 221-245, 2020.
23. [23] Hossain, MM, Ahme MM, Islam MA, Ukil SI. “An effective approach to determine an initial basic feasible solution: A TOCM-MEDM approach”. Open Journal of Optimization, 9(2), 27-37 2020.
24. [24] Jamali S, Soomro AS, Shaikh MM. “The minimum demand method-a new and efficient initial basic feasible solution method for transportation problems”. Journal of Mechanics of Continua and Mathematical Sciences, 15(19), 94-109, 2020.
25. [25] Amaliah B, Fatichah C, Suryani E, Muswar A. “Total opportunity cost Matrix-Supreme cell: A new method to obtain initial basic feasible solution of transportation problems”. The 8th International Conference on Computer and Communications Management, Singapore, Singapore, 17-19 July 2020.
26. [26] Sam'an M, Ifriza, YN. “A combination of TDM and KSAM to determine initial feasible solution of transportation problems”. Journal of Soft Computing Exploration, 2(1), 17-24, 2021.
27. [27] Nishad AK. “A new ranking approach for solving fully fuzzy transportation problem in intuitionistic fuzzy environment”. Journal of Control, Automation and Electrical Systems, 31(2020), 900-911, 2020.
28. [28] Pratihar J, Kumar R, Edalatpanah SA, Dey A. “Modified Vogel’s approximation method for transportation problem under uncertain environment”. Complex & intelligent systems, 7(1), 29-40, 2021.
29. [29] Sangeetha V, Vijayarangam J, Thirisangu K, Elumalai P. “Simplex based solution for a fuzzy transportation problem”. Malaya Journal of Matematik, S(1), 393-396, 2021.
30. [30] Russell EJ. “Letters to the editor-extension of dantzig's algorithm to finding an initial near-optimal basis for the transportation problem”. Operations Research, 17(1), 187-191, 1969.
31. [31] Ahmed MM, Khan AR, Uddin MS, Ahmed F. “A new approach to solve transportation problems”. Open Journal of Optimization, 5(1), 22-30, 2016.
32. [32] Can T. Yöneylem Araştırması, Nedensellik Üzerine Diyaloglar I. Birinci Baskı. İstanbul, TÜrkiye, Beta Yayınları, 2015.
33. [33] Tze-San L. “A complete russel’s method for the transportation problem”. SIAM Review, 28(4), 547-549, 1986.
34. [34] Shafaat A, Goyal SK. “Resolution of degeneracy in transportation problems”. Journal of the Operational Research Society, 39(4), 411-413, 1988.