Based on the mathematical model and specific features of a P-median problem, the subtraction operator between the location and the location of bats, the addition operator between the velocity and location as well as the feasible function were redefined. The idea of crossover in genetic algorithm was introduced in order to perform a local search on the current solution and a hybrid bat algorithm (HBA) was proposed for the problem. By some tests on the P-median problem and comparisons with other algorithms, the computational results show that the hybrid bat algorithm is feasible and efficient for solving P-median problems.