Evaluating Network Robustness for Electric Vehicle Charging Infrastructure in Qatar: A k-Dominating Set Approach

Abstract

This thesis addresses the robust placement of electric vehicle (EV) charging stations as a covering problem that must remain effective under adverse conditions such as com- ponent failures or demand surges. A robust coverage model is formulated as the k- Dominating Set Problem (k-DSP), which ensures that at least k charging stations serve each demand node. This built-in redundancy enhances network resilience so that even if a station fails or experiences an unexpected surge in usage, drivers can still find ser- vice nearby. Solving the k-DSP to optimality is NP-hard, making direct computation intractable for large networks and motivating the need for advanced solution strategies. To tackle this complexity, the thesis proposes a Matheuristic Fixed Set Search (MFSS) approach, which integrates exact mathematical programming techniques with a learning- based Fixed Set Search (FSS) metaheuristic. The MFSS method combines the strengths of mixed-integer programming with iterative refinement: it uses FSS’s learning mech- anism to identify promising subsets of charging station locations (the “fixed sets”). It uses mathematical programming to fill in the remaining decisions. The proposed MFSS algorithm is evaluated on standard benchmark instances, and its performance is com- pared against a classical Greedy Randomized Adaptive Search Procedure (GRASP) heuristic and the commercial solver CPLEX. Computational results demonstrate that MFSS consistently produces quality-competitive solutions with the best-known results from GRASP and CPLEX while achieving these solutions in a significantly reduced computation time. In addition to benchmark testing, the proposed model is applied to a case study on Qatar’s EV charging infrastructure using real-world geographic data. The analysis evaluates multiple robustness levels (k) under varying coverage radii, demonstrating that higher k values significantly enhance fault tolerance with marginal increases in infrastructure cost. These results confirm the effectiveness of the MFSS approach in producing scalable and resilient solutions suited to Qatar’s national EV deployment strategy. The k-DSP model, coupled with the MFSS algorithm, offers a robust planning framework that ensures uninterrupted service availability during station failures or peak demand conditions.

Date of Award	2025
Original language	American English
Awarding Institution	HBKU College of Science and Engineering