Optimizing Electric Vehicle Charging Station Placement in Banyumas Using Graph Domination Theory
Abstract
This study applies graph theory to optimize the placement of electric vehicle (EV) charging stations in Banyumas Regency, Indonesia, using real geospatial data from 27 sub-districts. Each sub-district is modeled as a vertex, with edges defined by a 10 km coverage radius. The domination number is employed to identify the minimum number of charging stations required to ensure full spatial coverage. Unlike prior EV infrastructure studies in Indonesia that primarily rely on demand-based heuristics or clustering methods, this research explicitly guarantees coverage through graph domination theory. To enhance robustness, the domination-based solution is compared with a Set Covering Problem solved using Ant Colony Optimization (ACO). Both approaches consistently identify six strategic locations, achieving 100% coverage while reducing infrastructure requirements by approximately 78% compared to a one-station-per-sub-district strategy. The results provide practical guidance for policymakers and urban planners by supporting cost-efficient, scalable, and equitable EV charging infrastructure deployment in regions with early-stage EV adoption.
Keywords
Full Text:
PDFReferences
Gayathri, A., Muneera, A., Rao, T. N., & Rao, T. S. (2020). Study of various dominations in graph theory and its applications. International Journal of Scientific & Technology Research, 9(2), 3426–3429.
Hamidi, M., & Taghinezhad, M. (2023). Application of superhypergraphs-based domination number in real world. J. Mahani Mathematical Research, 13(1), 211–228. https://doi.org/10.22103/jmmr.2023.21203.1415
Bibi, K. A., Lakshmi, A., & Jothilakshmi, R. (2017). Applications of distance-2 dominating sets of graph in networks. Advances in Computational Sciences and Technology, 10(9), 2801–2810.
Yegnanarayanan, V., Balas, V. E., & Chitra, G. (2013). On certain graph domination numbers and applications. International Journal of Advanced Intelligence Paradigms. https://doi.org/10.1504/IJAIP.2014.062176W
Ahmad, U., & Batool, T. (2023). Domination in rough fuzzy digraphs with application. Soft Computing, 27, 2425–2442. https://doi.org/10.1007/s00500-022-07795-1
Rehman, F. U., Hussain, M. T., & Rashid, T. (2023). Strong pair domination number in intuitionistic fuzzy influence graphs with application for the selection of hospital having the optimal medical facilities. Expert Systems with Applications, 238, 122169. https://doi.org/10.1016/j.eswa.2023.122169
Khan, U. A., Ameen, N., Javaid, M., Arif, M., & Rahim, M. (2024). Domination Number in the Context of Some New Graphs. Processes, 62(1), 14. https://doi.org/10.3390/proceedings2024062014.
Chen, Y., Wang, X., Li, Z., & Zhang, H. (2024). A graph-based spatial clustering approach for optimizing electric vehicle charging infrastructure deployment in urban areas. Applied Energy, 355, 122305. https://doi.org/10.1016/j.apenergy.2023.122305.
Mousavi, S. M., Javid, M., & Ghofrani, M. (2024). An improved metaheuristic framework for optimal electric vehicle charging station allocation considering demand uncertainty. Energy, 292, 130400. https://doi.org/10.1016/j.energy.2023.130400.
Gautam, A., & Singh, K. (2024). Ant colony optimization for cost-efficient and demand-balanced placement of electric vehicle charging stations in smart cities. Expert Systems with Applications, 238, 121787. https://doi.org/10.1016/j.eswa.2023.121787.
Gonggiatgul, T., Shobaki, G., & Muyan-Özcelik, P. (2022). A parallel branch-and-bound algorithm with history-based domination and its application to the sequential ordering problem. Journal of Parallel and Distributed Computing, 172, 131–143. https://doi.org/10.1016/j.jpdc.2022.10.007
Behzad, A., Behzad, M., & Praeger, C. E. (2007). On the domination number of the generalized Petersen graphs. Discrete Mathematics, 308(4), 603–610. https://doi.org/10.1016/j.disc.2007.03.024
Ebrahimi, B. J., Jahanbakht, N., & Mahmoodian, E. S. (2009). Vertex domination of generalized Petersen graphs. Discrete Mathematics, 309(13), 4355–4361. https://doi.org/10.1016/j.disc.2009.01.018
Wu, P., Jiang, H., Nazari-Moghadam, S., Sheikholeslami, S. M., Shao, Z., & Volkman, L. (2019). Independent domination stable trees and unicyclic graphs. Mathematics, 7(9), 820. https://doi.org/10.3390/math7090820
Alanko, S., Crevals, S., Isopoussu, A., Ostergard, P., & Pettersson, V. (2011). Computing the domination number of grid graphs. The Electronic Journal of Combinatorics, 18, 1–18.
Leel, S., Srivastav, S., Gupta, S., & Ganesan, G. (2024). Domination number in the context of some new graphs. Engineering Proceedings, 62(14), 1–7. https://doi.org/10.3390/engproc2024062014
Bermudo, S. (2022). Upper bound for the geometric-arithmetic index of trees with given domination number. Discrete Mathematics, 346, 113172. https://doi.org/10.1016/j.disc.2022.113172
Lu, M., Liu, H., & Tian, F. (2005). Bounds of Laplacian spectrum of graphs based on the domination number. Linear Algebra and Its Applications, 402, 390–396. https://doi.org/10.1016/j.laa.2005.01.006
Shao, Z., Kosari, S., Chellali, M., Sheikholeslami, S. M., & Soroudi, M. (2020). On a relation between the perfect Roman domination and perfect domination numbers of a tree. Mathematics, 8(6), 966. https://doi.org/10.3390/math8060966
Dettlaff, M., Lemańska, M., Topp, J., Ziemann, R., & Żyliński, P. (2020). Certified domination. AKCE International Journal of Graphs and Combinatorics, 17(1), 86–97. https://doi.org/10.1016/j.akcej.2018.09.004
Zhou, Y., & Zhao, D. (2019). On domination coloring in graphs. arXiv preprint arXiv:1909.03715.
Ghanbari, N., Jäger, G., & Lehtilä, T. (2024). Super domination: Graph classes, products and enumeration. Discrete Applied Mathematics, 349, 8–24. https://doi.org/10.1016/j.dam.2024.01.039
Hoppen, C., & Mansan, G. (2019). Total domination in regular graphs. Electronic Notes in Theoretical Computer Science, 346, 523–533. https://doi.org/10.1016/j.entcs.2019.08.046
Armond, A. M., Prasetyo, Y. D., & Ediningrum, W. (2022). Application of Ant Colony Optimization (ACO) Algorithm to Optimize Trans Banyumas Bus Routes. Proceedings of the 2022 IEEE International Conference on Cybernetics and Computational Intelligence (CyberneticsCom). https://www.semanticscholar.org/paper/Application-of-Ant-Colony-Optimization-(ACO)-to-Bus-Armond-Prasetyo/075c7ea6918b2647aa67ff3cb3e5445a216df712
Awasthi, A., & Venkitachalam, A. (2021). Multi-objective optimization for sustainable electric vehicle charging network design using hybrid dominating–covering models. Sustainable Cities and Society, 72, 103025. https://doi.org/10.1016/j.scs.2021.103025
Daskin, M. S., & Schilling, D. A. (2011). Discrete network location models. In Network and discrete location: Models, algorithms, and applications (2nd ed.). Wiley. https://daskin.engin.umich.edu/wp-content/uploads/sites/133/2014/07/chapter3currentdaskinandschilling.pdf
Yang, Y., Li, K., & Qian, Y. (2023). Hybrid graph–covering models for resilient EV charging network design. Transportation Research Part C: Emerging Technologies, 156, 104297. https://doi.org/10.1016/j.trc.2023.104297
DOI: http://dx.doi.org/10.30829/zero.v9i3.25502
Refbacks
- There are currently no refbacks.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
Publisher : Department of Mathematics Faculty of Science and Technology Universitas Islam Negeri Sumatera Utara Medan | |
✉️ Email: zero_journal@uinsu.ac.id 📱 WhatsApp:085270009767 (Admin Official) | |
 |  |  |  |  |