Most of real-life competitive location models include conflicting objectives. Recently, a new multi-objective evolutionary algorithm, called FEMOEA, which can be applied to many nonlinear multi-objective optimization problems, has been proposed. It combines ideas from different multi- and single-objective optimization evolutionary algorithms, although it also incorporates a new method to improve the efficiency of points and a new stopping rule, which help to improve the quality of the obtained approximation of the Pareto-front and to reduce the computational requirements. FEMOEA has been compared to an interval branch-and-bound algorithm able to obtain an enclosure of the true Pareto-front as well as to the reference NSGA-II, SPEA2 and MOEA/D algorithms . Comprehensive computational studies have shown that, among the studied algorithms, FEMOEA provides better approximations. The computational time needed by FEMOEA may be not negligible at all when the set approximating the Pareto-front must have many points, because a high precision is required. Furthermore, the computational resources needed may be so high that a PC may run out of memory. In those cases, parallelizing the algorithm and run it in a supercomputer may be the best way forward. In this work, a parallelization of FEMOEA, called FEMOEA-Paral, is presented. To show its applicability, a bi-objective franchisor-franchisee facility location, already proposed in literature, is solved.