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.