Graph-Based Optimization of Distribution Networks Using Minimum Spanning Tree Algorithms
DOI:
https://doi.org/10.57152/malcom.v6i1.2570Keywords:
Algorithms, Distribution Network, Graph, Minimum Spanning Tree, OptimizationAbstract
Urban electric power distribution networks must operate efficiently while supporting sustainability and green economy objectives. This study analyzes the optimization of an urban power distribution network using graph theory approaches, specifically Minimum Spanning Tree methods. The electrical network is modeled as an undirected weighted graph, where substations are represented as nodes and cable connections as edges with distance-based weights. Kruskal and Prim algorithms are applied to determine the optimal network configuration that minimizes total cable length while maintaining full connectivity. A case study of an existing urban distribution network consisting of 229 substations is used to evaluate the proposed approach. The results show that the optimized network configuration reduces total cable length from 61,474.23 meters to 49,391.44 meters a 19.66% reduction (12,082.79 meters saved) leading to improved material efficiency and lower infrastructure costs. Both algorithms produce identical optimal results, confirming their reliability for practical network planning. The findings demonstrate that graph-based optimization techniques can provide effective decision support for designing more efficient and environmentally responsible power distribution systems. This research highlights the potential of mathematical and computational methods for sustainable infrastructure development and for implementing a green economy in urban energy systems.
Downloads
References
L. Dogaru, "Green economy and green growth opportunities for sustainable development," Proceedings, vol. 63, no. 1, p. 70, 2021, doi: 10.3390/proceedings2020063070.
F. Firdaus, "Jejak karbon sektor energi D.I.Yogyakarta dan rekomendasi jumlah pohon yang harus ditanam untuk reduksi emisi gas CO2," AJIE-Asian Journal of Innovation and Entrepreneurship, vol. 4, no. 2, pp. 143-152, 2019.
Y. B. Wibisono and Y. D. Setianto, "Pencarian pohon perentang minimum pada jaringan listrik bangunan dengan menggunakan algoritma Kruskal," Proxies: Jurnal Informatika, vol. 2, no. 1, pp. 1-8, 2021, doi: 10.24167/proxies.v2i1.3198.
B. A. Pratiwi, D. Dharmawan, M. Ilham, R. A. Firdaus, T. P. Putra, and R. J. Yuniar, "Analisis jaringan listrik di perumahan Cardjo KM 15 Balikpapan menggunakan minimum spanning tree," Jurnal Elektrosista, vol. 11, no. 2, pp. 148-156, 2024, doi: 10.63824/jtep.v11i2.177.
A. Mulki, D. Suhaedi, and Y. Permanasari, "Optimasi jaringan distribusi listrik dengan pohon rentang minimum menggunakan bahasa pemrograman Python," Bandung Conference Series: Mathematics, vol. 2, no. 1, pp. 394-399, 2022, doi: 10.29313/bcsm.v2i1.1542.
T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, Third Edition, 3rd ed. Cambridge, MA: MIT Press, 2009.
J. B. Kruskal, "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.
R. C. Prim, "Shortest connection networks and some generalizations," Bell System Technical Journal, vol. 36, no. 6, pp. 1389-1401, 1957, doi: 10.1002/j.1538-7305.1957.tb01515.x.
M. M. Deza and E. Deza, Encyclopedia of Distances, 4th ed. Berlin, Germany: Springer, 2016, doi: 10.1007/978-3-662-52844-0.
A. Julistia and B. Mardhotillah, "Pengoptimalan pendistribusian jaringan listrik menggunakan kruskal algorithm," JISTech (Journal of Islamic Science and Technology), vol. 10, no. 1, pp. 64-71, 2025, doi: 10.30829/jistech.v10i1.24730.
A. Okabe and K. Sugihara, Spatial Analysis along Networks: Statistical and Computational Methods. Chichester, UK: John Wiley & Sons, 2012, doi: 10.1002/9781119967101.
K. Kusnadi, W. Gata, and F. Nova Arviantino, "Aplikasi algoritma Kruskal dan Sollin pada jaringan transmisi nasional provinsi Sulawesi Selatan," METIK JURNAL, vol. 6, no. 1, pp. 28-34, 2022, doi: 10.47002/metik.v6i1.260.
O. S. Sitompul, A. Putera, U. Siahaan, M. Donni, L. Siahaan, M. Furqan, H. Mawengkang, A. P. U. Siahaan, and N. Nasution, "A review of Prim and genetic algorithms in finding and determining routes on connected weighted graphs," International Journal of Civil Engineering and Technology, vol. 9, no. 9, pp. 1755-1765, 2018.
N. S. Saragih and Mulyono Mulyono, "Penerapan algoritma Boruvka pada jaringan listrik (studi kasus pada kelurahan Tanjung Pinggir kecamatan Siantar Martoba)," Jurnal Riset Rumpun Matematika Dan Ilmu Pengetahuan Alam, vol. 2, no. 2, pp. 284-292, 2023, doi: 10.55606/jurrimipa.v2i2.1622.
F. Mahardika, "Penerapan teori graf pada jaringan komputer dengan algoritma Kruskal," Jurnal Informatika: Jurnal Pengembangan IT, vol. 4, no. 1, pp. 17-21, 2019, doi: 10.30591/jpit.v4i1.1032.
N. Innocent, O. Dorcas, O. Duncan, O. Emma, O. Lamech, G. Salome, and O. Edwin, "Defining green economy aspects for eco-friendly industrial approaches; their linkages across the sustainable innovation paradigm," Scientific Research and Essays, vol. 17, no. 2, pp. 23-35, 2022, doi: 10.5897/sre2022.6745.
H. Mohamad, W. I. F. W. Zalnidzham, N. A. Salim, S. Shahbudin, and Z. M. Yasin, "Power system restoration in distribution network using minimum spanning tree - Kruskal's algorithm," Indonesian Journal of Electrical Engineering and Computer Science, vol. 16, no. 1, pp. 1-8, 2019, doi: 10.11591/ijeecs.v16.i1.pp1-8.
W. Pavon, M. Torres, and E. Inga, "Integrating minimum spanning tree and MILP in urban planning: A novel algorithmic perspective," Buildings, vol. 14, no. 1, p. 213, 2024, doi: 10.3390/buildings14010213.
Y. Labbi, D. B. Attous, H. A. Gabbar, B. Mahdad, and A. Zidan, "A new rooted tree optimization algorithm for distribution network reconfiguration," IEEE Transactions on Power Delivery, vol. 27, no. 4, pp. 2233-2244, 2012, doi: 10.1109/TPWRD.2012.2201754.
L. Li, T. Ma, Z. Liu, C. Mao, and D. Negnevitsky, "An improved distribution network reconfiguration method based on minimum spanning tree algorithm and heuristic rules," International Journal of Electrical Power and Energy Systems, vol. 82, pp. 466-473, 2016, doi: 10.1016/j.ijepes.2016.04.017.
R. Liao, Z. Zheng, X. Guan, W. Li, and M. Liang, "Application of neutrosophic minimum spanning tree in electrical power distribution network," CAAI Transactions on Intelligence Technology, vol. 5, no. 3, pp. 162-169, 2020, doi: 10.1049/trit.2019.0100
L. B. Techane, A. O. Salau, Y. W. Gebru, and E. A. Hailu, "Geographical information system based optimal path routing of distribution networks," Heliyon, vol. 8, no. 5, p. e09397, 2022, doi: 10.1016/j.heliyon.2022.e09397.
H. Lara and E. Inga, “Efficient strategies for scalable electrical distribution network planning considering geopositioning,” Electronics, vol. 11, no. 19, p. 3096, 2022, doi: 10.3390/electronics11193096.
A. Valenzuela, E. Inga, and S. Simani, “Planning of a resilient underground distribution network using georeferenced data,” Energies, vol. 12, no. 4, p. 644, 2019, doi: 10.3390/en12040644.
A. Valenzuela, I. Montalvo, and E. Inga, “A decision-making tool for electric distribution network planning based on heuristics and georeferenced data,” Energies, vol. 12, no. 21, p. 4065, 2019, doi: 10.3390/en12214065.
W. Pavón, E. Inga, and S. Simani, “Optimal routing an ungrounded electrical distribution system based on heuristic method with micro grids integration,” Sustainability, vol. 11, no. 6, p. 1607, 2019, doi: 10.3390/su11061607.
A. O. Salau, Y. W. Gebru, and D. Bitew, “Optimal network reconfiguration for power loss minimization and voltage profile enhancement in distribution systems,” Heliyon, vol. 6, no. 6, p. e04233, 2020, doi: 10.1016/j.heliyon.2020.e04233.
F. Pabón, E. Inga, and M. Campaña, “Planning underground power distribution networks to minimize negative visual impact in resilient smart cities,” Electricity, vol. 3, no. 3, pp. 463-479, 2022, doi: 10.3390/electricity3030024.
M. Mosbah, S. Arif, R. D. Mohammedi, and A. Hellal, “Optimum dynamic distribution network reconfiguration using minimum spanning tree algorithm,” in 2017 5th International Conference on Electrical Engineering Boumerdes (ICEE-B), pp. 1-6, 2017, doi: 10.1109/ICEE-B.2017.8192170.
H. Ahmadi and J. R. Martí, “Minimum-loss network reconfiguration: A minimum spanning tree problem,” Sustainable Energy, Grids and Networks, vol. 1, pp. 1-9, 2015, doi: 10.1016/j.segan.2014.10.001.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2025 Muhung Anggarawan, Hadi Permana, Fatia Amalia Maresti
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Copyright © by Author; Published by Institut Riset dan Publikasi Indonesia (IRPI)
This Indonesian Journal of Machine Learning and Computer Science is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
