Optimizing Electric Vehicle Charging Station Placement in Banyumas Using Graph Domination Theory - Yogo Dwi Prasetyo; Hari Sumardi (UIN Sumatera Utara, 2025)
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.