Caixeiro Viajante

resolução do PROBLEMA DO ENTREGADOR VIAJANTE
MARCO AURÉLIO PACHECO, RICARDO FUKASAWA
Departamento de Engenharia Elétrica, Pontifícia Universidade Católica do Rio de Janeiro
Rua Marquês de São Vicente, 225, Gávea, Rio de janeiro, RJ, CEP. 22453-900, BRASIL
E-mail: [e-mail] / [e-mail]

Resumo: Este artigo descreve os experimentos feitos tentando aplicar algoritmos genéticos para resolver uma modificação do problema do caixeiro viajante, chamada problema do entregador viajante. Foi feito um programa modificado para ajustar-se às condições que resolve o problema do caixeiro viajante achando soluções (sub) ótimas. Este programa emprega técnicas gerais de algoritmos genéticos e técnicas específicas. Assim como no caixeiro viajante, o problema se propõe a encontrar uma rota que passe por todas as cidades, e que tenha custo mínimo. A diferença é que este problema enfoca menos o lado do entregador e mais o lado do “cliente”.
Palavras chave: algoritmos genéticos, caixeiro viajante.
Abstract:
This article describes the experiments conducted to attempt to apply genetic algorithms to solve a modification of the traveling salesman problem, called the problem of delivery traveler. A modified program was made to adjust to the conditions to solve the traveling salesman problem by finding optimal solutions (sub). This program uses general techniques of genetic algorithms and techniques. As the traveling salesman problem proposes to find a route passing through every town, and at minimum cost. The difference is that this issue focuses less on the side of delivery and more on the side of the "client".
Keywords: genetic algorithms, traveling salesman.

1. Introdução:
O problema do caixeiro viajante é um problema muito famoso e muito estudado.
Um caixeiro viajante, partindo de sua cidade, deve visitar exatamente uma única vez cada cidade de uma dada lista e retornar para casa tal que a distância total percorrida seja a menor possível.