Genetic algorithm to solve the p-centre and p-radius problem on a network

Abstract

The p-centre problem is to locate p facilities on a network so as to minimize the largest distance from a demand point to its nearest facility. The problem is NP-complete for an arbitrary network. In this paper, genetic algorithms (GAs) to solve this problem are developed via two different representations. The nodes are taken as weighted, and the demand points are assumed to coincide with the nodes. Computational results obtained from the proposed GAs for different network sizes and different values of p are presented and compared for two different representations.

Keywords:

• Genetic algorithm
• p-centre problem
• Facility location problem
• Network

Acknowledgements

This work is supported in part by UGC, India (grant no. FA 17-130/98 (SA-I)).