NETWORK PLANNING IN CAMPUS AREA WITH MINIMUM SPANNING TREE METHOD

Year 2024, Volume: 7 Issue: 2, 61 - 81, 31.12.2024

Burcu Erben , Bülent Sezen

https://doi.org/10.58853/dumad.1231116

Abstract

Network Analysis, which is a planning method, is a type of analysis applied in Operations Research. These analysis methods are Shortest Path, Minimum Spanning Tree, Minimum Cost Flow, and Maximum Flow Model. The logic of each method is different. In this study, some evaluations about planning have made by considering only the Minimum Spanning Tree Algorithm. GAMS (General Algebraic Modeling System) program, which is one of the mathematical programs, was used for this analysis application. Minimum Spanning Tree model has been made applicable in the program by evaluating the distances of the departments in Gebze Technical University. Determined the total number of edges, which are connecting nodes, in this analysis to apply are three different scenarios for 5, 10, and 15. Afterward, as a result of the output obtained from the program, a network structure was created by connecting these edges. Made planning is base on Graph Theory in network analysis. This study aims to help persons' make about planning on campus.

Keywords

: Graf Teorisi, Minimum Kapsama Ağacı, GAMS, Ağ Analizi, Analiz

MİNİMUM KAPSAMA AĞACI YÖNTEMİ İLE KAMPÜS ALANINDA AĞ PLANLAMASI

Abstract

Konumlandırma süreci daha yaygın hale geldikçe, çoğu sektörde planlama ihtiyacı artmaktadır. Bir planlama yöntemi olan Şebeke (Ağ) Analizi, Yöneylem Araştırmasında çok fazla uygulanan bir analiz türüdür. Gelişen platformlar çoğu araştırmacıların değer biçen bir fikir içerisinde olmalarına yol açmaktadır. Çoğu sektörde etkili planlama yapmak analiz yöntemlerine dayanmaktadır. Bu analiz yöntemleri; en kısa yol, Minimum Kapsama Ağacı, Minimum Maliyet Akışı ve Maksimum Akış Modelidir. Farklı özelliklere sahip olan kullanılan model analiz için uygundur. Her bir metodun çalışma mantığı farklıdır. Bu çalışmada sadece Minimum Kapsayan Ağaç Algoritması ele alınarak planlamaya dair bazı değerlendirmeler yapılmıştır. Bu analiz uygulaması için matematiksel programlardan biri olan GAMS (Genel Cebirsel Modelleme Sistemi) programı kullanılmıştır. Gebze Teknik Üniversitesi içerisinde bulunan bölümlerin uzaklıkları değerlendirilerek Minimum Kapsama Ağacı (Minimum Spanning Tree) modeli programda uygulanabilir hale getirilmiştir. Uygulanacak bu analizde, düğümleri birleştiren toplam kenar sayısı, 5, 10 ve 15 olmak üzere üç farklı senaryo olarak belirlenmiştir. Sonrasında programdan elde edilen çıktı sonucunda, bu kenarlar birbirine bağlanarak bir ağ yapısı oluşturulmuştur. Yapılan planlama, ağ analizinde graf teorisine dayanmaktadır. Açıktır ki bu teori, uzaklık değerlerinin nasıl analiz edileceğine yardımcı olmayı amaçlamaktadır. Dahası, bu çalışma insanların kampüste planlama yapmalarına yardımcı olmayı amaçlamaktadır. Ek olarak, bu çalışma farklı alanlar olsa bile uzaklık hesaplamalarının dahil olduğu durumlarda kullanılabilecektir.

Keywords

: Graf Teorisi, Minimum Kapsama Ağacı, GAMS, Ağ Analizi, Analiz

References

