A Novel Parallel Algorithm with Map Segmentation for Multiple Geographical Feature Label Placement Problem

Release time:2022-04-01

DOI number:10.3390/ijgi10120826

Journal:ISPRS International Journal of Geo-Information

Key Words:label placement; parallel algorithm; map segmentation; fast optimization; hybrid algorithm; scalability

Abstract: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.

Co-author:Jiqiu Deng*, Zhiyong Guo

First Author:Mohammad Naser Lessani

Indexed by:Journal paper

Document Type:J

Volume:10

Issue:12

Page Number:826

Translation or Not:no

Date of Publication:2021-12-06

Included Journals:SCI

Links to published journals:https://www.mdpi.com/2220-9964/10/12/826