@article{Lessani2025, 
author = {M. Naser Lessani and Zhenlong Li and Jiqiu Deng and Zhiyong Guo},
title = {An MPI-based parallel genetic algorithm for multiple geographical feature label placement based on the hybrid of fixed-sliding models},
year = {2025},
journal = {Geo-Spatial Information Science},
volume = {28},
number = {2},
pages = {761-779},
keywords = {Label placement, fixed position, geographical features, parallel genetic algorithm, message passing interface},
url = {https://www.sciopen.com/article/10.1080/10095020.2024.2313326},
doi = {10.1080/10095020.2024.2313326},
abstract = {Multiple Geographical Feature Label Placement (MGFLP) has been a fundamental problem in geographic information visualization for decades. Moreover, the nature of label positioning has proven to be an Nondeterministic polynomial-time hard (NP-hard) problem. Although advances in computer technology and robust approaches have addressed the problem of label positioning, the lengthy running time of MGFLP has not been a major focus of recent studies. Based on a hybrid of the fixed-position and sliding models, a Message Passing Interface (MPI) parallel genetic algorithm is proposed in the present study for MGFLP to label mixed types of geographical features. To evaluate the quality of label placement, a quality function is defined based on four quality metrics: label-feature conflict; label-label conflict; label association with the corresponding feature; label position priority for all three types of features. The experimental results show that the proposed algorithm outperforms the DDEGA, DDEGA-NM, and Parallel-MS in both label placement quality and computation time efficiency. Across three datasets, compared to Parallel-MS, running times decreased from 118.45 to 8.34, 45.98 to 3.51, and 20.01 to 0.43 min, with further reductions in label-label and label-feature conflicts.}
}