Projeto CNPq

Relatório de Projeto de Pesquisa

Referência:

Projeto:

Equipe:

Instituição:

Período:

Processo nº 461324/00-8 – Auxílio à Pesquisa

Localização-Alocação e Roteamento em Redes com Sistemas de Informações Geográficas - Sigla: LARSIG

Edson Luiz França Senne (Coordenador)

Luiz Antonio Nogueira Lorena

Universidade Estadual Paulista – UNESP

Campus de Guaratinguetá

Dezembro de 2000 a dezembro de 2001.

Sumário

O objetivo deste projeto foi desenvolver Sistemas de Apoio à Decisão para problemas de localização-alocação e roteamento em redes utilizando a plataforma computacional dos Sistemas de Informações Geográficas ArcView e MapObjects. Devido à experiência anterior da equipe, o desenvolvimento procurou dar ênfase a aplicações no ambiente urbano, levando em consideração a malha urbana, dados e mapas digitalizados de cidades do Vale do Paraíba já disponíveis. O propósito final é dotar decisores de ferramentas úteis na solução de problemas de localização-alocação de facilidades e problemas de roteamento. São problemas que justificam a atenção devido ao fato de aparecerem em diversas aplicações e serem considerados de difícil solução. Vários novos algoritmos vêm sendo desenvolvidos com sucesso pela equipe, com diversas aplicações nas áreas de aplicação pretendidas.

1. Resumo do Projeto Aprovado

1.1 - Introdução

Problemas de localização tratam de decisões sobre onde localizar facilidades, considerando clientes que devem ser servidos, de forma a otimizar um certo critério (Love et al., 1988; Mirchandani and Francis, 1990; Francis et al., 1992; Drezner, 1995). O termo “facilidades” pode se referir a fábricas, depósitos, escolas, etc., enquanto que "clientes" se referem a depósitos, unidades de vendas, estudantes, etc. Em geral os vários centros selecionados que podem ser localizados, podem também ser alocados ao subconjunto de centros que serão abertos. Por isso, devido ao processo de alocação dos outros centros aos centros abertos, tais problemas são conhecidos como problemas de localização-alocação.

