We consider a generalized class of location–allocation problems, in which N new facilities are to be located in the plane with respect to M objects. Each object is associated with a convex cost function, specifying the expenses for serving the object from any location in the plane. For the resulting multi-dimensional mixed-integer optimization problem, we compare various traditional and new search methods. In particular, we apply multi-start, (variable) neighborhood search, tabu search, simulated annealing, an evolutionary algorithm and an ant colony optimization algorithm. They all have in common that they use the well-known alternate location and allocation algorithm [Cooper, L., 1964. Heuristic methods for location–allocation problems. SIAM Review 6, 37–53] as core local search function. We intend to impart a generalized view on these randomized search methods and also examine the efficiency of the different search strategies in solving the multi-connection location–allocation problem, a relatively new instance of the generalized class of location–allocation problems. Computational results show that the most crucial feature of the heuristics is the ability to combine a diversified search over the whole solution space with an intensified search near the best-known solution.