Locating a semi-obnoxious facility, like an airport or correctional center is typically a bi-criterion problem combining a convex objective function representing minimum transportation cost with a multi-extremal objective function representing the non-desirable part of the facility. Generic one or bi-objective heuristic methods can be applied to generate efficient locations for the problem. We consider the location of one facility in the plane and show that a simple random or grid search with filtering already provides a very good picture of the trade-off between the two objectives. Moreover, we argue that instead of using bi-criterion meta-heuristics, one could better exploit the convex-nonconvex structure of the problem applying the constraint method. We show how to evaluate the methods systematically using several heuristics from literature.