miniaturadaimagem|O problema do caixeiro-viajante busca encontrar o menor caminho que faz uma volta e conecta todos os pontos O problema do caixeiro-viajante (PCV) é um problema que tenta determinar a menor rota para percorrer uma série de cidades (visitando uma única vez cada uma delas), retornando à cidade de origem. Ele é um problema de otimização NP-difícil inspirado na necessidade dos vendedores em realizar entregas em diversos locais (as cidades) percorrendo o menor caminho possível, reduzindo o tempo necessário para a viagem e os possíveis custos com transporte e combustível.

História As origens do problema do caixeiro viajante — inclusive do seu nome — são desconhecidas. Um manuscrito de 1832 menciona o problema e apresenta exemplos de cidades da Alemanha e Suíça, mas não contém nenhum teor matemático.

Nos anos de 1800, problemas relacionados com o PCV começaram a ser desenvolvidos por dois matemáticos: o escocês William Rowan Hamilton e o britânico Thomas Penyngton Kirkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. Hassler Whitney apresentou interesse no tema e o abordou como o "problema dos 48 estados". Merril M. Flood estudou um problema de rota de ônibus escolar e considerou o problema. Inclusive, Flood, da Universidade de Princeton, considera o problema como o "problema de Whitney".

Apesar das pequenas variações ortográficas, como traveling vs travelling ou salesman vs salesman's, o nome do problema ficou globalmente conhecido por volta do ano 1950. Em 1949, uma das primeiras publicações contendo a expressão "problema do caixeiro viajante" foi publicada pela RAND Corporation sob autoria de Julia Robinson: On the Hamiltonian game (a traveling salesman problem).

Nos anos de 1950 e 1960, o problema ganhou popularidade na esfera científica, e organizações estabeleceram prêmios para o desenvolvimento de passos para sua solução. Contribuições notáveis foram realizadas por, por exemplo, George Dantzig, Delbert Ray Fulkerson e Selmer Martin Johnson, que utilizaram de programação inteira e desenvolveram um método de planos de corte para sua solução. Em 1959, Jillian Beardwood, J. H. Halton e John Hammersley desenvolveram uma fórmula para determinar o menor caminho a partir de uma casa e passando por pontos fixos antes de voltar ao início.

A partir da década de 1960, alguns pesquisadores abandonaram a busca de soluções otimizadas e se concentraram na busca de soluções cujo comprimento era limitado e, a partir disse, criavam árvores com os grafos na busca pela solução.

Na década de 1980, Halton e Terada apresentaram um algoritmo otimizado para o problema do caixeiro-viajante em k-dimensões euclidianas. Na década de 1990, foi desenvolvido o programa aberto Concorde, que busca por soluções do problema. O programa foi aplicado em áreas como mapeamento genético, rota de veículos, cronograma de barcos e navios e problemas de combinatória.

Definição e formulação do problema thumb|right|400px|Figura 1. Problema do caixeiro-viajante.

O problema do caixeiro-viajante (representado na Figura 1) consiste na procura de um circuito que possua a menor distância, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial.

Formulação combinatória Dado um conjunto de n cidades ci e uma matriz de distâncias , onde , , , a tarefa passa por encontrar a permutação que faça com que a função objectivo (distância do circuito) , onde

,

atinja o seu mínimo.

O tamanho do espaço de procura aumenta exponencialmente dependendo de n, o número de cidades, uma vez que existem

circuitos possíveis (a posição inicial é arbitrária, e a ordem do circuito pode ser invertida).

Embora tenham sido desenvolvidos bons algoritmos de aproximação para o PCV, o problema continua a oferecer uma grande atracção para a aplicação de novos algoritmos, tais como os evolucionários. Isto deve-se, essencialmente, às seguintes razões:

A problemática do PCV pode ser entendida facilmente, uma vez que se aproxima dos problemas populares do mundo real; O PCV demonstra o caso mais simples dos problemas de requisição que são de enorme relevância para a programação de processos industriais; Existem vários conjuntos de dados sobre o PCV «standard» que estão disponíveis em literatura, de tal forma que os resultados são comparáveis mesmo que o óptimo global não seja ainda definitivamente conhecido; Relativamente à complexidade computacional, o PCV, como um problema NP-completo, é conhecido por representar uma larga classe de problemas para os quais não existem algoritmos polinomiais em séries temporais determinísticos.

Representação continua do PCV A topologia de um PCV pode ser visualizada segundo uma representação contínua do problema:

Partindo de , uma permutação pode ser obtida através de uma ordenação das componentes do vector, que originam um novo vector de tal forma que . A nova ordem é interpretada como o circuito resultante da permutação.

Formulação gráfica No domínio da teoria dos grafos, cada cidade é identificada com um nó (ou vértice) e as rotas que ligam cada par de nós são identicadas como arcos (ou arestas). A cada uma destas linhas estarão associadas as distâncias (ou custos) correspondentes. Desde que seja possível ir directamente de uma cidade para qualquer outra, o gráfico diz-se completo. Uma viagem que passe por todas as cidades corresponde a um ciclo Hamiltoniano, representado por um conjunto específico de linhas. A distância do ciclo é o somatório das distâncias das linhas presentes no mesmo.

Formalmente, o problema pode ser representado por um grafo G(V, E), com e custos , , referentes a cada uma das arestas. O objectivo, no caso de um grafo completo com n vértices (cidades) é encontrar o melhor circuito entre os possíveis.