• https://www.gams.com/latest/gamslib_ml/libhtml/gamslib_mst.html
• Allison, R. J., Goodwin, S. P., Parker, R. J., Portegies Zwart, S. F., de Grijs, R., & Kouwenhoven, M. B. N. (2009). Using the minimum spanning tree to trace mass segregation. In. Ithaca: Cornell University Library, arXiv.org.
• Ana, U. (2021). Yönlü Graflar. Bursa Uludağ Üniversitesi Fen Bilimleri Enstitüsü, Retrieved from https://acikerisim.uludag.edu.tr/server/api/core/bitstreams/27d9dd09-4d19-4b03-94ed-d43e7d6c1a5e/content
• Antos, K. (2015). Minimum spanning tree problem. In. Barış, Ö., & Özceylan, E. (2019). Optimization of Minimum Spanning Tree and Traveling Salesman Problems Arising in a University Campus Network. International Journal of Industrial Engineering and Operational Research, 1(1), 1-10.
• Büke, C. O., & Erturaç, M. K. (2016). Ağ Analiz Yöntemiyle Sakarya Üniversitesi Esentepe Kampüsünün İncelenmesi ve Web Tabanlı Sunumu. Nature Sciences, 11(4), 14-25.
• Dongxiao Liu, & Zhao, T. (2021). Application of Minimum Spanning Tree in the Solution of Forest Fire Intelligent Drone Deployment. Journal of Physics: Conference Series.
• Dutta, S., Patra, D., Shankar, H., & Verma, P. A. (2014). Development of Gis Tool for the Solution of Minimum Spanning Tree Problem using Prim's Algorithm. In (Vol. XL, pp. 1105-1114). Gottingen: Copernicus GmbH.
• Erkal, T. (2013). Eskişehir’de acil durum yönetiminde ağ (network) analizlerinin kullanılması. Türk Coğrafya Dergisi(61), 11-20.
• Evans, J. R., Minieka, E., & Minieka, E. (1992). Optimization algorithms for networks and graphs (2nd ed.). New York: M. Dekker.
• Fang, K., Model, P., & Yiqin, X. (2008). GIS network analysis in rescue of coal mine. Paper presented at the 21st International Society for Photogrammetry and Remote Sensing (ISPRS) Congress.
• Faruk Dayı, & Ulusoy, T. (2018). Evaluating financial performance with minimum spanning tree approach: an applicatıon in airlines companies. 13(30), 89-103. doi:10.7827/TurkishStudies.14348
• Finke, G. ( 2008). Operations Research and Networks.
• Gen, M., Cheng, R., & Lin, L. (2008). Network Models and Optimization Multiobjective Genetic Algorithm Approach(pp. XIV, 692 p). doi:https://doi.org/10.1007/978-1-84800-181-7
• Golden, B., Raghavan, S., & Stanojevic, D. (2005). Heuristic Search for the Generalized Minimum Spanning Tree Problem. INFORMS Journal on Computing, 17(3), 290-304. Retrieved from https://search.proquest.com/docview/200530855?accountid=15962
• Gopal Pandurangan, Peter Robinson, & Scquizzato, M. (2018). The Distributed Minimum Spanning Tree Problem. Bull. EATCS. Retrieved from https://www.math.unipd.it/~scquizza/papers/PanduranganRS18b.pdf
• Gros, C. (2013). Graph Theory and Small-World Networks. In Complex and Adaptive Dynamical Systems (pp. 1–40).
• Haripriya V, & K, S. H. (2023). The Performance Optimization of Approximate Minimum Spanning Tree for The Different Mobility Model. Paper presented at the 2023 International Conference on Distributed Computing and Electrical Circuits and Electronics (ICDCECE).
• Huong Luu, & Chrobak, M. (2022). Better Hardness Results for the Minimum Spanning Tree Congestion Problem. Computer Science doi:https://doi.org/10.48550/arXiv.2209.08219
• Jia Li, Jiangwei Li, Chenxu Wang, Fons J Verbeek, Tanja Schultz, & Liu, H. (2023). Outlier detection using iterative adaptive mini-minimum spanning tree generation with applications on medical data. Sec. Computational Physiology and Medicine, 14. doi:https://doi.org/10.3389/fphys.2023.1233341
• Jing Deng, Zihan Xu, & Xing, X. (2023). Dynamic spillovers between clean energy and non-ferrous metals markets in China: A network-based analysis during the COVID-19 pandemic. Resources Policy, 83. doi:https://doi.org/10.1016/j.resourpol.2023.103575
• Karas, İ. (2023). Graf Teorisi ve Algoritmaları Retrieved from https://web.karabuk.edu.tr/ismail.karas/759/Sunu1_esas.pdf
• Knowles, J. D., & Corne, D. W. (2002). Enumeraton of Pareto optimal multi-criteria spanning trees - A proof of the incorrectness of Zhou and Gen's proposed algorithm. European Journal of Operational Research, 143(3), 543-547. Retrieved from https://search.proquest.com/docview/204152474?accountid=15962
• Kritikos, M., & Ioannou, G. (2017). A greedy heuristic for the capacitated minimum spanning tree problem. The Journal of the Operational Research Society, 68(10), 1223-1235. doi:http://dx.doi.org/10.1057/s41274-016-0146-7
• Larsson, C., & Safari Books Online (Firm). (2014). Design of modern communication networks : methods and applications(1st ed., pp. 1 online resource (1 volume)). Retrieved from https://go.oreilly.com/yale-university/library/view/-/9780124072381/?ar
• Lenaerts, T. (2011). Scale Free Networks. Encyclopedia of Astrobiology, 1492–1493. doi:10.1007/978-3-642-11274-4_1405
• Mark Needham, & Hodler, A. E. (2019). Graph Algorithms: O'Reilly Media, Inc.
• Meghanathan, N. (2012). Graph Theory Algorithms for Mobile Ad Hoc Networks. Informatica, 36(2), 185-199. Retrieved from https://search.proquest.com/docview/1346615761?accountid=15962
• N. Blomsma, B. de Rooy, F. Gerritse, R. van der Spek, P. Tewarie, A. Hillebrand, . . . Dellen, E. v. (2022). Minimum spanning tree analysis of brain networks: A systematic review of network size effects, sensitivity for neuropsychiatric pathology, and disorder specificity Network Neuroscience 6(2), 301–319. doi:https://doi.org/10.1162/netn_a_00245
• Needham, M., & Hodler, A. E. (2019). Graph algorithms : practical examples in Apache Spark and Neo4j.
• Osipov, V., Sanders, P., & Singler, J. (2009). The Filter-Kruskal Minimum Spanning Tree Algorithm*. In (pp. 52-61). Philadelphia: Society for Industrial and Applied Mathematics.
• Paz Carmi, M. J. Katz, & Mitchell, J. S. B. (2005). The minimum area spanning tree problem. European Workshop on Computational Geometry.
• Pirim H, Ekşioğlu B, & AD, P. (2015). Clustering high throughput biological data with B-MST, a minimum spanning tree based heuristic. Comput Biol Med. , 62, 94-102. doi:10.1016/j.compbiomed.2015.03.031.
• Requejo, C., & Santos, E. (2018). Efficient lower and upper bounds for the weight-constrained minimum spanning tree problem using simple Lagrangian based algorithms. Operational Research, 1-29. doi:http://dx.doi.org/10.1007/s12351-018-0426-x
• Sara Nasirian, Paola Pierleoni, Alberto Belli, Marco Mercuri, & Palma, L. (2023). Pizzza: A Joint Sector Shape and Minimum Spanning Tree-Based Clustering Scheme for Energy Efficient Routing in Wireless Sensor Networks. IEEE Access, 11. doi:https://doi.org/10.1109/ACCESS.2023.3291915
• Seth Pettie, & Ramachandran, V. (2008). Randomized minimum spanning tree algorithms using exponentially fewer random bits. TALG, 4(1). doi:https://doi.org/10.1145/1328911.1328916
• Sezen, B., & Erben, B. (2019). Sürdürülebilir ulaşımda önemli bir yere sahip olan bisikletin Gams küme kapsama modeli ile konumlandırılması: Gebze Teknik Üniversitesi örneği. Akıllı Ulaşım Sistemleri Ve Uygulamaları Dergisi, 2(1), 42-56.
• Şaar, F., & Topcu, A. E. (2021). Minimum spanning tree-based cluster analysis: A new algorithm for determining inconsistent edges. Concurrency and Computation: Practice and Experience, 34. doi:https://doi.org/10.1002/cpe.6717
• TESLIUC, M. (2017). The University of Chicago Mathematics REU 2017. Retrieved from https://math.uchicago.edu/~may/REU2017/
• Tsiotas, D. (2020). Detecting differences in the topology of scale-free networks grown under time-dynamic topological fitness. Scientific Reports. doi:https://doi.org/10.1038/s41598-020-67156-6
• Vasileios Karyotis, & Khouzani, M. H. R. (2016). Chapter 5 - Malware-propagative Markov random fields. In. Wamiliana, W. (2004). Solving the degree constrained minimum spanning tree problem using tabu and modified penalty search methods. Jurnal Teknik Industri, 6(1), 1-9. doi:http://dx.doi.org/10.9744/jti.6.1.pp.
• Wilson Pavon, Myriam Torres, & Inga, E. (2023). Integrating Minimum Spanning Tree and MILP in Urban Planning: A Novel Algorithmic Perspective. doi:https://doi.org/10.3390/buildings14010213
• Xiao Qun Liao, Tong Su, & Ma, L. (2020). Application of neutrosophic minimum spanning tree in electrical power distribution network. CAAI Transactions on Intelligence Technology, 5(2). doi:https://doi.org/10.1049/trit.2019.0100
• YILDIZ, M., BATI, M., & ŞAHİN, M. (2017). Milli Mücadele Dönemi Savaşlarının En Küçük Örten Ağaç Yöntemi İle İncelenmesi Manisa Celal Bayar Üniversitesi Sosyal Bilimler Dergisi, 15(3), 19-36. doi:https://doi.org/10.18026/cbayarsos.340963
• Younes Berouaga, Cherif El Msiyah, & Madkour, J. (2023). Portfolio Optimization Using Minimum Spanning Tree Model in the Moroccan Stock Exchange Market. Int. J. Financial Stud., 11(2). doi:https://doi.org/10.3390/ijfs11020053
• Zakaria Hasanatu, & Boah, D. K. (2024). Rural Electrification of Selected Areas in the Northern Region of Ghana Viewed as a Minimum Spanning Tree Problem. Earthline Journal of Mathematical Sciences. doi:10.34198/ejms.14424.841871