Esta é uma área que têm despertado crescente interesse em planejadores, principalmente quando uma base de dados geograficamente referenciada pode ser usada. Dois principais grupos de pesquisa e divulgação: EURO Working Group on Locational Analysis (http://www.vub.ac.be/EWGLA/homepage.htm) e SOLA – INFORMS Section on Location Analysis (http://www.ualberta.ca/~sola), promovem reuniões anuais, na forma de congressos, onde são discutidos desenvolvimentos relacionados a problemas de localização.

As aplicações são, em geral, divididas para os setores público e privado. No caso de setores públicos, as aplicações maximizam a satisfação dos clientes em detrimento dos custos necessários para o alcance de tal objetivo (em geral os custos não são estimados com exatidão). Entre os exemplos de aplicações em setores públicos, estão: a localização de escolas, de postos de saúde, corpo de bombeiros, ambulâncias, viaturas de polícia, pontos de ônibus, entre outros. No caso do setor privado, custos fixos estão envolvidos e suas aplicações envolvem, em geral, fábricas, depósitos, torres de transmissão, lojas de franquias, etc.

Problemas de roteamento aparecem em uma série de serviços, como entrega bancária, entrega postal, entrega de mercadorias, rotas de ônibus escolar, coleta de lixo industrial, serviço de entrega noturna, operações de frete, dentre outros. A solução destes problemas pode diminuir bastante o custo de distribuição, causando uma grande economia tanto para a indústria como para o governo. No entanto, muitos destes problemas são difíceis de resolver. Estas características dos problemas de roteamento (relevantes e de difícil solução) fazem com que haja muita literatura a respeito (Christofides et al., 1979; Bodin et al., 1983; Gendreau et al., 1997).

O uso de SIGs - Sistemas de Informações Geográficas (Fischbeck, 1994) para resolver problemas de localização-alocação e roteamento ainda não está totalmente difundido na comunidade científica internacional. Mas, levando-se em conta a capacidade de armazenar, exibir e manipular dados espacialmente distribuídos, a integração de algoritmos de localização aos SIGs foi iniciada há alguns anos. A ESRI (Environmental Systems Research Institute) integrou alguns problemas não-capacitados de localização-alocação em seu Sistema de Informações Geográficas ARC/INFO. A integração baseou-se inicialmente na heurística de Teitz & Bart (1968) para solução do problema de p-medianas. Uma técnica proposta por Hillsman (1984) usa edição na formulação do problema de p-medianas e consegue, de forma aproximada, tratar outros tipos de problemas de localização-alocação usando a mesma heurística. No caso de problemas de roteamento, já existem também alguns algoritmos já integrados a SIGs, principalmente baseados no problema do caixeiro viajante (Reinelt, 1994).

1.2 - Objetivos do Projeto

Os principais objetivos previstos no projeto foram:

- Continuar a pesquisa e orientação sobre novos algoritmos de localização-alocação e roteamento, promovendo suas integrações aos SIGs ArcView e MapObjects já disponíveis;

- Construir protótipos de Sistemas de Apoio à Decisão usando modelos de localização e roteamento e dados geo-referenciados, com ênfase em aplicações na área urbana;

- Dar ênfase à realização de aplicações contando com dados já disponíveis e com outros dados que venham a ser adquiridos ou coletados pela equipe;

- Proporcionar ampla divulgação das metodologias, sistemas de informação, modelos e resultados obtidos no projeto, especialmente via Internet e com publicações, formação de alunos e participação em reuniões científicas.

1.3 - Atividades e Cronograma de Desenvolvimento

As seguintes atividades foram previstas no projeto:

(a) Levantamento bibliográfico.

(b) Pesquisa e orientação.

(d) Integração dos algoritmos aos SIGs visando a construção de Sistemas de Apoio à Decisão.

(e) Desenvolvimento de aplicações.

(f) Confecção de relatórios e divulgação de resultados.

O cronograma previsto do projeto foi o seguinte:

Bimestres

Atividade

1.4 – Referências Bibliográficas

Bodin, L.; Golden, B.; Assad, A.; Ball, M. Routing and scheduling of vehicles and crews: the state of the art. Computers and Operations Research, 10(2): 65-211, 1983.

Christofides, N.; Mingozzi, A.; Toth, P. The vehicle routing problem. In: Combinatorial Optimization, Christofides, N.; Mingozzi, A.; Toth P. and Sandi C. (eds.). John Wiley, 1979.

Drezner, Z. (ed.) Facility Location: A Survey of Applications and Methods, Springer-Verlag, NY, 1995.

Fischbeck P. GIS: More than a Map. OR/MS Today, 42-45, Aug. 1994.

Francis, R.L.; McGinnis, L.F.; White, J.A. Facility Layout and Location: An Analytical Approach, Prentice Hall, NJ, 1992.

Gengreau, M.; Laporte G.; Potvin, J.Y. Vehicle routing: modern heuristics. In: Local Search in Combinatorial Optimization. E. Aarts and J.K. Lenstra (eds.), p. 311-336. John Wiley, 1997.

Hillsman, E.L. The p-median structure as a unified linear model for location-allocation analysis. Environment and Planning A, 16: 305-318, 1984.

Love, R.F.; Morris, J.G.; Wesolowsky, G.O. Facilities Location: Models and Methods, North Holland, NY, 1988.

Mirchandani, P.B.; Francis, R.L. (eds.) Discrete Location Theory, Wiley Interscience, NY, 1990.

Reinelt, G. The Traveling Salesman, Springer-Verlag, Berlin, 1994.

Teitz, M.B.; Bart, P. Heuristic methods for estimating the vertex median of a weighted graph. Operations Research, 16: 955-961, 1968.

2. Principais Resultados Alcançados

A apresentação dos resultados alcançados no projeto está dividida nos seguintes itens:

- Atividades de pesquisa;

- Atividades de orientação;

- Integração de algoritmos de localização e roteamento a Sistemas de Informações Geográficas;

- Desenvolvimento de protótipos de Sistemas de Apoio à Decisão;

- Trabalhos científicos no período.

2.1 – Atividades de Pesquisa

Problemas de Localização-Alocação e Problemas Relacionados

q A relaxação lagrangeana/surrogate foi aplicada com sucesso aos seguintes problemas de localização de facilidades: p-medianas, p-medianas capacitado, p-medianas com restrição de distância máxima, localização de máxima cobertura e a um problema de localização com competiçã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.

q Foi desenvolvida uma nova abordagem para a solução de problemas de localização com o uso da relaxação lagrangeana/surrogate no processo de geração de colunas, visando estabilizar e acelerar o método tradicional de geração de colunas. Esta abordagem foi aplicada ao problema de p-medianas e ao problema de p-medianas capacitado.

q A utilização do algoritmo de localização-alocação alternada como heurística de mutação no processo evolutivo foi aplicada a um algoritmo genético construtivo (AGC) desenvolvido anteriormente, com resultados muito bons. Este algoritmo foi aplicado a problemas de p-medianas, problemas de p-medianas capacitado, e problemas de máxima cobertura.

q O problema de localização capacitado foi considerado como aplicação na localização de silos em cooperativas agrícolas, numa tentativa de identificar e propor soluções para problemas de redes no ambiente agrícola. O algoritmo genético construtivo com a utilização do algoritmo de localização-alocação foi aplicado ao problema, com resultados muito bons.

q Foi estudada, anteriormente, a aplicação do algoritmo genético construtivo ao problema da formação de células de manufatura em ambientes de produção, onde máquinas que processam tarefas são agrupadas em células com o objetivo de tornar a produção mais eficiente. Trata-se também de um problema clássico com grande aplicação prática. Na formulação do AGC foi utilizada a relação com o problema de p-medianas, como uma medida de distância apropriada.

Problemas de Roteamento de Veículos e Problemas Relacionados

q Iniciou-se o estudo visando a aplicação da relaxação lagrangeana/surrogatete aliada a métodos de otimização por subgradientes e ao processo de geração de colunas para o problema de roteamento de veículos com janelas de tempo. Problemas relacionados, como o de programação de horários para tripulações (crews) estão sendo pesquisados.

q 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. Iniciou-se a implementação de relaxação lagrangeana/surrogate no processo de geração de colunas, visando estabilizar a solução do modelo de particionamento. Está sendo pesquisado como resolver o problema de forma exata usando o método branch-and-price combinado com a relaxação lagrangeana/surrogate.

q Está sendo desenvolvida uma aplicação do algoritmo genético construtivo para o problema generalizado de atribuição. Os resultados obtidos até o momento são muito bons quando comparados a aplicação de algoritmos genéticos clássicos.

q Uma nova metodologia para avaliação do desempenho de sistemas de transporte foi desenvolvida, tendo recebido o Prêmio CNT Produção Acadêmica, conferido pela Confederação Nacional de Transporte. A implementação desta metodologia tem resultado em alguns sistemas de apoio à decisão, como os relacionados a seguir.

q Foram desenvolvidos algoritmos para aplicações em redes de linhas de transporte público visando a determinação do itinerário de linhas viáveis, o levantamento do conjunto de possíveis trajetos entre as diferentes regiões de uma cidade e para a determinação dos intervalos entre partidas de veículos, nos horários de pico e entre-picos. Estes algoritmos vêm sendo utilizados no desenvolvimento de sistemas de apoio à decisão para planejamento de transporte urbano de passageiros.

q Foram desenvolvidos algoritmos que, a partir de resultados de uma pesquisa origem-destino, determinam a distribuição de viagens entre as diferentes regiões de uma cidade (matrizes origem–destino). Para tanto, foram implementados métodos de expansão que, partindo de uma amostra coletada através da pesquisa origem-destino, expande seus resultados para o total da população no ano-base, e métodos de distribuição que permitem determinar as previsões de deslocamento entre as diferentes regiões da cidade, para um dado ano-meta a partir de dados do ano-base. Estes algoritmos também vêm sendo utilizados no desenvolvimento de sistemas de apoio à decisão para planejamento de transporte urbano de passageiros.

q Vem sendo estudado o problema de rotulação de pontos, importante para a confecção automática de mapas usando Sistemas de Informações Geográficas. Estuda-se a aplicação do algoritmo genético construtivo para a solução deste problema que, basicamente, objetiva escrever rótulos em pontos de um mapa (como nomes de cidades, por exemplo) de forma clara e evitando conflitos entre rótulos (que não podem se sobrepor). O problema vem sendo modelado e resolvido como um problema em grafos (encontrar um conjunto independente máximo). Também será proposta uma alternativa para a rotulação em tela visando aplicações para a Internet ou para consulta automática em veículos.

q O problema da coloração de grafos é um problema clássico de grande importância e que apresenta várias aplicações relacionadas às áreas do projeto (pois pode ser visto como um problema de clustering). Outro problema de clustering é o da programação de horários (timetabling). Abordagens de solução para tais problemas vêm sendo desenvolvidas com a aplicação do algoritmo genético construtivo.

2.2 – Atividades de Orientação

Concluídas no Período:

Geraldo Ribeiro Filho

Doutorado em Computação Aplicada no INPE.

Título da Tese: Melhoramentos no Algoritmo Genético Construtivo e Novas Aplicações em Problemas de Agrupamento.

Orientador: Luiz Antonio Nogueira Lorena

Data da defesa: dezembro de 2000.

Em Andamento:

Reinaldo Gen Ichiro Arakaki

Doutorado

Tema da tese: Algoritmo Genético Construtivo para Problemas de p-Medianas Capacitado e de Máxima Cobertura

Orientador: Luiz Antonio Nogueira Lorena

Data de início: março de 2000.

Bolsa: CAPES

Renan Kirihata

Iniciação Científica

Título do projeto: Sistema de Apoio à Decisão para Planejamento de Transporte Urbano de Passageiros

Orientador: Edson Luiz França Senne

Data de início: março de 2001

Bolsa: Fapesp

Mariana Quissak Bartelega Peixoto

Iniciação Científica

Título do projeto: Solução de Problemas de Localização e Roteamento em Redes com Sistema de Informações Geográficas

Orientador: Edson Luiz França Senne

Data de início: julho de 2001

Bolsa: Fapesp

Ana Paula Ribeiro Marimoto

Iniciação Científica

Título do projeto: Desenvolvimento de Sistemas de Apoio à Decisão para Problemas de Localização e Roteamento de Veículos

Orientador: Edson Luiz França Senne

Data de início: agosto de 2001

Bolsa: CNPq/PIBIC

2.3 - Integração de Algoritmos de Localização e Roteamento a Sistemas de Informações Geográficas

A aplicação do ArcView como banco de dados geográfico e ferramenta gráfica foi estendida para a fase de validação de algoritmos. O código-fonte da heurística lagrangeana/surogate para o problema de p-medianas foi utilizado como ponto de partida para o estudo dos outros modelos de localização implementados nesta fase do projeto. Foi necessário alterar o programa original para modelagem das características e particularidades dos outros modelos. Na fase de testes foram utilizados os dados disponíveis no ArcView para a cidade de São José dos Campos, SP, visando executar correções e melhorias no código, quando necessário. A partir de então, foram conduzidos estudos com dados disponíveis na literatura, permitindo comprovar a qualidade das soluções obtidas com o novo código. Algumas alterações foram executadas também nas scripts do ArcView, porém em menor escala. Tais alterações visam permitir ao usuário a entrada de alguns dos parâmetros específicos para cada modelo, por exemplo, a distância de atendimento para o problema de máxima cobertura.

Algoritmos para a solução dos seguintes problemas de localização foram integrados ao sistema de informações geográficas ArcView:

- Problema de p-medianas capacitado;

- Problema de p-medianas com restrição de distância máxima;

- Problema de localização de máxima cobertura;

- Problema de localização com competição.

A figura a seguir ilustra a solução heurística obtida para um problema de máxima cobertura, considerando 708 pontos, para instalação de três antenas de telecomunicações de curto alcance (800 m). Foram utilizadas as rotinas do ArcView para processar o arquivo contendo a solução de alocação do problema (linhas retas) e a área de cobertura (círculos) dos pontos escolhidos para instalação das antenas.

O algoritmo para o problema de p-medianas capacitado foi também integrado ao sistema de informações geográficas SPRING (versão 3.5), liberada em maio de 2001 durante a realização do GisBrasil em Curitiba. A figura a seguir ilustra um resultado da aplicação do algoritmo de p-medianas capacitado em uma região de São José dos Campos, SP, onde a partir de um conjunto de pontos com suas respectivas demandas de serviço armazenadas no banco de dados, foram identificadas as quatro melhores localizações. As demandas de cada ponto são obtidas selecionando-se na interface um atributo da tabela de objetos que corresponda às demandas em estudo.

Algoritmos de roteamento baseados no algoritmo de p-medianas capacitado também foram integrados a SIGs. No problema de roteamento, pode-se associar a cada um dos veículos um cluster formado pelo depósito e pelo subconjunto de clientes atendidos. A determinação de tais clusters foi realizada pelo algoritmo de p-medianas capacitado (cada mediana e seus clientes alocados correspondem a um cluster). O cálculo das rotas foi realizado utilizando uma rotina específica do módulo Network Analyst do sistema de informações geográficas ArcView. A figura a seguir ilustra esta solução para dados da cidade de São José dos Campos, SP. Neste exemplo, considerou-se que a mediana (em destaque) corresponde aos pontos de origem e de destino da rota.

2.4 – Desenvolvimento de Protótipos de Sistemas de Apoio à Decisão

Vêm sendo desenvolvidas algumas ferramentas de apoio ao processo de tomada de decisão envolvendo problemas de localização de facilidades e roteamento de veículos em redes, com ênfase em aplicações para o ambiente urbano.

Uma das aplicações desenvolvidas neste período do projeto refere-se a um sistema de apoio à decisão para a análise e o planejamento de redes urbanas de transporte de passageiros. As figuras a seguir ilustram a interface principal deste sistema e uma possível saída do sistema com informações sobre o desempenho da rede de linhas de transporte, para uma aplicação desenvolvida para a cidade de Guaratinguetá, SP.

Outra aplicação refere-se a um protótipo de Sistema de Apoio à Decisão acerca das linhas de ônibus e dos pontos de parada existentes na cidade de Guaratinguetá, SP. Para tanto a cidade foi dividida em zonas de interesse de tráfego conforme mostra a figura abaixo.

A figura a seguir apresenta uma saída do sistema, possibilitando uma análise do sistema de transporte público da cidade de Guaratinguetá, SP. Na figura, os pontos de parada são representados por pequenos círculos e pode-se observar um maior destaque nas vias à medida que aumenta a oferta de linhas.

Outra aplicação refere-se a um protótipo de Sistema de Apoio à Decisão para problemas de localização e roteamento utilizando o SIG TransCAD. As figuras a seguir ilustram algumas soluções obtidas pelo sistema.

Localização-Alocação

Roteamento

Vem sendo desenvolvido também, com base no ambiente de desenvolvimento C++ Builder e na biblioteca de classes MabObjects, um sistema de apoio à decisão específico para problemas de localização de facilidades e roteamento de veículos, utilizando algoritmos já desenvolvidos para essas duas classes de problemas.

2.5 – Trabalhos Científicos no Período

Trabalhos publicados:

Senne, E.L.F.; Lorena, L.A.N.

Lagrangean/surrogate heuristics for p-median problems. In: Computing Tools for Modeling, Optimization and Simulation: Interfaces in Computer Science and Operations Research, M. Laguna and J. L. Gonzalez-Velarde (eds.), Kluwer Academic Publishers, p. 115-130, 2000

Ribeiro Filho, G.; Lorena, L.A.N.

A Constructive Evolutionary Approach to the Machine-Part Cell Formation Problem. In: Buildings Competencies for International Manufacturing - Perpectives for developing countries, A. Fleury, H. Yoshizaki, L. B. M. Guimaraes and J. L. D. Ribeiro (eds.), UFRGS/FEENG, Porto Alegre, p. 340-348, 2000

Batista Junior, E.D.; Senne, E.L.F.

TRANSIS: Um Novo Método para Avaliar o Desempenho de Sistemas de Transporte Urbano de Passageiros. In: Panorama Nacional da Pesquisa em Transportes 2000, Setti, J.R.A.; Cybis, H.B.B. (eds.), ANPET, ISBN 85-97893-02-5, p. 179-189, 2000

Ribeiro Filho, G.; Lorena, L.A.N.

A Constructive Evolutionary Approach to School Timetabling. In: Applications of Evolutionary Computing, Boers, E.J.W., Gottlieb, J., Lanzi, P.L., Smith, R.E., Cagnoni, S., Hart, E., Raidl, G.R., Tijink, H., (eds.), Springer Lecture Notes in Computer Science, 2037 : 130-139, 2001

Lorena, L.A.N.; Senne, E.L.F.; Paiva, J.A.C.; Pereira M.A.

Integração de modelos de localização a sistemas de informações geográficas. In: Gestão e Produção, 8 (2) : 188-195, agosto de 2001.

Lorena, L.A.N.; Furtado, J.C.

Constructive genetic algorithm for clustering problems. In: Evolutionary Computation, 9 (3): 309-328, 2001

Lorena, L.A.N.

Analise de redes. In: Câmara, G.; Monteiro, A.M.; Fuks, S.; Camargo, E.; Felgueiras,C. Análise Espacial de Dados Geográficos. São José dos Campos, INPE, 2001 (2ª edição, revista e ampliada).

Trabalhos aceitos para publicação:

Yamamoto, M.; Camara, G.; Lorena, L.A.N.

Tabu search heuristic for point-feature cartographic label placement.

GeoInformatica - An International Journal on Advances of Computer Science for Geographic Information Systems

Lorena, L.A.N.; Narciso, M.G.

Using logical surrogate information in Lagrangean relaxation: an application to symmetric traveling salesman problems.

European Journal of Operational Research

Lorena, L.A.N.; Pereira M.A.

A Lagrangean/surrogate heuristic for the maximal covering location problem using Hillsman's edition.

International Journal of Industrial Engineering - Special Issue on Facility Location and Layout

Oliveira A.C.M.; Lorena, L.A.N.

A Constructive Genetic Algorithm for the Linear Gate Assignment Problem.

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Trabalhos submetidos para publicação:

Lorena, L.A.N.; Narciso, M.G.; Beasley J.E.

A constructive genetic algorithm for the generalized assignment problem.

Evolutionary Optimization

Lorena, L.A.N.; Senne, E.L.F.

Local search heuristics for capacitated p-median problems

Networks and Spatial Economics

Senne. E.L.F.; Lorena, L.A.N.

Stabilizing column generation using Lagrangean/surrogate relaxation: an application to p-median location problems.

European Journal of Operational Research

Lorena, L.A.N.; Pereira. M.A.; Salomão S.N.A.

A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas

Pesquisa Operacional

Trabalhos apresentados em congressos:

Ribeiro Filho, G.; Lorena, L.A.N.

A Constructive Evolutionary Approach to School Timetabling

EvoCOP2001 – First European Workshop on Evolutionary Computation in Combinatorial Optimization, Lake Como (Milan), april 18-19, 2001

Ribeiro Filho, G.; Lorena, L.A.N.

DNA Fragment Assembly using the Constructive Genetic Algorithm.

INFORMS Annual Meeting 2001 Miami Beach - November 4, 2001 - November 7, 2001

Oliveira A.C.M.; Lorena, L.A.N.

A Constructive Genetic Algorithm for the Linear Gate Assignment Problem.

GECCO – Genetic and Evolutionary Computation COnference – 2001, San Francisco, july 7-11, 2001.

Arakaki, R.G.I.; Lorena, L.A.N.

A Constructive Genetic Algorithm for the Maximal Covering Location Problem

MIC 2001 – 4th Metaheuristics International Conference, Porto, Portugal, july 16-20, 2001.

Senne, E.L.F.; Lorena, L.A.N.

Stabilizing Column Generation Using Lagrangean/Surrogate Relaxation: An Application to p-Median Location Problems.

EURO 2001 – The European Operational Research Conference, Rotterdam, The Netherlands, july 2001. Abstracts, p. 116.

Narciso, M.G.; Lorena, L.A.N.

Uma aplicação da relaxação lagrangeana/surrogate ao problema simétrico do caixeiro viajante usando um método de subgradientes melhorado

XXIII SBPO - Simpósio Brasileiro de Pesquisa Operacional, Campos do Jordão, nov. 2001.

Pereira M.A.; Lorena, L.A.N.

A heurística lagrangeana/surrogate aplicada ao problema de localização de máxima cobertura

XXIII SBPO - Simpósio Brasileiro de Pesquisa Operacional, Campos do Jordão, nov. 2001.

Oliveira A.C.M.; Lorena, L.A.N.

A Constructive Evolutionary Approach to Linear Gate Assignment Problems.

ENIA 2001 – Encontro Nacional de Inteligência Artificial, Fortaleza, julho, 30 – agosto, 03, 2001.

Lorena, L.A.N.; Pereira, M.A.; Salomão, S.N.A.

A relaxação Lagrangeana/surrogate e o método de geração de colunas: novos limitantes e novas colunas

V Oficina Nacional de Problemas de corte e empacotamento, 06 e 07 de dezembro de 2001, INPE, S. J. Campos, SP.

Kirihata, R.; Senne, E.L.F.

Uma Ferramenta para o Planejamento de Transporte Urbano de Passageiros usando Sistema de Informações Geográficas.

In: 4ª Jornada de Iniciação Científica e Pós-Graduação, Unesp, Guaratinguetá, SP, setembro, 2001. Anais em CD-ROM (5 páginas).

Batista Junior, E.D.; Senne, E.L.F.; Teixeira, A.P.

SIGPOP: Gerenciamento de Pontos de Parada com a Utilização de Sistema de Informação Geográfica

XI Congresso Latinoamericano de Transporte Publico Urbano, Cuba, setembro 17-21, 2001.

Senne, E.L.F.

Uma Abordagem de Geração de Colunas para Solução de Problemas de p-Medianas.

In: 17º Seminário de Matemática Aplicada e Computacional. Guaratinguetá, SP, Unesp, setembro, 2001. Resumos, p. 6.

Batista Junior, E.D.; Senne, E.L.F.; Teixeira, A.P.

A Importância de um Sistema de Informação para o Gerenciamento do Transporte de Passageiros.

In: 21º Encontro Nacional de Engenharia de Produção, Salvador, BA, outubro, 2001. Anais em CD-ROM (7 páginas).

Senne, E.L.F.; Batista Junior, E.D.; Kirihata, R.

Transig: Sistema de Apoio à Decisão para Planejamento de Transporte Urbano.

In: 21º Encontro Nacional de Engenharia de Produção, Salvador, BA, outubro, 2001. Anais em CD-ROM (8 páginas).

Kirihata, R.; Senne, E.L.F.

TranSIG: Sistema de Apoio à Decisão para Planejamento de Transporte Urbano.

In: 13º Congresso de Iniciação Científica da Unesp, Bauru, SP, outubro, 2001. Resumos, p. 59.

Relatório técnico:

Batista Junior, E.D.; Senne, E.L.F.; Missao, C.K.; Segismundo, A.; Kirihata, R.

Sistema TranSis. Relatório Técnico 05/00, DPD/FEG/UNESP, Guaratinguetá, SP, dezembro, 2001.

3. Conclusões e Comentários

Apresentam-se a seguir algumas conclusões e comentários sobre as atividades desenvolvidas no período.

O segmento de pesquisa e orientação de alunos contou com grande atividade neste período. Todas as áreas importantes para o projeto foram contempladas. Algumas outras áreas relacionadas foram também consideradas. Os problemas de localização já contam com diversas contribuições dos participantes do projeto. A técnica de solução que combina a relaxação lagrangeana/surrogate e geração de colunas vem se mostrando bastante promissora, e pode-se esperar várias outras contribuições de métodos eficientes para solução dos problemas de localização e roteamento. O desenvolvimento do algoritmo genético construtivo continua sendo realizado com a participação de vários pesquisadores e, como conseqüência, vem se firmando como uma meta-heurística competitiva para problemas de otimização combinatória. A área de transportes conta com a participação efetiva de estudantes de Iniciação Científica e vários sistemas de apoio à decisão estão sendo elaborados.

As integrações de problemas de localização proporcionaram a formação de amostras de dados de diversos tamanhos que foram extraídos como pontos com coordenadas no sistema de informações geográficas ArcView, usando mapa digitalizado de São José dos Campos, SP. Esses dados formaram um conjunto de instâncias que foram utilizados para comparação dos algoritmos integrados ao ArcView, ao SPRING e sem a integração a um SIG. Essas instâncias estão disponíveis para futuras comparações com outros algoritmos que venham a ser integrados aos SIGs.

Em resumo, as seguintes aplicações foram examinadas no projeto:

Localização

- Problema de p-medianas,

- Problema de p-medianas considerando distâncias de rede,

- Problema de p-medianas capacitado,

- Problema de p-medianas com restrição de distância máxima,

- Problema de localização de máxima cobertura,

- Problema de localização com competição.

Roteamento

- Roteamento de veículos com janelas de tempo,

- Programação de horários para tripulações (crews),

- Problema Generalizado de Atribuição,

- Problema simétrico do Caixeiro Viajante.

Transportes

- Metodologia para avaliação do desempenho de sistemas de transporte,

- Dimensionamento de rede de linhas de transporte urbano de passageiros,

- Gerenciamento de pontos de parada.

Problemas relacionados

- Problema de rotulação de pontos,

- Coloração de grafos,

- Programação de horários (timetabling),

- Problema da formação de células de manufatura,

Integrações ao ArcView

- Problema das p-medianas,

- Problema das p-medianas considerando distâncias de rede,

- Problema de p-medianas capacitado,

- Problema de p-medianas com restrição de distância máxima,

- Problema de localização de máxima cobertura e

- Problema de localização com competição.

Integrações ao SPRING

- Problema das p-medianas,

- Problema das p-medianas considerando distâncias de rede, e

- Problema de p-medianas capacitado.

Sistemas de Apoio à Decisão

- Ferramenta para análise e planejamento de redes de linhas de transporte urbano,

- Sistema de informação para o gerenciamento de pontos de parada de redes de linhas de transporte urbano,

- Ferramentas para o processo de tomada de decisão envolvendo problemas de localização de facilidades e roteamento de veículos em redes, com ênfase em aplicações para o ambiente urbano.

O projeto LARSIG apresenta no período um balanço muito positivo. Apresenta-se abaixo uma tabela com um resumo da produção em pesquisa e orientação obtida neste período do projeto.

Projeto LARSIG – Resumo de Atividades	Qtd.
Publicações em revistas e/ou capítulo de livros internacionais	4
Publicações em revistas e/ou capítulo de livros nacionais	3
Artigos aceitos para publicação em revista internacional	4
Teses de doutorado defendidas	1
Teses de doutorado em andamento	1
Trabalhos de iniciação científica em andamento	3
Trabalhos apresentados em congressos	15
Trabalhos submetidos para revistas	4
Relatórios técnicos	1
Total	36

Todas essas informações estão disponibilizadas via Internet, na página do projeto: http://www.feg.unesp.br/~elfsenne/projetos/larsig/rfinal.htm, visando uma ampla divulgação dos resultados obtidos.

Integrações ao SPRING

Projeto LARSIG – Resumo de Atividades