Uma das tarefas de otimização mais comuns é o roteamento de veículos, em que o objetivo é encontrar os melhores trajetos para uma frota de veículos que visitam um conjunto de locais. Normalmente, "melhor" significa trajetos com a menor distância ou custo total. Veja alguns exemplos de problemas de roteamento:
- Uma empresa de entrega de pacotes quer atribuir rotas para que os motoristas façam entregas.
- Uma empresa de TV a cabo quer atribuir rotas para que os técnicos façam chamadas de serviços residenciais.
- Uma empresa de compartilhamento de viagens quer atribuir rotas para que os motoristas embarquem e desembarquem.
O problema de roteamento mais famoso é o Problema do vendedor viajante (TSP, na sigla em inglês): encontre a rota mais curta para um vendedor que precisa visitar clientes em locais diferentes e voltar ao ponto de partida. Um TSP pode ser representado por um gráfico, em que os nós correspondem aos locais, e as bordas (ou arcos) indicam viagem direta entre os locais. Por exemplo, o gráfico abaixo mostra um TSP com apenas quatro locais, rotulados como A, B, C e D. A distância entre dois locais é determinada pelo número próximo à borda que os une.
Ao calcular as distâncias de todos os trajetos possíveis, é possível notar que o trajeto mais curto é ACDBA, para o qual a distância total é de 35 + 30 + 15 + 10 = 90.
O problema fica mais difícil quando há mais locais. No exemplo acima, há apenas seis rotas. Mas, se houver 10 locais (sem contar o ponto de partida), o número de trajetos será 362.880. Para 20 locais, o número aumenta para 2432902008176640000. Uma pesquisa exaustiva de todos os trajetos possíveis pode encontrar as mais curtas, mas isso é computacionalmente intratável para todos, exceto para pequenos conjuntos de locais. Para problemas maiores, são necessárias técnicas de otimização para pesquisar de maneira inteligente o espaço de solução e encontrar uma solução ideal (ou quase ideal).
Uma versão mais geral do TSP é o problema de roteamento de veículos (VRP, na sigla em inglês), em que há vários veículos. Na maioria dos casos, os VRPs têm restrições: por exemplo, os veículos podem ter capacidades para o peso ou o volume máximo de itens que podem carregar, ou os motoristas podem precisar visitar os locais durante os períodos especificados solicitados pelos clientes.
As ferramentas OR podem resolver vários tipos de VRPs, incluindo:
- Problema do vendedor de viagens, o problema clássico de trajeto em que só há um veículo.
- Problema de roteamento de veículos: uma generalização do TSP com vários veículos.
- VRP com restrições de capacidade, em que os veículos têm capacidade máxima para os itens que podem carregar.
- VRP com períodos de tempo, em que os veículos precisam visitar os locais em intervalos especificados.
- VRP com restrições de recursos, como espaço ou pessoal para carregar e descarregar veículos no depósito (o ponto de partida dos trajetos).
- VRP com visitas perdidas, em que os veículos não precisam visitar todos os locais, mas têm uma penalidade para cada visita que é perdida.
Limitações para resolver problemas de definição de trajeto de veículos
Problemas de trajeto de veículos são inerentemente intratáveis: o tempo necessário para resolvê-los cresce exponencialmente com o tamanho do problema. Para problemas suficientemente grandes, pode levar anos para que a ferramenta OR (ou qualquer outro software de roteamento) encontre a solução ideal. Como resultado, às vezes, OR-Tools retorna soluções boas, mas não ideais. Para encontrar uma solução melhor, mude as opções de pesquisa do solucionador. Consulte um exemplo em Como alterar a estratégia de pesquisa.