Colaboradores por Instituição:

Os problemas de Localização de Facilidades continuaram a ser estudados considerando uma nova relaxação para problemas de Otimização Combinatória, proposta e desenvolvida como tese de doutorado de Marcelo Gonçalves Narciso. A nova relaxação combina duas relaxações conhecidas (Lagrangeana e surrogate) e produz os mesmos limites da relaxação Lagrangeana usual, mas com significativos ganhos (de até 75%) em tempo computacional para problemas de grande porte. A relaxação Lagrangeana/surrogate foi aplicada com sucesso aos seguintes problemas: Problema Generalizado de Atribuição (com Marcelo Narciso - dois trabalhos), o Problemas de Localização (p-Medianas, Localização Capacitado e Não-capacitado), em cooperação com o Prof. Edson L. Senne da FEG-UNESP.

Os Algoritmos Genéticos foram considerados como um método construtivo para a formação de uma população com o máximo de informação possível sobre o problema em questão. Na tese de doutorado de João Carlos Furtado foram conseguidos excelentes resultados para os seguintes problemas de "clustering": p-medianas, p-medianas capacitado e particionamento de grafos. Várias outras aplicações tem sido desenvolvidas usando essa nova abordagem de algoritmos evolutivos.

A metaheurística Busca Tabu foi aplicada com sucesso ao problema de rotulação de mapas.

O projeto temático Análise de Redes com Sistemas de Informações Geográficas - ARSIG foi concluído em junho de 1999. Com relação à pesquisa, nosso saldo foi muito bom, contando no período com 3 publicações em revistas internacionais, 4 em revistas nacionais, 2 trabalhos aceitos para publicação em revista internacional, 2 teses de doutorado defendidas, 2 dissertações de mestrado, 11 trabalhos de iniciação científica, 19 trabalhos apresentados em congressos, 10 trabalhos submetidos para publicação em revistas, 2 relatórios técnicos e um capítulo de livro. Completando um total de 56 trabalhos científicos.

Um novo projeto temático (Sistemas de Apoio à Decisão usando Redes e Sistemas de Informações Geográficas - ARSIG-2) foi submetido à FAPESP em julho de 1999, visando a continuação das pesquisas e integrações iniciadas no ARSIG. Neste projeto propõe-se alem de ampliar a participação da FEG/UNESP, também a cooperação com o Departamento de Processamento de Imagens do INPE e o CNPTIA da EMBRAPA em Campinas.

• A relaxação Lagrangeana/surrogate foi aplicada com sucesso aos seguintes problemas de localização de facilidades: p-medianas, localização capacitado e não-capacitado, em cooperação entre os pesquisadores Luiz A. N. Lorena e Edson L. F. Senne da FEG/UNESP. Um trabalho foi aceito para publicação em revista internacional e outro submetido para publicação. Os resultados de trabalhos anteriores sobre p-medianas foram sensivelmente melhorados, com a introdução de um algoritmo de localização-alocação alternada, usado para viabilizar soluções duais no processo de otimização por subgradientes.

• Algoritmo Genético Construtivo (AGC) proposto na tese de doutorado de João Carlos Furtado foi aplicado aos problemas de clustering: p-medianas, p-medianas capacitado e particionamento de grafos capacitados. Um trabalho foi submetido para publicação em revista internacional. Trabalhos foram apresentados em congresso internacional e nacional.

