Aplicações GIS: Otimização de rotas

Quando pensamos em uma solução que inclua sistemas GIS a primeira e mais trivial idéia é aplicá-lo ao problema do caixeiro-viajante (TSP do inglês 'travelling salesman problem').
O TSP consiste basicamente no seguinte: Como fazer o caixeiro viajar por várias cidades percorrendo o menor caminho. Por 'menor caminho' é possível definir diversas definições, por exemplo o menor caminho sendo o de menor distância, ou o menor caminho sendo o que passar por menos pedágios, ou mesmo a combinação de mais de um desses.
Há muito estudo sobre a melhor forma de resolver esse problema e ter abordagens criativas. Há muitos algoritmos  desenvolvidos para tal, e sua aplicação em sistema de logística é direta.
Para empresas de transporte a solução do TSP é importantíssima, entretanto o TSP é a versão simplificada do problema real para essas empresas. Empresas de transporte tem normalmente mais de 1 'caixeiro viajante'. A otimização é buscada obtendo o caminho mais barato entre diversas cidades utilizando diversos veículos (representação real do caixeiro viajante). Além disso outros parâmetros podem ser usados como entrada do problema como por exemplo tempo limite para se visitar todos os pontos, exemplo na distribuição de jornais, eles devem ser entregues até uma hora limite.
Esse problema de roteamento de veículos (PRV) é um dos mais estudados problemas na área da otimização combinatória. E novamente ele pode ter diversas variantes como:

• Problema de roteamento de veículos capacitados (PRVC)
• Problema de roteamento de veículos com janela de tempo (PRVJT)
• Problema de roteamento de veículos com coleta e entrega
• Problema de roteamento de veículos com múltiplos depósitos
• Problema de roteamento de veículos periódico (PRVP)
• Problema de roteamento de veículos periódico com janela de tempo
• Problema de roteamento de veículos com entregas particionadas

Todos esses problemas se beneficiam de sistemas GIS para obter diversas informações, a mais direta é os possíveis caminhos. Um mapa de estradas ou ruas permite traçar quais são as possíveis rotas a se percorrer, além de também determinar as localidades que se deve visitar, como mostra o mapa abaixo:

Nele há 4 pontos a serem alcançados com algumas simples possíveis rotas. Entretanto esse mapa pode ser mais complicado como o seguinte:

A análise dele é mais complicada e sistemas de ajuda na geração da melhor rota se tornam indispensáveis em empresas de logística. Para se ter uma idéia o custo de entrega de um produto é, em média, 10-15% do valor do produto.
Sistemas GIS permitem resolver o melhor traçado acima tendo dados da rede de caminhos e a localização dos pontos de entrega e dos veículos. Há possibilidade não utilizar dados geo referenciados para resolver o TSP, entretanto com a utilização de dados geo referenciado se pode ter melhorias na solução como re-definição das rotas em tempo real. Com GIS é possível monitorar a posição dos veículos assim pode-se re-gerar as rotas ótimas entre os pontos.
Além disso é possível obter outras informações geo-referenciadas como previsão do tempo para uma região ou informações de tráfego de uma região ou sobre desastres naturais como ponte ou pistas interditadas.

Fazendo a convergência dessas informações se tem não só a possibilidade de facilmente evitar problemas nos percursos, re gerando o melhor percurso automaticamente, como dando suporte decisões mais complexas no planejamento de percurso.
Mais, tendo os veículos geo-referenciado pode-se criar zonas proibidas e monitoramento do percurso percorrido, detectando desvios desnecessários e/ou perigosos.

Casos de sucesso da aplicação de GIS para roteamento de frotas existem para empresas como DHL e o The Washington Times.

Concluindo, é fácil perceber que a utilização de GIS para solucionar o problema otimização de roteamento de frota aumenta muito a qualidade de solução. GIS permite a convergência de dados geo referenciados resultando numa rota que se baseia informações importantes como tráfego, clima e regiões restritas.