Uma pesquisa científica realizada por pesquisadores do Instituto de Ciências Exatas e Tecnologia (ICET), no município de Itacoatiara, pretende resolver diferentes instâncias do Problema do Caixeiro Viajante (PCV) com boas soluções. A pesquisa é encabeçada pelo professor doutor Jorge Yoshio Kanda e tem linha de atuação na iniciação científica.

O problema do caixeiro é um clássico exemplo de como a computação pode atuar na resolução de problemas que exigem a otimização de combinações.

Dentre outras aplicações práticas a resolução do PCV pode apresentar uma modelagem matemática de otimização de rotas de veículos de cargas, que necessitam entregar mercadorias em diversos pontos de uma localidade percorrendo uma distância mínima, assim, não havendo a execução de deslocamentos desnecessários e, consequentemente, um melhor aproveitamento do tempo, de combustível, diminuição das despesas e maximização dos lucros.

Este problema é muito importante para a Logística, pois ajuda a definir as melhores rotas possíveis. Empresas que abastecem muitos clientes ou que têm muitas filiais, a escolha dos caminhos passa a ter muita relevância nos custos. Do ponto de vista teórico o PCV é muito mais amplo que isto, tendo aplicabilidade em inúmeros outros casos.

Este mesmo problema é usado para otimizar a fabricação de microchips, obtendo os caminhos mais curtos para os circuitos integrados, a otimização de padrões de corte em chapas e placas, economizando material quando obtém o melhor aproveitamento possível, além de economizar o uso e troca das facas ou lasers que fazem o corte, e em uma versão levemente modificada ele ajuda a fazer o sequenciamento do DNA. Um problema típico com algumas centenas de pontos (cidades) pode levar muitas horas para ser resolvido, pois as combinações possíveis crescem muito rapidamente.

Segundo Kanda, os três alunos de PIBIC envolvidos estão pesquisando técnicas de otimização que resolvam instâncias desse problema. "Este é um exemplo de problema computacionalmente conhecimento como NP Completo, ou seja, é um problema difícil de ser resolvido rapidamente de maneira exata por um procedimento exaustivo, principalmente quando há muitas variáveis envolvidas. Por isso, a nossa pesquisa consiste em analisar técnicas de otimização que buscam por uma boa solução, próxima da solução ótima, mas que possa ser fornecida no menor tempo possível", explicou.

Neste tipo aplicação há muito interesse científico e prático, pois a aplicação desses modelos computacionais podem trazer inúmeros benefícios para a sociedade.