This paper addresses the Bi-objective Maximal Covering Location Problem with Compactness (BOMCLP-C), a new variant of the classical maximal covering location problem that simultaneously maximizes total demand coverage and minimizes the spatial dispersion of selected facilities. The problem is NP-hard and exhibits a highly multimodal search space due to the combinatorial interaction between coverage and compactness objectives under cardinality constraints. To effectively approximate its Pareto front, two evolutionary multi-objective optimization paradigms are investigated: NSGA-II, representing dominance-based search, and MOEA/D, representing decomposition-based search. For each paradigm, two variants are implemented: a penalty-based formulation that relaxes the facility-count constraint through additive penalties, and a customized constraint-handling variant enhanced with local search (LS) that maintains feasibility and refines solutions in the neighborhood structure. Computational experiments on real-world instances drawn from the literature demonstrate that LS-based variants consistently achieve higher-quality Pareto fronts, attaining full feasibility and superior hypervolume values. A Wilcoxon signed-rank analysis confirms the significant performance difference between NSGA-II-LS and MOEA/D-LS. The study shows the effectiveness of integrating problem-specific constraint handling and local improvement in evolutionary multi-objective frameworks for large-scale discrete location optimization. It emphasizes the need for concise, feasible space representation when dealing with integer or combinatorial constraints.