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

Callaghan, Becky, Salhi, Said, Nagy, Gábor (2017) Speeding up the optimal method of Drezner for the p-centre problem in the plane. European Journal of Operational Research, 257 . pp. 722-734. ISSN 0377-2217. (doi:10.1016/j.ejor.2016.08.038)

Abstract

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.

Item Type:	Article
DOI/Identification number:	10.1016/j.ejor.2016.08.038
Uncontrolled keywords:	Location; p-centre problem; Continuous space; Z-maximal circles; Optimal algorithm
Subjects:	H Social Sciences
Divisions:	Faculties > Social Sciences > Kent Business School > Management Science Faculties > Social Sciences > Kent Business School > Centre for Logistics and Heuristic Organisation (CLHO)
Depositing User:	Said Salhi
Date Deposited:	10 Oct 2016 09:20 UTC
Last Modified:	15 Jul 2019 12:53 UTC
Resource URI:	https://kar.kent.ac.uk/id/eprint/57827 (The current URI for this page, for reference purposes)