ARSIG para o Domínio Agropecuário

Autores

Luiz Antônio Nogueira Lorena
e-mail: lorena@lac.inpe.br
Vínculo: Instituto nacional de Pesquisas Espaciais
Endereço:
Telefone: (0xx12) 345-6553

Marcelo G. Narciso
e-mail: narciso@cnptia.embrapa.br
Vínculo: Embrapa Informática Agropecuária
Endereço:
Telefone: (0xx19) 289-9800 r 162

Resumo

O ARSIG (Análise de Redes com Sistema de Informação Geográfica) é um projeto lançado pelo INPE (ver http://www.lac.inpe.br/~lorena/ArsigIndex.html) e tem como parceiros a FEG/Unesp e, atualmente, a Embrapa Informática Agropecuária. Este projeto tem 2 anos e ainda está em andamento (faltam mais 3 anos). O ARSIG visa a disponibilizar ao usuário um sistema de apoio a decisão (SAD), o qual o usuário acessará pela Internet. Este SAD fornecerá soluções para problemas de localização e roteamento, nos domínios urbano e rural. O Projeto ainda não está pronto, mas já se tem alguns produtos disponibilizados na Internet, isto é, uma primeira versão de programas executáveis de algoritmos eficientes para problemas de localização e roteamento. Além destes algoritmos, existem programas (scripts) de integração dos executáveis (programas para resolver problemas de localização e roteamento) com o SIG ArcView. Na Segunda etapa do projeto (ano 2000 a 2002), os algoritmos de localização e roteamento serão melhorados e outros tipos de problemas deverão ser inseridos. O SAD será composto pelos executáveis dos algoritmos (localização, roteamento e outros), SIG (ArcView e Spring), um banco de dados sobre mapas do Estado de São Paulo (a ser implementado pela Embrapa Informática Agropecuária) e o CGI, também desenvolvido pela Informática Agropecuária, para integrar o sistema (algoritmos/banco de dados sobre mapas/SIG) na Internet. Ao término desta etapa, o sistema estará acessível ao usuário na Internet (agricultores, pecuaristas, empresários, prefeituras, etc.) para que o mesmo tenha um sistema de apoio a decisão de qualidade.

Abstract

The ARSIG (Network Analisys with Geographic Information System) is a project created by INPE (see http://www.lac.inpe.br/~lorena/ArsigIndex.html) and it has as partners FEG/Unesp and, nowadays, Embrapa Informática Agropecuária. This Project has two years of existence and it is still in progress (there are 3 years left to finish it) .

The ARSIG aims to deliver to the Internet user a Decision Support System (DSS). This DSS will provide solutions to the localization and routing problems in the urban and rural domains. The project is still not concluded, but there are some products available in the Internet, such as a first version of executable programs of efficient algorithms for location and routing problems. Besides of this algorithms, there are programs (scripts) of integration to executable programs (programs to solve problems of localization and routing) with ArcView GIS.

In second stage of project (years 2000 and 2001), the algorithms of localization and routing will be improved and others kinds of problems will be added in the ARSIG project. The DSS will be composed of algorithms (localization, routing and others), GIS (ArcView and Spring), data base about maps of São Paulo State (to be implemented by Embrapa Informática Agropecuária) and the CGI, also developed by Embrapa Informática Agropecuária, to integrate the system (algorithms/data base about maps/GIS) to the Internet. At the end of this stage, the system will be acessible to the Internet user (agriculturist, person skilled in cattle raising, entrepreneur, prefectures, and so on) so the person can make use of a qualified DSS.

Palavras Chaves

Algoritmos de roteamento e localização, SIG, Banco de dados, Internet, sistema de apoio a decisão.

1. INTRODUÇÃO

O ARSIG é um sistema de apoio a decisão (SAD) para o usuário. Este SAD é composto por algoritmos de localização (Senne e Lorena, 1997) e roteamento (Lorena e Furtado. 1998, Senne e Lorena, 1998), SIG, banco de dados, e ferramentas para acesso do usuário, na Internet, ao sistema (banco de dados, SIG, algoritmos). O SAD em questão irá fornecer dados, relatórios, mapas, e outros que darão condições ao usuário de decidir a maneira como ele poderá organizar uma rede de distribuição de produtos agrícolas (ou gado, produtos agroflorestais, etc.), onde estabelecer armazéns para distribuição de produtos agrícolas, como os produtos poderão ser entregues em um tempo mínimo a diversas localidades, etc. Os problemas a serem enfocados pelo ARSIG, em princípio, são conhecidos como problemas de localização e roteamento (além destes, outros tipos de problemas poderão ser inseridos). São problemas que justificam a atenção devido ao fato de aparecerem em diversas aplicações, tanto na zona urbana quanto na zona rural, e serem considerados de difícil solução. O objetivo principal da pesquisa está no desenvolvimento de novos algoritmos e na adaptação de algoritmos clássicos considerados eficientes para as áreas de localização e roteamento, a princípio, podendo se estender a outros tipos de problemas, no decorrer do tempo. 

Um Sistemas de Informação Geográfica (SIG) será integrado com os algoritmos para a visualização do resultado e também para coleta de dados para os algoritmos. Uma parte do sistema (SIG-algoritmos) será disponibilizado à comunidade agrícola, prefeituras (para localização de escolas, hospitais, distribuição de alimentos, etc.), indústrias, etc. pela Internet. Esta parte do sistema é os algoritmos (programas executáveis) e os scripts de integração dos algoritmos com o SIG (Arc View e Spring).

Além do sistema SIG-algoritmos, será disponibilizado também um banco de dados (BD) de mapas de algumas regiões rurais de São Paulo. Estes dados (mapas) serão fornecidos pelo INPE (Instituto Nacional de Pesquisas Espaciais), ANEEL (Agência Nacional de Energia Elétrica), CPRM (Cia de Pesquisas e Recursos Minerais, http://www.cprm.gov.br ) e IBGE. Outras instituições, no decorrer do projeto, poderão fornecer mais mapas. O BD será integrado ao SIG-algoritmos e este novo sistema, em conjunto com a ferramenta Utilis (ver http://www.cnptia.embrapa.br/produtos.html ), formarão um sistema de apoio a decisão (SAD), o qual será acessado pelos usuários via Internet. O SIG irá acessar mapas do BD e os algoritmos irão resolver problemas de localização/roteamento referentes a estes mapas. Desta forma, o usuário poderá fazer simulações usando o SAD disponibilizado na Internet. Caso o BD não tenha o mapa que o usuário deseja (usuário de outro estado ou de outro país, por exemplo, ou ainda, uma região de São Paulo cujo mapa não esteja disponível), haverá a opção do usuário (de São Paulo, outro estado ou outro país) acessar aos softwares componentes do SAD (programas executáveis dos algoritmos e scripts de integração dos executáveis dos algoritmos com o SIG) e com isto, ele poderá acessar o mapa que quiser através de uma outra instituição e usar os programas (executáveis e scripts) em associação com o SIG e um BD que ele tenha. A integração ficaria por conta do usuário. Entretanto, ele teria também uma documentação de como fazer esta integração. O documento também estaria no site deste SAD. Vale a pena mencionar que este SAD pode ser estendido para outras regiões do Brasil, podendo cada unidade da Embrapa (nos demais estados) ter o seu específico para a sua região.

A Embrapa Informática Agropecuária irá enfocar o domínio agropecuário (e indústria ligada a agropecuária) do projeto e o INPE (Instituto Nacional de Pesquisas Espaciais) e a FEG/Unesp (Faculdade de Engenharia da Unesp, Campus de Guaratinguetá), o domínio urbano e indústrias.

2. JUSTIFICATIVA E APLICAÇÕES PRÁTICAS

Os problemas de localização e roteamento podem ser tratados como modelos em redes. Estes problemas ocorrem, tipicamente, em um espaço discreto, ou seja, em um espaço em que o número de locais possíveis e o número de caminhos entre os locais são finitos. Em outras palavras, muitos problemas práticos de localização e de roteamento estão intimamente relacionados ao uso de uma rede de transporte como um espaço no qual os "serviços" operam. Nestas redes, os nós correspondem às interseções das vias de transporte e os arcos, representados por segmentos de reta, correspondem os diversos caminhos que compõem tais vias.

Até o momento não se conhecem abordagens eficientes, em tempo de processamento e/ou memória, de solução geral para os problemas de localização e roteamento (Papadimitriou and Steiglitz, 1982, Lorena e Senne, 1996). Tais problemas ocorrem em várias áreas, em sistemas produtivos em geral e, em particular, na análise de redes usando Sistemas de Informações Geográficas.

Vale a pena mencionar que o número de variáveis envolvidas nos problemas de roteamento e localização pode ser muito grande, o que dificulta sobremaneira a obtenção da solução ótima. Desta forma, não é qualquer algoritmo que pode dar uma solução rápida e de qualidade para ser inserida no SIG. Isto é um motivo de pesquisa, visto que importa o tempo de resposta e a qualidade da solução. Neste projeto, esta pesquisa está sendo feita (1997 a 1999). Foram feitos testes com relaxações (lagrangeana e surrogate), para fornecer limites inferiores (ou superiores) a solução ótima e também foram feitos testes com algoritmos genéticos.

Os algoritmos genéticos construtivos (ver Lorena e Furtado, 1998 ) foram testados com sucesso em algumas aplicações, incluindo os problemas de roteamento e localização. Entretanto, os resultados podem ser melhorados. Para isto, novas pesquisas para melhorar o desempenho deste algoritmo serão feitas (2000 a 2002). Além disso, com os trabalhos sobre a relaxação lagrangeana/surrogate, feitos por (Lorena e Narciso, 1999) e (Senne e Lorena, 1997), cujos resultados obtidos foram de ótima qualidade, tem-se outras alternativas para se determinar limites para a solução ótima. Estes limites podem ser aproveitados em algoritmos que implementam métodos exatos (fornecem a melhor solução) para serem executados em menor tempo possível.

Sistemas de Informações Geográficas (SIGs) integram Computação Gráfica a uma base de dados. São poderosas ferramentas de análise e planejamento espacial. O comércio de SIGs representa um dos segmentos que mais crescem nos Estados Unidos, tornando-se crítica a integração de técnicas de Pesquisa Operacional nesta tecnologia (Fischbeck, 1994). Nos SIGs, os problemas de Otimização Combinatória aparecem combinados à análise de redes de fluxo (estradas, ruas, canais de comunicação, dentre outros), com os algoritmos clássicos de otimização de fluxo em redes diretamente aplicáveis. Problemas mais complexos de localização de centros (silos/armazéns, usinas (sucos, açúcar, etc.), indústrias de beneficiamento de produtos agrícolas, escolas (inclusive na zona rural), ambulatórios, terminais de passageiros ou de cargas, garagens de operadoras de transporte coletivo e outras facilidades relacionadas com o transporte de passageiros ou de cargas) e roteamento de veículos podem também ser tratados com SIGs, levando-se em conta várias informações espaciais.

3. EXEMPLO DE APLICAÇÃO DO ARSIG

3.1 Modelo de localização

Localização é o processo de se determinar a melhor, ou ótima localização para uma ou mais facilidades (fábricas, depósitos, armazéns ou outras instalações) ou centros ofertantes, de modo que os serviços ou benfeitorias sejam acessíveis à população, representada por pontos de demanda, da maneira mais eficiente. Os modelos otimizam eficiência, determinando simultaneamente a configuração das facilidades. O modelo utilizado foi o de distâncias mínimas ou problema das p-medianas (Lorena e Senne, 1996), onde o objetivo foi minimizar a distância total percorrida entre cada ponto de demanda e seu centro ofertante mais próximo.

3.2 - Exemplo do sistema algoritmo de localização/ArcView.

Nesta aplicação foram utilizados dados do centro da cidade de São José dos Campos-SP. Os pontos em forma de bolinhas são os pontos de demanda. Este exemplo pode ser visto em ver http://www.lac.inpe.br/~lorena/ArsigIndex.html e foi feito pela equipe do projeto.

Inicialmente o script solicita ao usuário que digite o número de medianas desejado, neste caso, 3 medianas. Na figura abaixo as medianas estão representadas por pontos (círculos) e podem por exemplo ser associadas a centros ofertantes de um determinado tipo de serviço. As linhas que saem das medianas (círculos) representam a ligação entre os pontos de demanda e seus centros ofertantes correspondentes.

Figura 1 - Solução do processamento com 3 medianas (pontos de localização)

4. CONCLUSÕES

O ARSIG é um projeto que visa a produzir um SAD para o usuário na Internet. Este SAD será uma importante ferramenta de decisão para problemas que envolvam localização e roteamento. Futuramente, outros tipos de problemas serão adicionados ao SAD.

Atualmente, tem-se algoritmos de localização e roteamento (executáveis) disponíveis na Internet para serem usados em conjunto com o ArcView. Além disso, os scripts que integram os algoritmos com o ArcView estão também disponíveis. Futuramente, todo o SAD estará disponível.

Com este SAD, será possível ao usuário a otimização de custos e maior ganho (lucro) com a utilização do software em determinados pontos da cadeia produtiva agrícola ou pecuária ou ainda, na indústria. Além disso, este SAD devera ser útil na definição e solução de problemas de logística, distribuição e localização para itens relacionados a insumos e produtos agrícolas.

Com o presente projeto (ARSIG), pretende-se dar uma efetiva contribuição no tratamento de questões relacionadas com o transporte e localização, quer no desenvolvimento de algoritmos para roteamento de veículos e localização de facilidades, quer na viabilização de aplicações utilizando Sistemas de Informações Geográficas e banco de dados (mapas) com a posterior disponibilização deste sistema na Internet.

5. REFERÊNCIAS BIBLIOGRÁFICAS