Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

A new mathematical model and a Lagrangean decomposition for the point-feature cartographic label placement problem

Texto completo
Autor(es):
Mauri, Geraldo R. [1] ; Ribeiro, Glaydston M. [2] ; Lorena, Luiz A. N. [3]
Número total de Autores: 3
Afiliação do(s) autor(es):
[1] UFES, BR-29500000 Alegre, ES - Brazil
[2] UFES, BR-29933415 Sao Mateus, ES - Brazil
[3] Natl Inst Space Res INPE, BR-12210970 Sao Jose Dos Campos, SP - Brazil
Número total de Afiliações: 3
Tipo de documento: Artigo Científico
Fonte: Computers & Operations Research; v. 37, n. 12, p. 2164-2172, DEC 2010.
Citações Web of Science: 14
Resumo

This paper proposes a 0-1 integer linear programming model for the point-feature cartographic label placement problem based on labeling of the largest number of free labels. In addition, one non-trivial valid inequality is presented to strengthen this proposed model. Even with the strengthened model, a commercial solver was not able to solve a representative sample of known instances presented in the literature. Thus, we also present a Lagrangean decomposition technique based on graph partitioning. Our added approaches established optimal solutions for practically all the used instances and the results significantly improved the ones presented in recent studies concerning the problem. (C) 2010 Elsevier Ltd. All rights reserved. (AU)

Processo FAPESP: 04/11053-9 - Metodologia híbrida para resolução do problema dial-a-ride
Beneficiário:Geraldo Regis Mauri
Linha de fomento: Bolsas no Brasil - Doutorado