A greedy randomized adaptive search procedure for the point-feature cartographic label placement

被引：28

作者：

Cravo, Gildasio Lecchi ^{[1
]}

Ribeiro, Glaydston Mattos ^{[2
]}

Nogueira Lorena, Luiz Antonio ^{[3
]}

机构：

[1] UNIARACRUZ, Fac Aracruz, BR-29194910 Aracruz, ES, Brazil

[2] Univ Fed Espirito Santo, UFES, BR-29933480 Mateus, ES, Brazil

[3] INPE, Brazilian Space Res Inst, BR-12227010 Sao Jose Dos Campos, Brazil

来源：

COMPUTERS & GEOSCIENCES | 2008年 / 34卷 / 04期

关键词：

GRASP; heuristic; label placement;

D O I：

10.1016/j.cageo.2007.01.007

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The point-feature cartographic label placement problem (PFCLP) is an NP-hard problem, which appears during the production of maps. The labels must be placed in predefined places avoiding overlaps and considering cartographic preferences. Owing to its high complexity, several heuristics have been presented searching for approximated solutions. This paper proposes a greedy randomized adaptive search procedure (GRASP) for the PFCLP that is based on its associated conflict graph. The computational results show that this metaheuristic is a good strategy for PFCLP, generating better solutions than all those reported in the literature in reasonable computational times. (C) 2007 Elsevier Ltd. All rights reserved.

引用

页码：373 / 386

页数：14

共 42 条

[1]

Abello J., 1999, External Memory Algorithms. DIMACS Workshop External Memory Algorithms and Visualization, P119

[2] Parallel GRASP with path-relinking for job shop scheduling [J].

Aiex, RM ;

Binato, S ;

Resende, MGC .

PARALLEL COMPUTING, 2003, 29 (04) :393-430

[3]

Atkinson JB, 1998, J OPER RES SOC, V49, P700, DOI 10.1038/sj.jors.2600521

[4] OPERATIONS SEQUENCING IN DISCRETE PARTS MANUFACTURING [J].

BARD, JF ;

FEO, TA .

MANAGEMENT SCIENCE, 1989, 35 (02) :249-255

[5] An empirical study of algorithms for point-feature label placement [J].

Christensen, J ;

Marks, J ;

Shieber, S .

ACM TRANSACTIONS ON GRAPHICS, 1995, 14 (03) :203-232

[6]

Christensen J, 1994, GRAPHICS GEMS, P497

[7] A GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURE FOR MAXIMUM INDEPENDENT SET [J].

FEO, TA ;

RESENDE, MGC ;

SMITH, SH .

OPERATIONS RESEARCH, 1994, 42 (05) :860-878

[8] GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].

FEO, TA ;

RESENDE, MGC .

JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133

[9] A GRASP-STAR FOR A DIFFICULT SINGLE-MACHINE SCHEDULING PROBLEM [J].

FEO, TA ;

VENKATRAMAN, K ;

BARD, JF .

COMPUTERS & OPERATIONS RESEARCH, 1991, 18 (08) :635-643

[10] A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM [J].

FEO, TA ;

RESENDE, MGC .

OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :67-71

← 1 2 3 4 5 →