Resolução do problema do caixeiro viajante utilizando metaheurística vnsvnd com programação distribuída socket tcp

RESOLUÇÃO DO PROBLEMA DO CAIXEIRO VIAJANTE UTILIZANDO METAHEURÍSTICA VNS/VND COM PROGRAMAÇÃO DISTRIBUÍDA SOCKET TCP

Aldorico Passamani Layber¹, Claudio Vidal Augusto¹, Leticia Borsoi Justi¹ e Bruno Missi Xavier¹
¹Centro Universitário São Camilo - ES [e-mail]; [e-mail]; [e-mail]; [e-mail]

Resumo O Problema do Caixeiro Viajante é considerado na literatura como NP-Difícil, e cresce em complexidade à medida que aumenta o número de nó. Este trabalho apresenta a criação de uma heurística associada a técnicas de processamento distribuído a fim de dividir entre uma rede de computadores, o custo computacional do problema. O objetivo deste estudo é gerar uma solução em tempo computacional melhor que as técnicas de programação convencionais. Quanto a metodologia, foi desenvolvida uma heurística baseada em VNS/VND e Socket TCP, onde sua execução foi comparada aos resultados da heurística não distribuída. Os resultados obtidos demonstram uma boa vantagem no tempo computacional do algoritmo distribuído em relação ao algoritmo não distribuído. Este trabalho contribui para o esclarecimento da utilização de técnicas de programação distribuídas aliadas ao desenvolvimento de heurísticas.

Palavras-chave: Problema do Caixeiro Viajante; VNS/VND; Socket TCP.

Introdução

Este trabalho tem como objetivo mostrar técnicas heurísticas para resolver o Problema do Caixeiro Viajante (PCV), em tempo computacional acessível, onde é um dos mais antigos problemas de complexidade. Caracteriza-se por, dado um conjunto de n cidades e uma matriz de distâncias, fazer com que seja localizado um caminho que tenha a menor distância a ser percorrida para que sejam visitadas todas as cidades passando precisamente uma única vez em cada cidade e voltando a cidade de origem formando um ciclo hamiltoniano, enquanto simultaneamente minimiza alguma função de custo. O PCV é considerado um problema de otimização, além de exibir uma