A bi-objective competitive facility location and design problem is considered. The problem of obtaining a complete representation of the efficient set and its corresponding Pareto-front has been previously tackled through exact general methods, but they require high computational effort. In this work, we propose a new evolutionary multi-objective optimization algorithm, named FEMOEA, which deals with the problem at hand in a fast and efficient way. It combines ideas from different multi-objective and single-objective optimization evolutionary algorithms, although it also incorporates new devices which help to reduce the computational requirements, and also to improve the quality of the provided solutions. The performance of the algorithm is analyzed by comparing it to other (meta)heuristics previously proposed in the literature. In particular, the reference algorithms MOEA/D, SPEA2 and NSGA-II have been considered. A comprehensive computational study shows that the new heuristic method outperforms, on average, the three heuristic algorithms. Additionally, it reduces, on average, the computing time of the exact methods by approximately 99%, and this offering high-quality discrete approximations of the true Pareto-front.