Minimum Spanning Tree (MST) Problem: Minimum Distance Line Determination for Denizli Light Rail System Project Proposal

Year 2022, Issue: 15, 111 - 124, 31.01.2022

Müge Akay , Ayşegül Tuş

https://doi.org/10.47072/demiryolu.1004307

Abstract

The route determination process is an important issue in urban transportation and if it is planned correctly, the investment or the new system will provide improvement in traffic. The aim of this study is to determine the line with a minimum distance within the scope of the light rail system project proposed by Denizli Municipality as an alternative to the highway transportation system in order to provide comfort, convenience and time saving in Denizli city transportation. So the line determination has been considered as the Minimum Spanning Tree (MST) problem that can be used in the design of systems in graph ie network structure. Prim, Kruskal algorithms and matrix method have been used to solve the problem. Optimal results have been obtained with all three methods. Minimum MST distance is 29,09 km. However, when the processes for these methods are evaluated in terms of ease of operation, number of iterations, and minimization of complexity, it has been concluded that the matrix method, which is more advantageous, would be more appropriate to use in real life MST problems.

Keywords

Minimum Spanning Tree, Prim Algorithm, Kruskal Algorithm, Matrix Method, Rail System

Minimum Yayılan Ağaç (MYA) Problemi: Denizli İli Hafif Raylı Sistem Proje Önerisi için Minimum Mesafeli Hat Belirleme

Abstract

Şehir içi ulaşımda hat (güzergâh) belirleme süreci, önemli bir konudur ve bu süreç doğru bir şekilde planlanırsa yapılan yatırım veya kurulan yeni sistem, trafikte iyileşme sağlayacaktır. Bu çalışmanın amacı, şehir içi ulaşımda rahatlık, kolaylık ve zaman tasarrufu sağlamak için Denizli Belediyesi tarafından karayolu ulaşım sistemine alternatif olarak önerilen hafif raylı sistem projesi kapsamında minimum mesafeli bir hat belirlemektir. Bu nedenle hat belirleme, graf yani ağ yapısındaki sistemlerin tasarlanmasında kullanılabilen bir Minimum Yayılan Ağaç (MYA) problemi olarak ele alınmıştır. Problemin çözümünde Prim, Kruskal algoritmaları ve matris yöntemi kullanılmıştır. Her üç yöntem ile optimal sonuç elde edilmiştir. Minimum MYA mesafesi 29,09 km’dir. Ancak söz konusu yöntemler için süreçler; işlem kolaylığı, iterasyon sayısı, karmaşıklıkların minimuma indirilmesi açısından değerlendirildiğinde, daha avantajlı olan matris yönteminin gerçek hayat MYA problemlerinde kullanılmasının daha uygun olacağı sonucuna varılmıştır.

Keywords

Minimum Yayılan Ağaç, Prim Algoritması, Kruskal Algoritması, Matris Yöntemi, Raylı Sistem

References

