Fechar
Metadados

@PhDThesis{Gomes:2015:DiDiDe,
               author = "Gomes, S{\'o}stenes Pereira",
                title = "Dispers{\~a}o discreta e decomposi{\c{c}}{\~a}o lagrangeana 
                         desbalanceada para o problema de rotula{\c{c}}{\~a}o 
                         cartogr{\'a}fica de pontos",
               school = "Instituto Nacional de Pesquisas Espaciais (INPE)",
                 year = "2015",
              address = "S{\~a}o Jos{\'e} dos Campos",
                month = "2015-05-18",
             keywords = "problema de rotula{\c{c}}{\~a}o cartogr{\'a}fica de pontos, 
                         otimiza{\c{c}}{\~a}o combinat{\'o}ria, dispers{\~a}o discreta, 
                         point-feature labeling problem, combinatorial optimization, 
                         discrete dispersion.",
             abstract = "Este trabalho aborda o Problema de Rotula{\c{c}}{\~a}o 
                         Cartogr{\'a}fica de Pontos (PRCP), que {\'e} um problema de 
                         otimiza{\c{c}}{\~a}o combinat{\'o}ria, demonstrado na 
                         literatura ser NP-dif{\'{\i}}cil. Considera-se que quando todos 
                         os pontos devem ser rotulados e sobreposi{\c{c}}{\~o}es de 
                         r{\'o}tulos s{\~a}o inevit{\'a}veis, o mapa pode ser mais 
                         leg{\'{\i}}vel se os r{\'o}tulos em conflito s{\~a}o 
                         posicionados de maneira dispersiva, isto {\'e}, se os 
                         r{\'o}tulos s{\~a}o posicionados o mais distante 
                         poss{\'{\i}}vel. Neste contexto, {\'e} apresentada uma nova 
                         abordagem para o problema, denominada Dispers{\~a}o Discreta, 
                         j{\'a} utilizada em Problemas de Localiza{\c{c}}{\~a}o de 
                         Facilidades em diversos trabalhos da literatura. Com esta nova 
                         abordagem, o PRCP foi formulado como um Problema de 
                         programa{\c{c}}{\~a}o inteira mista, de maneira a considerar as 
                         dist{\^a}ncias entre posi{\c{c}}{\~o}es candidatas. Um 
                         algoritmo gen{\'e}tico construtivo tamb{\'e}m foi desenvolvido, 
                         para obter resultados em inst{\^a}ncias mais complexas. Por fim, 
                         {\'e} proposta uma Decomposi{\c{c}}{\~a}o Lagrangeana 
                         desbalanceada, que permitiu obter a solu{\c{c}}{\~a}o {\'o}tima 
                         de diversas inst{\^a}ncias do PRCP, al{\'e}m de provar a 
                         otimalidade dos resultados j{\'a} existentes de outras 
                         inst{\^a}ncias. ABSTRACT: This work concerns to the Point-Feature 
                         Cartographic Labeling Problem (PFCLP), which is a NP-Hard 
                         combinatorial problem. It is considered that when all points must 
                         be labeled and overlaps are inevitable, the map can be more 
                         readable if overlapping labels are placed in a dispersive way, i. 
                         e., overlapping labels are distant from each other. Thus, we 
                         present a Discrete Dispersion approach, generally used in the 
                         Facility Location Problem, which considers distance values between 
                         candidate positions. A constructive genetic algorithm to obtain 
                         results in more complex instances is likewise presented. Finally, 
                         we propose an unbalanced Lagrangean Decomposition, which achieved 
                         the optimal solution of several instances of PFCLP, and proved the 
                         optimality of various results of literature.",
            committee = "Vijaykumar, Nandamudi Lankalapalli (presidente) and Lorena, Luiz 
                         Antonio Nogueira (orientador) and Ribeiro, Glaydston Mattos 
                         (orientador) and Carvalho, Solon Ven{\^a}ncio de and Becceneri, 
                         Jos{\'e} Carlos and Salles Neto, Luiz Ledu{\'{\i}}no de and 
                         Marins, Fernando Augusto Silva",
           copyholder = "SID/SCD",
         englishtitle = "Discrete dispersion and unbalanced Lagrangean decomposition for 
                         point-feature cartographic labeling problem",
             language = "pt",
                pages = "100",
                  ibi = "8JMKD3MGP3W34P/3JG3TF8",
                  url = "http://urlib.net/rep/8JMKD3MGP3W34P/3JG3TF8",
           targetfile = "publicacao.pdf",
        urlaccessdate = "05 dez. 2020"
}


Fechar