文章基本信息

标题：A Trade-Off Algorithm for Solving p-Center Problems with a Graph Convolutional Network
本地全文：下载
作者：Haojian Liang ; Shaohua Wang ; Huilai Li 等
期刊名称：ISPRS International Journal of Geo-Information
电子版ISSN：2220-9964
出版年度：2022
卷号：11
期号：5
页码：270
DOI：10.3390/ijgi11050270
语种：English
出版社：MDPI AG
摘要：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.