Speeding up the optimal method of Drezner for the p-centre problem in the plane

•Revisit an optimal algorithm for the continuous p-centre problem.•Introduce neighbourhood reduction schemes.•Present lemmas and proofs to support the validity of the above schemes.•Produce an adaptive CPLEX policy.•Solve much larger problems optimally for the first time.

This paper revisits an early but interesting optimal algorithm first proposed by Drezner to solve the continuous p-centre problem. The original algorithm is reexamined and efficient neighbourhood reductions which are mathematically supported are proposed to improve its overall computational performance. The revised algorithm yields a considerably high reduction in computational time reaching, in some cases, a decrease of 96%. This new algorithm is now able to find proven optimal solutions for large data sets with over 1300 demand points and various values of p for the first time.