We consider the problem of locating chargers for a fleet of electric vehicles operating a ride-hailing service with the objective of maximizing its operational profit. One of the main challenges of the problem lies in the fact that controlling the operation of the fleet is itself a stochastic dynamic problem, which makes a direct modeling approach extremely challenging. In practice, the most effective way of evaluating the performance of a particular charger configuration is to simulate its operation and measure its profit. Thus, the problem is formulated as a Discrete Simulation-based Optimization (DSO) problem. Due to the black-box nature of simulators, methods employed for DSOs tend to rely on iteratively sampling and partitioning the solution space so as to progressively concentrate the sampling effort on the most promising portions of the feasible space. To boost the effectiveness of such methods, it is fundamental to be able to quickly identify which portions of the feasible region are relevant to explore through an effective partitioning scheme. In our approach, we consider the use of a clustering approach to partition the search space of the DSO problem and identify high-quality regions of the search space.