Reportagens






 

Problemas de localização e transportes integrados
a sistemas de informações geográficas

Luiz Antonio Nogueira Lorena

Muitos problemas do cotidiano envolvem a decisão sobre locais para instalação de serviços e de meios de transportes. Por exemplo, qual a melhor localização para a instalação de postos de serviços, hospitais, fábricas, centros de distribuição de mercadorias, armazéns, antenas de telefonia celular, etc? A localização de serviços é seguida de problemas relativos a transportes visando seu melhor uso, tais como os de coleta de lixo, recolhimento de produtos, distribuição de mercadorias, dentre muitos outros. Para ilustrar, um problema cotidiano que envolve um número cada vez maior de pessoas é a dificuldade de acesso a diferentes pontos de interesse (trabalho, residência, serviços, lazer), especialmente em cidades de médio e grande porte. A respeito do transporte de cargas as dificuldades são semelhantes.

Esses problemas possuem as seguintes características comuns:
- Ocorrem, tipicamente, em contexto em que o número de locais possíveis e o número de caminhos entre os locais são finitos, mas o número de opções é geralmente muito grande tornando-os de difícil solução.
- Os dados estão espacialmente distribuídos e poderiam ser integrados a sistemas computacionais que guardem informações de entidades espaciais.
- Os dados espacialmente distribuídos apresentam várias aplicações quando podem ser identificadas redes para apoio e definição de problemas. As redes são entidades formadas por pontos (nós ou vértices) e linhas (arcos ou arestas) que descrevem de maneira natural vias públicas, conexões de água, telefonia e outros. As redes para modelos urbanos descrevem em geral ruas, avenidas e suas interseções (cruzamentos).

Os Sistemas de Informações Geográficas (SIGs) são ferramentas adequadas e modernas para modelagem e tratamento de problemas com distribuição espacial de dados. Os SIGs integram computação gráfica a uma base de dados. A vantagem em usar um SIG está na habilidade de associar a cada arco e nó da rede um conjunto de atributos que de outra maneira não estaria disponível para a análise. Além disso, alguns algoritmos bem conhecidos, como por exemplo, para minimizar a distância e o tempo percorridos em uma rota, estão imediatamente disponíveis. Outra vantagem está na utilização de informações de um censo demográfico que associe características econômicas e de população para áreas nas redondezas de cada nó ou arco da rede. Em outras palavras, muitos problemas práticos de localização de facilidades e de transportes estão intimamente relacionados ao uso de uma rede viária como um espaço no qual os "serviços" operam.

Entretanto, o uso de SIGs para ajudar na definição e solução de problemas de localização e transportes ainda não está totalmente difundido na comunidade científica internacional, mesmo considerando que os fabricantes comerciais já integram ferramentas para resolução de alguns desses problemas em seus SIGs.

Recentemente os projetos ARSIG - Análise de Redes com Sistemas de Informações Geográficas e ARSIG2 - Sistemas de Apoio à Decisão Usando Redes e Sistemas de Informações Geográficas, foram desenvolvidos como temáticos, apoiados pela Fapesp, com a coordenação do LAC/Inpe, em colaboração com a Unesp/FEG e o CNPTIA/Embrapa. Nesses projetos alguns dos principais algoritmos de localização, propostos pelos pesquisadores participantes dos projetos, foram integrados a SIGs comerciais e ao SPRING, desenvolvido pelo Inpe. Toda a informação produzida, incluindo os algoritmos, dados coletados e publicações em revistas especializadas, estão disponíveis na página dos projetos: http://www.lac.inpe.br/~lorena/ArsigIndex.html.

A seguir serão descritas através de exemplos algumas aplicações de localização e distribuição que apresentam software disponível para o público interessado.

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. O termo "facilidades" pode ser substituído por fábricas, depósitos, escolas etc., enquanto 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. Desta forma também são conhecidos como problemas de localização-alocação, devido ao processo de alocação dos outros centros aos centros abertos.

As aplicações são em geral divididas para setores públicos e privados. No caso de setores públicos 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, postos de saúde, corpo de bombeiros, ambulâncias, viaturas de polícia, pontos de ônibus, entre outros. No caso do setor privado, custos chamados fixos estão envolvidos, e suas aplicações envolvem em geral fábricas, depósitos, torres de transmissão, lojas de franquias, entre outros.

