The p-median problem is one of the discrete optimization problem in location theory which aims to satisfy total demand with minimum cost. A high-level algorithmic approach can be specialized to solve optimization problem. In recent years, meta-heuristic methods have been applied to support the solution of Combinatorial Optimization Problems (COP). Collision Bodies Optimization algorithm (CBO) and Enhanced Colliding Bodies Optimization (ECBO) are two recently developed continuous optimization algorithms which have been applied to some structural optimization problems. The main goal of this paper is to provide a useful comparison between capabilities of these two algorithms in solving p-median problems. Comparison of the obtained results shows the validity and robustness of these two new meta-heuristic algorithms for p-median problem.