Abstract
A greedy heuristic-based algorithm was put forward to obtain the approximate optimal solution for the DUDC(discrete unit disk cover) problem within polynomial time. Firstly, discrete cells were generated to represent the 2D plane. Then, alternative sets which can cover certain amount of target points were built. A greedy algorithm was articulated to find a minimal combination of the alternative sets, and full coverage of all target points was realized. The minimal covering circles were calculated considering the position of each point in the sets. The center of the minimal covering circles was selected as the location. Based on a case study, the effectiveness of the proposed algorithm was validated. The factors of influence the performance of the algorithm were also discussed and ratio of time complexity and approximation was analyzed.
| Translated title of the contribution | A Greedy Heuristic-based Approach to Solving the Discrete Unit Disk Cover Problem |
|---|---|
| Original language | Chinese |
| Pages (from-to) | 78-85 |
| Number of pages | 8 |
| Journal | Huanan Ligong Daxue Xuebao/Journal of South China University of Technology (Natural Science) |
| Volume | 47 |
| Issue number | 12 |
| DOIs | |
| Publication status | Published - 2019 |
Keywords
- DUDC
- Greedy heuristic-based approach
- Location problem
- Urban service center