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 contributionA Greedy Heuristic-based Approach to Solving the Discrete Unit Disk Cover Problem
Original languageChinese
Pages (from-to)78-85
Number of pages8
JournalHuanan Ligong Daxue Xuebao/Journal of South China University of Technology (Natural Science)
Volume47
Issue number12
DOIs
Publication statusPublished - 2019

    Research areas

  • DUDC, Greedy heuristic-based approach, Location problem, Urban service center

ID: 70895301