Dependendo da importância que poderá ter o sentido das setas(arestas), entre nós(cidades), o PCV pode-se distinguir em simétrico ou assimétrico.

PCV assimétrico Dependendo da importância que a direção das arestas que atravessam o grafo possam ter, distingue-se o PCV assimétrico do simétrico.

O PCV assimétrico é o problema de encontrar o caminho hamiltoniano mais curto de grafos ponderados. Os vértices são as cidades, enquanto os pesos são as distâncias entre elas.

Para formular o PCV assimétrico em m cidades, introduzem-se variáveis zero ou um:

Assim, e dado o facto de que a cada nó do grafo apenas pode corresponder e sair uma seta (Figura 2), um obtém uma atribuição clássica do problema. Estas restrições, contudo não são suficientes, uma vez que esta formulação permite a ocorrência de subcircuitos, ou seja, mesmo respeitando as condições impostas, considera-se a formação de aglomerados de cidades sem ligação. Por esta razão, a formulação do problema tem que possuir condições necessárias para remoção de subcircuitos. Assim, o problema é reformulado da seguinte forma:

thumb|right|300px|Figura 2. Entrada e saída de uma seta por cada nó.

Onde:

K é um subconjunto não vazio apropriado das cidades 1, ..., m; O custo pode ser diferente do custo ; Existem m(m-1) zero-um variáveis.

PCV simétrico Para formular o PCV simétrico, um demonstra que a direcção atravessada é imaterial, de modo que = . Uma vez que a direcção não tem interesse, um pode considerar o gráfo onde existe apenas um arco, sem direcção, entre todos os pares de nós. Assim, é a variável de decisão onde j percorre todos os arcos E do grafo, sem direcção, e é o custo de percorrer cada troço. Para encontrar um circuito neste gráfo, um, deve seleccionar um subconjunto de arcos, tal que todos os nós estejam contidos exactamente em dois dos arcos seleccionados. Assim, o problema pode ser formulado como um problema 2-matching no gráfo com m(m-1)/2 zero-um variáveis, isto é, metade do número da formulação anterior. Tal como no caso assimétrico, os subcircuitos devem ser eliminados através de restrições de eliminação de subcircuitos. O problema pode então ser formulado como:

onde J(j) é o conjunto de todos os arcos, não direccionados, ligados ao nó j e E(K) é o subconjunto de todos os arcos, não direccionados, que ligam as cidades em qualquer subconjunto K não vazio apropriado de todas as cidades.

É evidente que o problema simétrico é um caso especial do assimétrico, mas experiências práticas demonstram que os algoritmos para o problema assimétrico, regra geral, desenvolvem mal no simétrico. Assim, este tipo de problemas requerem formulações especiais e tratamentos de soluções (Hoffman, 2000).

Tipologia de métodos para a resolução do PCV A solução do PCV pode ser determinada por diferentes métodos. Estes, podem ser agrupados em métodos exactos e heurísticos. Os primeiros têm por base procedimentos

Os métodos heurísticos são procedimentos bastante particulares, o que os torna inflexíveis para a determinação de boas soluções para um outro problema ligeiramente diferente.

As heurísticas podem ser agrupadas em métodos de construção de circuitos e métodos de melhorias de circuitos.

Métodos de construção de circuitos Nestes métodos, o circuito é construído sequencialmente, isto é, os nós vão sendo inseridos faseadamente, mediante certas condições, sem que exista qualquer modificação posterior à inserção definida pelo processamento do algoritmo.

A construção do circuito pode ser elaborada através dos seguintes métodos:

Vizinho mais próximo, que é caracterizado pela escolha da cidade mais próxima, sempre que o caixeiro se desloque, até que todas as cidades sejam visitadas; De inserção, que se descreve pela inclusão de cidades, uma a uma, atendendo a um determinado critério de proximidade, por exemplo, a cidade mais distante, partindo de um circuito inicial com duas cidades. Aquando da inserção, a escolha deve ser analisada entre cada par de cidades do circuito parcial, até que todas estejam inseridas; Da cobertura mínima, onde é elaborada um árvore que contenha todas as cidades, com a finalidade de se encontrar uma árvore de cobertura com a menor soma de distâncias possível; Das economias, ou heurística de Clarke e Wright, que consiste no agrupamento sequencial de cidades, com base numa ordem decrescente de economias decorrentes da sua inclusão, isto é, considerando o impacto, da junção do nó no circuito, nas economias agregadas da distância entre nós e da distância de cada um dos nós ao nó inicial. Algoritmo de Christofides, cuja ideia geral é: criar uma árvore geradora mínima T; criar um subgrafo M induzido pelo acoplamento perfeito dos nós de grau ímpar da árvore T, formar um multigrafo H com a união de T e M, gerar um circuito Euleriano em H e, por fim, eliminar os nós repetidos do circuito.

Métodos de melhoria de circuitos Estes métodos procuram melhorar o circuito obtido através de algum outro método. Para tal, o método mais utilizado, elaborado por Lin e Kernighan em 1973, denomina-se por k-opt. Nesta proposta, k arcos são substituídos, no circuito, por outros k arcos com o objectivo de diminuir a distância total percorrida.

Quanto maior for o valor de k, melhor é a precisão do método, mas maior é o esforço computacional.

Com a variação do valor k, no método de melhoria k-opt, a heurística de Lin e Kernighan aumentaria a sua eficiência quando comparada com o mesmo método utilizando um valor de k fixo. Desta forma, o método não fica mais simples, contudo passa a ser possível a aplicação do método a problemas mais abrangentes com resultados favoráveis.