Summary: The Euclidean \(p\)-median problem is concerned with the decision of the locations for public service centres. Existing methods for the planar Euclidean \(p\)-median problems are capable of efficiently solving problems of relatively small scale. This paper proposes two new heuristic algorithms aiming at problems of large scale. Firstly, to reflect the different degrees of proximity to optimality, a new kind of local optimum called level-\(m\) optimum is defined. For a level-\(m\) optimum of a \(p\)-median problem, where \(m< p\), each of its subsets containing \(m\) of the \(p\) partitions is a global optimum of the corresponding \(m\)-median subproblem. Starting from a conventional local optimum, the first new algorithm efficiently improves it to a level-2 optimum by applying an existing exact algorithm for solving the 2-median problem. The second new algorithm further improves it to a level-3 optimum by applying a new exact algorithm for solving the 3-median problem. Comparison based on experimental results confirms that the proposed algorithms are superior to the existing heuristics, especially in terms of solution quality.