• [1] A.Y. Gündüz, M. Kaya, C. Aydemir, “Kentiçi ulaşımında karayolu ulaşımına alternatif sistem: Raylı ulaşım sistemi”, Akademik Yaklaşımlar Dergisi, cilt 2, sayı 1, ss. 134-151, 2011.
• [2] H. G. Önder, F. Ademar, “Türkiye’deki kentiçi raylı toplu taşıma sistemlerinin ulaşım ana planları bağlamında değerlendirilmesi”, Demiryolu Mühendisliği, sayı 10, ss. 31-45, 2019.
• [3] H. Kutlu, H. Ulvi , F. Akdemir , “Gelişmekte Olan Ülkelerde Raylı Sistem Yatırım Kararlarını Etkileyen Ölçütlerin Belirlenmesi: AB ve Türkiye Özelinde Bir Araştırma”, Demiryolu Mühendisliği, sayı 9, ss. 61-78, 2019.
• [4] S. T. Altuntaş, Y. Eyigün, “Sürdürülebilir kentiçi ulaşım politikaları raylı sistemler örneği”, Teknoloji ve Uygulamalı Bilimler Dergisi, cilt 3, sayı 2, ss. 217-233, 2021.
• [5] S. Şahin, “Malatya’da kentiçi ulaşım ve toplu taşıma sistemlerinin karşılaştırmalı incelenmesi: Trambüs ve hafif raylı sistem örneği”, Yüksek Lisans Tezi, İnönü Üniversitesi, Sosyal Bilimler Enstitüsü, Malatya, 2020.
• [6] H. Gerçek, B. Karpak, T. Kılınçaslan, “A multiple criteria approach for the evaluation of the rail transit networks in Istanbul”, Transportation, vol. 31, no. 2, pp. 203-228, 2004.
• [7] A. Ludin, S. Latip, “Using multi-criteria analysis to identify suitable light rail transit route”, Jurnal Alam Bina, vol. 9, no. 1, pp. 131-142, 2007.
• [8] M. I. T. Alkubaisi, “Predefined evaluating criteria to select the best tramway route”, Journal of Traffic and Logistics Engineering, vol. 2, no. 3, pp. 211-217, 2014.
• [9] G. S. Kalamaras, L. Brino, G. Carrieri, C. Pline, P. Grasso, “Application of multicriteria analysis to select the best highway alignment”, Tunnelling and Underground Space Technology, vol. 15, no. 4, pp. 415-420, 2000.
• [10] M. Hamurcu, T. Eren, “Ankara Büyükşehir Belediyesi’nde çok ölçütlü karar verme yöntemi ile monoray güzergâh seçimi”, Transist, sayı 8, ss. 410-419, 2015.
• [11] M. Hamurcu, T. Eren, “Using ANP-TOPSIS methods for route selection of monorail in Ankara”, In 28th European Conference on Operational Research, Poznan, Polland, 2016, pp. 3-6.
• [12] M. Hamurcu, T. Eren, “Raylı sistem projeleri kararında AHS-HP ve AAS-HP kombinasyonu”, Gazi Mühendislik Bilimleri Dergisi, cilt 3, sayı 3, ss.1-13, 2017.
• [13] B. Sarımehmet, M. Hamurcu, E. Tamer, “Çok kriterli karar verme: Kırıkkale YHT istasyonu-şehir bağlantısının sağlanması”, Demiryolu Mühendisliği, sayı 11, ss. 26-40, 2020.
• [14] R. Banai, “Public transportation decision-making: A case analysis of the Memphis light rail corridor and route selection with analytic hierarchy process”, Journal of Public Transportation, vol. 9, no. 2, pp. 1-24, 2006.
• [15] I. M. Brunner, K. Kim, E. Yamashita, “Analytic hierarchy process and geographic information systems to identify optimal transit alignments”, Transportation Research Record, vol. 2215, no. 1, pp. 59-66, 2011.
• [16] K. Watanabe, K. Gotoh, K. Tachiiri, “Route selection for a new transportation system in hillside urban areas: A case study in Nagasaki, Japan”, Journal of Urban Planning and Development, vol. 132, no. 2, pp. 89-96, 2006.
• [17] R. L. Graham, P. Hell, “On the history of the minimum spanning tree problem”, Annals of the History of Computing, vol. 7, no. 1, pp. 43-57, 1985.
• [18] P.C. Pop, “The generalized minimum spanning tree problem: An overview of formulations, solution procedures and latest advances”, European Journal of Operational Research, vol. 283, no. 1, pp.1-15, 2020.
• [19] A. Dey, A. Pal, H. V. Long, “Fuzzy minimum spanning tree with interval type 2 fuzzy arc length: formulation and a new genetic algorithm”, Soft Computing, vol. 24, no. 6, pp. 3963-3974, 2020.
• [20] O. P. Biswas, M. Goel, H. Negi, M. Datta, “An efficient greedy minimum spanning tree algorithm based on vertex associative cycle detection method”, Procedia Computer Science, vol. 92, pp. 513-519, 2016.
• [21] E. K. Donkoh, S. K. Amponsah, K. F. Darkwah, “Optimal pipeline connection for the West African gas pipeline project”, Research Journal of Applied Sciences, Engineering and Technology, vol. 3, no. 2, pp. 67-73, 2011.
• [22] O. T. Arogundade, B. Sobowale, A. T. Akinwale, “Prim algorithm approach to improving local access network in rural areas”, International Journal of Computer Theory and Engineering, vol. 3, no.3, pp. 413-417, 2011.
• [23] Çevik, S. S. Karaca, M. Özkan, “En küçük yayılma modeli ile İç Anadolu Bölgesinde bir kargo firmasının dağıtım güzergâhının belirlenmesi”, Karamanoğlu Mehmetbey Üniversitesi Sosyal ve Ekonomik Araştırmalar Dergisi, cilt 2011, sayı 2, ss. 1-9, 2011.
• [24] C. K. Gitonga, “Prims algorithm and its application in the design of university LAN networks”, International Journal, vol. 3, no. 10, pp. 131-136, 2015.
• [25] N. P. Akpan, I. A. Iwok, “A minimum spanning tree approach of solving a transportation problem”, International Journal of Mathematics and Statistics Invention, vol. 5, no. 3, pp. 09-18, 2017.
• [26] F. Marpaung, “Comparative of Prim’s and Boruvka’s algorithm to solve minimum spanning tree problems”, Journal of Physics: Conference Series, vol. 1462, IOP Publishing, 2020. doi:10.1088/1742-6596/1462/1/012043
• [27] D. Rachmawati, F. Y. P. Pakpahan, “Comparative analysis of the Kruskal and Boruvka algorithms in solving minimum spanning tree on complete graph”, in International Conference on Data Science, Artificial Intelligence, and Business Analytics (DATABIA), 2020, IEEE, pp. 55-62.
• [28] S. Jahan, T. Hossain, F. A. Simi, “Matrix method for determining minimum spanning tree”, Journal of Applied Mathematics and Computation, vol. 4, no. 4, pp. 118-122, 2020.
• [29] A. Shahin, F. Jaferi, “The shortest route for transportation in supply chain by minimum spanning tree”, International Journal of Logistics Systems and Management, 22(1), 43-54, 2015.
• [30] X. Zhou, J. Yang, J. J. Wu, Z. G. Shi, K. L., Gao, H. W., Liu (2018), “Interest tourism route plan algorithm based on improved minimum spanning tree”, DEStech Transactions on Computer Science and Engineering, International Conference on Modeling, Simulation and Optimization (MSO 2018), ISBN: 978-1-60595-542-1, 270-273.
• [31] K. A. Tin, “Applications of the shortest spanning tree and path on graph theory”, IRE Journals, vol 1, no. 2, pp. 3-6, 2019.
• [32] J. A. Bondy, U. S. R. Murty, Graph theory with applications. London: Macmillan Press, 1976.
• [33] J. B. Kruksal, “On the shortest spanning subtree of a graph and the traveling salesman problem”, Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48-50, 1956.
• [34] R. C. Prim, “Shortest connection networks and some generalizations”, The Bell System Technical Journal, vol. 36, no. 6, pp. 1389-1401, 1957.
• [35] E. W. Dijkstra, “A note on two problems in connexion with graphs”, Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959.
• [36] G. D. Kurt, “Kablosuz ağlarda en az kesinti ihtimalli işbirlikli yol atama”, Yüksek Lisans Tezi, Elektrik ve Elektronik Mühendisliği, TOBB Ekonomi ve Teknoloji Üniversitesi, Fen Bilimleri Enstitüsü, 2011.