Name
Title | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.3390/ijgi11050270 | ISPRS INTERNATIONAL JOURNAL OF GEO-INFORMATION |
Keywords | DocType | Volume |
p-center problems, graph convolutional network, heuristic algorithm, minimum domain set, deep learning | Journal | 11 |
Issue | ISSN | Citations |
5 | 2220-9964 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Haojian Liang | 1 | 0 | 0.34 |
| Shaohua Wang | 2 | 0 | 1.35 |
| Huilai Li | 3 | 0 | 0.34 |
| Huichun Ye | 4 | 0 | 0.34 |
| Yang Zhong | 5 | 0 | 0.34 |