A Trade-Off Algorithm for Solving p-Center Problems with a Graph Convolutional Network

Abstract

The spatial optimization method between combinatorial optimization problems and GIS has many geographical applications. The p-center problem is a classic NP-hard location modeling problem, which has essential applications in many real-world scenarios, such as urban facility locations (ambulances, fire stations, pipelines maintenance centers, police stations, etc.). This study implements two methods to solve this problem: an exact algorithm and an approximate algorithm. Exact algorithms can get the optimal solution to the problem, but they are inefficient and time-consuming. The approximate algorithm can give the sub-optimal solution of the problem in polynomial time, which has high efficiency, but the accuracy of the solution is closely related to the initialization center point. We propose a new paradigm that combines a graph convolution network and greedy algorithm to solve the p-center problem through direct training and realize that the efficiency is faster than the exact algorithm. The accuracy is superior to the heuristic algorithm. We generate a large amount of p-center problems by the Erdos–Renyi graph, which can generate instances in many real problems. Experiments show that our method can compromise between time and accuracy and affect the solution of p-center problems.

Keywords

• p-center problems
• graph convolutional network
• heuristic algorithm
• minimum domain set
• deep learning