• A aluna Helena Kiyoka Kobayashi realizou trabalho de Iniciação Científica (orientação conjunta de Luiz A N. Lorena e Geraldo Ribeiro Filho) sobre o assunto: Implementação e Análise do Problema das p-medianas usando Algoritmo Genético Construtivo. O algoritmo proposto na tese de J. C. Furtado, foi programado em JAVA, proporcionando a usuários de Internet testar on-line a aplicação do AGC para problemas definidos na tela do computador. O trabalho da Helena foi indicado como melhor trabalho apresentado na sessão de Ciências Exatas e Tecnologia durante a apresentação oral do I Congresso de Iniciação Científica (PIBIC/CNPq/UMC) realizado na Universidade de Mogi das Cruzes (veja: http://matter.ccet.umc.br/~helena/AGC.html).

• O AGC está sendo aplicado na tese de doutorado de Reinaldo G. Arakaki (com orientação de Luiz A N. Lorena) para uma fase de clustering, existente no problema clássico de roteamento de veículos, onde o problema é tratado como um problema de localização (p-medianas capacitado).

• Novos problemas de localização estão sendo considerados para futuras pesquisas, como o de máxima cobertura, de localização de hubs (p-hub), e outros. Deseja-se fazer uma distinção entre as aplicações para setor público e privado, como é comum nas aplicações da área. Pretende-se aplicar o AGC e heurísticas duais (Lagrangeana/surrogate) aos problemas identificados.

• O problema de roteamento de veículos tem sido tratado através do AGC para o problema clássico de um depósito e possíveis extensões. O aluno de doutorado Reinaldo Arakaki vem modelando e implementando o AGC para os problemas, e resultados preliminares foram apresentados em sua defesa preliminar em junho/99.

• Um problema clássico, relacionado ao roteamento de veículos, usado na fase de clustering é o Problema Generalizado de Atribuição (PGA). A aplicação da relaxação Lagrangeana/surrogate ao PGA resultou em resultados excelentes com grande economia de tempo computacional, principalmente para a Decomposição Lagrangeana. Um artigo publicado em revista internacional (autores Marcelo G. Narciso e Luiz A N Lorena) confirma esses resultados para uma grande amostra de instancias.

• Está sendo desenvolvida em cooperação entre os pesquisadores Luiz A N. Lorena, Marcelo G. Narciso e John Beasley (Imperial College) uma aplicação do AGC para o PGA. Os resultados obtidos são muito bons quando comparados a aplicação de Algoritmos Genéticos clássicos. Pretende-se apresentá-los em congresso internacional e revista internacional.

• Foi submetido para revista internacional (autores Luiz A N. Lorena e Marcelo G. Narciso) um resultado da tese de doutorado de Marcelo Narciso: uma aplicação da relaxação Lagrangeana/surrogate ao problema simétrico do Caixeiro Viajante. Neste trabalho o método usual de subgradientes e´ melhorado usando as informações locais da relaxação surrogate . Este trabalho também está aceito para apresentação no IFORS´99, a ser realizado na China em agosto de 1999.

• A aluna Missae Yamamoto estudou em sua dissertação de mestrado (orientação conjunta de Luiz A N. Lorena e Gilberto Câmara) um problema de Otimização Combinatória que surge na confecção automática de mapas usando SIGs. O problema é conhecido como rotulação de pontos. Basicamente o problema é o de escrever rótulos em pontos (nomes de cidades,...) de forma clara e evitando conflitos entre rótulos (não podem ocupar o mesmo espaço). O problema foi modelado e resolvido usando busca tabu, tendo sido obtidos resultados melhores que os da literatura para um conjunto padrão de dados. Seu trabalho foi submetido e aceito para apresentação no MIC´99 - III Metaheuristics International Conference. Também deve ser apresentado no GISBRASIL´99. Uma versão foi submetida para publicação em revista internacional.

A integração de algoritmos para problemas de localização foi iniciada considerando o problema mais estudado até o momento, o problema das p-medianas, e dentre os SIGs adquiridos no projeto temático ARSIG, o considerado de mais fácil aprendizagem, o ArcView.

• O aluno de iniciação científica Alex Adriano Pinto (orientado do Prof. Edson L. F. Senne – FEG/UNESP) adaptou uma script do ArcView para realizar a sua comunicação com o código executável pmedian.exe , compilado na linguagem C e que aplica a heurística Lagrangean/surrogate de Senne e Lorena (Senne, E. L. F. and Lorena, L. A. N. Lagrangean/surrogate heuristics for p-median problems, 1999).

• A bolsista (PCI-CNPq) Solange P. B. Marcondes melhorou a script inicial e apresentou um guia de aplicação do algoritmo de p-medianas no ArcView, para possíveis usuários. A nova script , o programa executável e o guia estão disponibilizados via Internet na página do projeto ARSIG (http://www.lac.inpe.br/~lorena/ArsigIndex.html). Por enquanto as distâncias consideradas não levam em conta a rede urbana, usa-se somente um tema de pontos, com distâncias Euclidianas.

• Foi iniciada a integração dos algoritmos ao sistema SPRING, um SIG completo em desenvolvimento no INPE, em trabalho conjunto com o pesquisador João Argemiro C. Paiva, do DPI/INPE. O mesmo software para problemas das p-medianas foi integrado ao SPRING. Na versão atual, as distâncias podem ser Euclidianas ou considerar características da rede urbana. Também alguns algoritmos relacionados a transportes e roteamento foram implementados. Basicamente os algoritmos de Djkstra e Floyd, para calcular caminhos mínimos em um grafo. Algumas possíveis aplicações estão assinaladas. Uma nova versão do SPRING foi lançada no GISBRASIL´99, já incluindo a versão beta do módulo de redes. Está disponível na Internet na página http://www.dpi.inpe.br/spring/ .

Narciso, M. G. and Lorena, L. A. N. Lagrangean/surrogate Relaxation for Generalized Assignment Problems. European Journal of Operational Research, 114(1), 165-177, 1999.

Lorena, L. A. N. and Senne, E. L. F. Improving traditional subgradient scheme for Lagrangean relaxation: an application to location problems, International Journal of Mathematical Algorithms - aceito em março de1999.

Senne, E. L. F. and Lorena, L. A. N. Lagrangean/surrogate heuristics for p-median problems Submetido para publicação (em maio 1999) no livro "OR Computing Tools for the New Millennium" que será editado após o congresso 7th INFORMS Computing Society Conference on OR Computing Tools for the New Millennium, January 5-7, 2000 - Cancún, México

Lorena, L. A. N. and Furtado, J. C. Constructive genetic algorithm for clustering problems. Evolutionary Computation, out. 1998

Lorena, L. A N. and Narciso, M. G. Using local surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. Submetido ao European Journal of Operational Reserach, nov. 98

Yamamoto, M, Câmara, G. and Lorena, L. A N. Tabu search heuristic for point-feature cartographic label placement. Submetido a Geoinformatica, em maio 1999.

Lorena, L. A. N. and Furtado, J. C. Constructive genetic algorithm for clustering problems. Apresentado no Optimization 98- Coimbra, Portugal - 20-22 julho de 1998.

Furtado, J.C. and Lorena, L.A.N.Algoritmo Genético Construtivo na otimização de problemas combinatoriais de agrupamentos. XXX SBPO e III Oficina de cortes e empacotamento. Curitiba-Nov. 1998

Lorena, L. A N. and Narciso, M. G. Using local surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. Versão resumida apresentada na 1ª Oficina do projeto temático FAPESP - Planejamento e Controle da Produção em Sistemas de manufatura. UNICAMP - Abril, 1999.

Lorena, L. A N. and Narciso, M. G. Using local surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems. Aceito para apresentação no IFORS´99 - China - Agosto - 1999.

Yamamoto, M. , Lorena, L. A N. and Câmara. G. Tabu Search Application for Point Features Cartographic Label Placement Problem. Aceito para apresentação no MIC´99 - III Metaheuristics International Conference - a ser realizado em Angra dos Reis, July 19-22, 1999.

Uma Aplicação da busca tabu ao problema de rotulação cartográfica de pontos.

Aluna: Missae Yamamoto

Curso: Mestrado em Computação Aplicada no INPE

Data da apresentação: dez./1998

Orientadores: Dr. Luiz Antonio N. Lorena e Dr. Gilberto Câmara Neto

Implementação e Análise do Problema das p-medianas usando Algoritmo Genético Construtivo.

Aluna: Helena Kiyoka Kobayashi.

Iniciação Científica – CNPq/PIBIC .

UMC, Mogi das Cruzes, SP,

Março a dezembro 1998.