Skip to content

Latest commit

 

History

History
89 lines (59 loc) · 4.22 KB

README.md

File metadata and controls

89 lines (59 loc) · 4.22 KB
Raw

dotnet-caixeiro-viajante-TSP

Download versão 1.0.0

image

Caixeiro Viajante Tradicional Algoritmo p/ Caixeiro Viajante
image image
  • Implementação para resolver o problema do caixeiro viajante para N pontos utilizando a biblioteca Gurobi para realizar a otimização.
  • A estratégia adotada para a otimização utiliza as regras de restrição baseadas no algoritmo de Miller-Tucker-Zemlin (MTZ).

Domínio

image

  • A função objetivo é a somatória de todas as arestas, para isso tem-se três restrições:

  • Cada ponto de destino deve ser visitado uma única vez pelo viajante

  • Cada ponto de origem deve ter um único ponto chegada

  • Todos os pontos devem ser visitados sem utilizar subrotas

Objetivo

  • Escolher a melhor rota de modo a otimizar os custos diminuindo a distância total percorrida

Tecnologias

Licença Gurobi

  • Para utilizar a biblioteca é necessário realizar cadastro no site Gurobi
  • Realizar o download e instalação do programa Gurobi Optimizer
  • Solicitar uma licença acadêmica (necessário uma conta de email universitária)
  • Com a licença criada em Gurobi ir em detalhes, pegar o id da chave e executar o comando no terminal (com a sua respectiva chave)
grbgetkey xx-xx-xx-xx-xx
  • Executar o programa Gurobi Token Server
  • Baixar e rodar imagem Docker do Gurobi
docker pull gurobi/optimizer
  • Criar projeto dotnet e adicionar o pacote via Nuget
dotnet add package OPTANO.Modeling.Gurobi --version 9.1.2.26`

Limitações

  • Na resolução do problema obtem-se muitas subrotas que entram em conflito com as restrições do domínio (não repetição de pontos e que todos eles sejam visitados), então cria-se restrições manualmente para evitar essas subrotas no modelo.
  • Como limitante há um crescimento exponencial no número de restrições conforme aumenta-se o número de pontos
  • A consequência desse fenônemo é o consumo de recurso computacional
  • O algoritmo MTZ dispensa a adição manual das restrições de subrotas reduzindo consideravelmente o custo computacional

Restrições de Miller-Tucker-Zemlin(MTZ)

image

  • Como comparação uma rota com 20 pontos teria 1.048.554 combinações de restrições no modelo e com esse algoritmo apenas 342 restrições, percentual de 0,032% em comparação ao método tradicional.
  • Mesmo o algoritmo MTZ removendo subrotas com um número de restrições excepcionalmente menor que o método convencional a solução ainda continuará sujeita ao limite de recurso computacional do hospedeiro.

Próximos passos

  • Implementar outra estratégia como solução para o TSP sem MTZ, que em tempo de execução identifica existência de subrotas e adiciona-as dinâmicamente como restrição do modelo antes de gerar a solução.
  • Verificar exemplos de implementação no site do Gurobi
  model.SetCallback(new tsp_cs(vars));
  model.Optimize();

Referência

Material obtido do Pr. Dr. Gustavo Valentim Loch da UFPR.