Since van Groenigen and Stein (1998) proposed the SSA+MMSD (Spatial Simulated Annealing + Minimization of the Mean of Shortest Distances criterion) method, this method has found many applications in the optimization of sampling designs. However, it is computationally inefficient due to the complexity of this method itself. Initially in this paper, we analyze the computational complexity associated with this method from both SSA and MMSD aspects. And then, we propose some corresponding revisions (including the initial solution, perturbation rules, as well as the objective function) accordingly so as to reduce its computations. Finally, we evaluate the efficiency improvement via comparing some efficiency indexes of both original and modified methods (including the total perturbations needed, valid and better candidate designs generating rates of the perturbations, and the rate of objective function decline). Analysis and experimental results indicate that the modified method is much more efficient than the original one; in C++ implementations, the mean execution time needed for the modified method is only about 1/3 of that of the original.