Um exemplo inicial será usado para melhor explicar os conceitos e problemas envolvidos. Suponha que uma prefeitura deseja localizar ambulâncias para o atendimento emergencial de pessoas acidentadas, levando-se em conta um tempo máximo de atendimento. Os seguintes dados devem ser levantados: as posições candidatas para localização das estações, as demandas de cada posição, e o tempo de resposta entre estações de ambulâncias e os possíveis locais de atendimento.

A figura 1 mostra uma possível solução ao problema, onde estão sendo considerados os dados georeferenciados da região central de São José dos Campos. Um tema de pontos foi extraído, um ponto por quadra, com as respectivas demandas, calculadas com base no cadastro de imóveis existente nas quadras. A demanda será maior, conforme aumenta o número de imóveis nas quadras. Quadras vazias receberam a demanda unitária. A solução apresenta a localização de 3 ambulâncias considerando um raio de cobertura linear, embora, neste caso as distâncias (entre pontos e a crítica) deveriam levar em conta o deslocamento sobre um tema de linhas e pontos (rede).



Figura 1: Solução para três ambulâncias

A mesma situação poderia se referir à localização de antenas transmissoras para distribuição de serviço de internet via rádio, com raio de ação de 800 metros (o alcance das antenas não leva em conta as cotas dos terrenos e os obstáculos que estariam no raio de ação)

As figuras 2 e 3 mostram as soluções de um problema contendo 31 vértices, dos quais foram selecionados três para a instalação de unidades básicas de saúde. Além das distâncias foram admitidas capacidades de atendimento aos postos no intuito de evitar filas. No primeiro caso consideraram-se distâncias lineares e no segundo foram utilizadas distâncias calculadas sobre a rede que representa um subconjunto das ruas que compõem o centro da cidade de São José dos Campos. Pode-se observar que existem diferenças entre as soluções dos dois estudos.


Figura 2: Localização de três unidades - distâncias euclidianas


Figura 3: Localização de três unidades - distâncias de rede

Problemas de distribuição 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 entregas noturnas, operações de frete, e outros. A solução desses problemas pode diminuir bastante o custo de distribuição, sendo de uma grande economia tanto para a indústria como para o governo. No entanto, muitos desses problemas são difíceis de resolver. Esses dois atrativos fazem com que existam muitos trabalhos disponíveis na literatura sobre esses problemas que são conhecidos como problemas de roteamento e programação (scheduling).

Como exemplo pode-se examinar uma possibilidade freqüentemente explorada nas aplicações, estabelecendo grupos de clientes que satisfaçam as restrições de capacidades dos veículos, e então sequenciar de forma ótima o roteiro de entregas dos caminhões dentro dos grupos. Veja a figura 4 para uma solução de rotas para três caminhões, onde foram aproveitados os grupos formados no problema de localização representado na figura 3. Pode-se interpretar que o depósito de onde partem os caminhões está situado fora dos grupos e os caminhões devem percorrer um trajeto inicial para entrar nas rotas dentro dos grupos de clientes.


Figura 4: Rotas para três caminhões (considerando capacidades)

Vários outros exemplos podem ser apresentados justificando a utilidade dessas ferramentas na solução de problemas do cotidiano. O leitor interessado poderá obter maiores informações na página dos projetos ARSIG, onde várias outras referências bibliográficas relevantes são apresentadas.

Com o presente artigo procurou-se mostrar alguns aspectos de problemas cotidianos que podem ser resolvidos com o auxílio de ferramentas computacionais e análise espacial de dados. Os projetos ARSIG iniciaram uma efetiva contribuição no tratamento de questões como essas, relacionadas com o transporte, 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.


Luiz Antonio Nogueira Lorena é pesquisador do Laboratório Associado de Computação e Matemática Aplicada do Instituto Nacional de Pesquisas Espaciais.

 
Anterior Proxima
Atualizado em 10/04/2004
http://www.comciencia.br
contato@comciencia.br

© 2003
SBPC/Labjor
Brasil