华南理工大学学报(自然科学版)

作者：王淼 吴松涛 李永哲 武悦

单位：1. 哈尔滨工业大学2. 代尔夫特理工大学

基金：国家自然科学基金

共享经济所提出的城市综合体模式，具有有限服务半径的特点。城市综合体选址问题的基本数学模型为离散单位圆盘覆盖（DUDC）问题。该问题考虑用若干给定半径r的离散单位圆盘对平面中n个离散点进行覆盖。其研究目的是用最少数量的圆盘覆盖全部离散点。本文提出了一种基于贪心启发式的计算方法，可以在多项式时间复杂度内获得DUDC问题的近似最优解。首先生成了可替代二维平面的离散单元格，在每一单元格中心建立能够覆盖一定数量目标点的替代集，使用贪心算法确定替代集的最小组合方式，实现了对目标点的全覆盖。基于每个子集内所包含的点的具体位置，计算了其最小覆盖圆。最小覆盖圆的中心视为选址位置。基于具体案例证明了算法的有效性。讨论了该算法的影响因素，分析了时间复杂度以及近似度比率。

来源：2019年第12期

《华南理工大学学报(自然科学版)》期刊编辑部

查看华南理工大学学报(自然科学版)杂志2019年第12期