A Novel Parallel Algorithm with Map Segmentation for Multiple Geographical Feature Label Placement Problem
点击次数：
DOI码：
10.3390/ijgi10120826
发表刊物：
ISPRS International Journal of Geo-Information
关键字：
label placement; parallel algorithm; map segmentation; fast optimization; hybrid algorithm; scalability
摘要：
Multiple geographical feature label placement (MGFLP) is an NP-hard problem that can negatively influence label position accuracy and the computational time of the algorithm. The complexity of such a problem is compounded as the number of features for labeling increases, causing the execution time of the algorithms to grow exponentially. Additionally, in large-scale solutions, the algorithm possibly gets trapped in local minima, which imposes significant challenges in automatic label placement. To address the mentioned challenges, this paper proposes a novel parallel algorithm with the concept of map segmentation which decomposes the problem of multiple geographical feature label placement (MGFLP) to achieve a more intuitive solution. Parallel computing is then utilized to handle each decomposed problem simultaneously on a separate central processing unit (CPU) to speed up the process of label placement. The optimization component of the proposed algorithm is designed based on the hybrid of discrete differential evolution and genetic algorithms. Our results based on real-world datasets confirm the usability and scalability of the algorithm and illustrate its excellent performance. Moreover, the algorithm gained superlinear speedup compared to the previous studies that applied this hybrid algorithm.
合写作者：
Jiqiu Deng*, Zhiyong Guo
第一作者：
Mohammad Naser Lessani
论文类型：
期刊论文
文献类型：
J
卷号：
10
期号：
12
页面范围：
826
是否译文：
否
收录刊物：
SCI
学位：博士学位
职称：副教授
学科：地质资源与地质工程. 测绘科学与技术
所在单位：地球科学与信息物理学院