Mobile stroke units (MSUs), which are specialized ambulances equipped with a brain imaging device and staffed with trained healthcare personnel, have the potential to provide rapid on-site diagnosis and treatment for stroke patients. To maximize the efficiency of utilizing MSUs, it is crucial to strategically allocate these units. When solving the MSU allocation problem, the current methods search the whole search space when looking for the optimal solutions, which causes slow convergence. In the current paper, we propose the Quality Clustering for Reducing the Search Space (QCRSS) framework to reduce the search space by filtering out ambulance locations without negatively affecting the quality of the solution too much when solving the MSU allocation problem. By narrowing down the set of possible locations, the problem becomes more manageable, leading to faster convergence when solving the MSU problem. Extensive experiments under the multiple MSU settings show that the QCRSS is large ly faster in convergence toward the optimal solution by reducing the search space by 5x, 11x, 26x, and 67x for two, three, four, and five MSUs, respectively. We illustrate the performance of the QCRSS through both qualitative and quantitative analyses.