In this study, we propose a greedy randomized adaptive search procedure (GRASP) heuristic and a hybrid GRASP-Tabu heuristic. The hybrid GRASP-Tabu heuristic combines GRASP and tabu search to efficiently find lower bounds for large-scale instances for the maximal covering location problem with customer preference ordering. To evaluate the quality of the obtained bounds, we reformulate the problem as a single-level integer programming problem using valid inequalities, as in Cánovas et al. (2007) , to ensure that each customer is allocated to the most preferred facility among those that are opened. According to computational results, despite their simplicity, the proposed algorithms provide optimal or near optimal solutions in a small computation time.