{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T14:34:49Z","timestamp":1776436489328,"version":"3.51.2"},"reference-count":34,"publisher":"MDPI AG","issue":"5","license":[{"start":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T00:00:00Z","timestamp":1558396800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"the National Key R&amp;D Program of China","award":["2017YFC0601503"],"award-info":[{"award-number":["2017YFC0601503"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IJGI"],"abstract":"<jats:p>Label placement is a difficult problem in automated map production. Many methods have been proposed to automatically place labels for various types of maps. While the methods are designed to automatically and effectively generate labels for the point, line and area features, less attention has been paid to the problem of jointly labeling all the different types of geographical features. In this paper, we refer to the labeling of all the graphic features as the multiple geographical feature label placement (MGFLP) problem. In the MGFLP problem, the overlapping and occlusion among labels and corresponding features produces poorly arranged labels, and results in a low-quality map. To solve the problem, a hybrid algorithm combining discrete differential evolution and the genetic algorithm (DDEGA) is proposed to search for an optimized placement that resolves the MGFLP problem. The quality of the proposed solution was evaluated using a weighted metric regarding a number of cartographical rules. Experiments were carried out to validate the performance of the proposed method in a set of cartographic tasks. The resulting label placement demonstrates the feasibility and the effectiveness of our method.<\/jats:p>","DOI":"10.3390\/ijgi8050237","type":"journal-article","created":{"date-parts":[[2019,5,21]],"date-time":"2019-05-21T10:52:51Z","timestamp":1558435971000},"page":"237","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["A Hybrid of Differential Evolution and Genetic Algorithm for the Multiple Geographical Feature Label Placement Problem"],"prefix":"10.3390","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5964-9301","authenticated-orcid":false,"given":"Fuyu","family":"Lu","sequence":"first","affiliation":[{"name":"School of Geosciences and Info-Physics, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0729-1018","authenticated-orcid":false,"given":"Jiqiu","family":"Deng","sequence":"additional","affiliation":[{"name":"School of Geosciences and Info-Physics, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiyu","family":"Li","sequence":"additional","affiliation":[{"name":"School of Geosciences and Info-Physics, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hao","family":"Deng","sequence":"additional","affiliation":[{"name":"School of Geosciences and Info-Physics, Central South University, Changsha 410083, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2019,5,21]]},"reference":[{"key":"ref_1","unstructured":"Schrijver, A. (2004). Combinatorial Optimization: Polyhedra and Efficiency, Springer."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1179\/caj.1972.9.2.99","article-title":"The Logic of Automated Map Lettering","volume":"9","author":"Yoeli","year":"1972","journal-title":"Cartogr. J."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"128","DOI":"10.1559\/152304075784313304","article-title":"Positioning Names on Maps","volume":"2","author":"Imhof","year":"1975","journal-title":"Am. Cartogr."},{"key":"ref_4","unstructured":"Marks, J., and Shieber, S. (1991). The Computational Complexity of Cartographic Label Placement, Harvard University. Technical Report TR-05-91."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Formann, M., and Wagner, F. (1991, January 10\u201312). A packing problem with applications to lettering of maps. Proceedings of the Seventh Annual Symposium on Computational Geometry, North Conway, NH, USA.","DOI":"10.1145\/109648.109680"},{"key":"ref_6","first-page":"228","article-title":"Practical Results Using Simulated Annealing for Point Feature Label Placement","volume":"24","author":"Zoraster","year":"1997","journal-title":"Cartogr. Geogr. Inf. Syst."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"2164","DOI":"10.1016\/j.cor.2010.03.005","article-title":"A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem","volume":"37","author":"Mauri","year":"2010","journal-title":"Comput. Oper. Res."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/j.eswa.2017.11.014","article-title":"Towards unambiguous map labeling-Integer programming approach and heuristic algorithm","volume":"98","year":"2018","journal-title":"Expert Syst. Appl."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"5878","DOI":"10.1016\/j.eswa.2013.04.035","article-title":"Dispersion for the point-feature cartographic label placement problem","volume":"40","author":"Gomes","year":"2013","journal-title":"Expert Syst. Appl."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1016\/j.cageo.2007.01.007","article-title":"A greedy randomized adaptive search procedure for the point-feature cartographic label placement","volume":"34","author":"Cravo","year":"2008","journal-title":"Comput. Geosci."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"266","DOI":"10.1287\/ijoc.9.3.266","article-title":"Placing text labels on maps and diagrams using genetic algorithms with masking","volume":"9","author":"Verner","year":"1997","journal-title":"INFORMS J. Comput."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.jher.2008.10.001","article-title":"Comparison between genetic algorithm and linear programming approach for real time operation","volume":"2","author":"Azamathulla","year":"2008","journal-title":"J. Hydro-Environ. Res."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Li, L., Zhang, H., Zhu, H., Kuai, X., and Hu, W. (2016). A Labeling Model Based on the Region of Movability for Point-Feature Label Placement. ISPRS Int. J. Geo-Inf., 5.","DOI":"10.3390\/ijgi5090159"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1007\/0-387-25383-1_13","article-title":"A Constructive Genetic Approach to Point-Feature Cartographic Label Placement","volume":"32","author":"Yamamoto","year":"2005","journal-title":"Metaheuristics Prog. Real Probl. Solv."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1111\/gean.12082","article-title":"A Constructive Genetic Algorithm for Discrete Dispersion on Point Feature Cartographic Label Placement Problems","volume":"48","author":"Gomes","year":"2016","journal-title":"Geogr. Anal."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/129617.129620","article-title":"A rule-based system for dense-map name placement","volume":"35","author":"Doerschler","year":"1992","journal-title":"Commun. ACM"},{"key":"ref_17","unstructured":"Wolff, A., Knipping, L., Kreveld, M.v., Strijk, T., and Agarwal, P.K. (1997). A Simple and Efficient Algorithm for High-Quality Line Labeling, Department of Computer Science, Utrecht University. Technical Report UU-CS-2001-44."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Sun, S., Zhao, H., Fang, J., Cheng, Z., and Zhao, Y. (2010, January 18\u201320). A pratical Method for Line Labeling. Proceedings of the 18th International Conference on Geoinformatics: GIScience in Change, Peking University, Beijing, China.","DOI":"10.1109\/GEOINFORMATICS.2010.5567478"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"1368","DOI":"10.1007\/s12665-016-6190-4","article-title":"A grid algorithm suitable for line and area feature label placement","volume":"75","author":"Wu","year":"2016","journal-title":"Environ. Earth Sci."},{"key":"ref_20","unstructured":"Pfefferkorn, C., Burr, D., Harrison, D., and Heckman, B. (1985, January 11\u201314). A Cartographic Expert System. Proceedings of the Seventh International Symposium on Autocarto, Falls Church, VA, USA."},{"key":"ref_21","first-page":"101","article-title":"A Program for Automatic Name Placement","volume":"21","author":"Ahn","year":"1984","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1179\/1743277414Y.0000000091","article-title":"A Practical Algorithm for the External Annotation of Area Features","volume":"54","author":"Rylov","year":"2016","journal-title":"Cartogr. J."},{"key":"ref_23","first-page":"13","article-title":"A General Cartographic Labelling Algorithm","volume":"33","author":"Edmondson","year":"1996","journal-title":"Cartogr. Int. J. Geogr. Inf. Geovis."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1142\/S0218195903001062","article-title":"A unified approach to automatic label placement","volume":"13","author":"Kakoulis","year":"2003","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1559\/152304006777323127","article-title":"Placing Text and Icon Labels Simultaneously: A Real-Time Method","volume":"33","author":"Zhang","year":"2006","journal-title":"Cartogr. Geogr. Inf. Sci."},{"key":"ref_26","unstructured":"Price, K.V., Storn, R.M., and Lampinen, J.A. (2005). Differential Evolution: A Practical Approach to Global Optimization, Springer."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"3516","DOI":"10.1007\/s11771-012-1437-z","article-title":"Differential evolution with controlled search direction","volume":"19","author":"Jia","year":"2012","journal-title":"J. Cent. South Univ."},{"key":"ref_28","unstructured":"Ebinger, L.R., and Goulette, A.M. (2019, April 12). Automated Name Palcement in a Non-Interactive Environment. Available online: https:\/\/pdfs.semanticscholar.org\/114f\/ab94f3b7c96cf1992cf66f171828ed310966.pdf."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"435","DOI":"10.1007\/s10107-002-0327-9","article-title":"Optimal labeling of point features in rectangular labeling models","volume":"94","author":"Klau","year":"2003","journal-title":"Math. Program."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1007\/s10878-007-9073-5","article-title":"Column generation approach for the point-feature cartographic label placement problem","volume":"15","author":"Ribeiro","year":"2008","journal-title":"J. Comb. Optim."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"396","DOI":"10.1016\/j.ejor.2007.10.002","article-title":"POPMUSIC for the point feature label placement problem","volume":"192","author":"Alvim","year":"2009","journal-title":"Eur. J. Oper. Res."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1023\/A:1008202821328","article-title":"Differential Evolution\u2013A Simple and Efficient Heuristic for global Optimization over Continuous Spaces","volume":"11","author":"Storn","year":"1997","journal-title":"J. Glob. Optim."},{"key":"ref_33","unstructured":"(2019, April 10). What Is the Maplex Label Engine?. Available online: http:\/\/desktop.arcgis.com\/zh-cn\/arcmap\/10.3\/map\/working-with-text\/what-is-maplex-.htm."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Gomarasca, M.A. (2009). Elements of Cartography, Springer.","DOI":"10.1007\/978-1-4020-9014-1_2"}],"container-title":["ISPRS International Journal of Geo-Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/5\/237\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T12:53:55Z","timestamp":1760187235000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2220-9964\/8\/5\/237"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,5,21]]},"references-count":34,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2019,5]]}},"alternative-id":["ijgi8050237"],"URL":"https:\/\/doi.org\/10.3390\/ijgi8050237","relation":{},"ISSN":["2220-9964"],"issn-type":[{"value":"2220-9964","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,5,21]]}}}