Problema do caixeiro-viajante

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.

Fatos históricos

A origem do nome «travelling salesman problem» é desconhecida. Não parece existir qualquer documento que prove o(a) autor(a) do nome do problema. Merril Flood, da Universidade de Princeton, um dos investigadores mais proeminentes nas primeiras aplicações do problema proferiu, no entanto, o seguinte comentário: «I don´t know who coined the peppier name "Traveling Salesman Problem" for Whitney's problem, [...]» (Applegate et al., cop. 2006, p. 2).

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 Kerkman. A forma geral do PCV parece ter sido, pela primeira vez, estudada por matemáticos nos anos de 1930 em Harvard e Viena. O problema foi posteriormente estudado por Hassler Whitney e Merril Flood em Princeton. Exceptuando 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 (Applegate et al., cop. 2006, p.2).

Definição e formulação do problema

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 (Nilsson, 1982).

Formulação combinatória

Dado um conjunto $C=\{c_{1}\;,...,\;c_{n}\}$ de n cidades c_i e uma matriz de distâncias $\left(\rho _{ij}\right)$, onde $\rho _{ij}=\rho (c_{i},\;c_{j})$ $($ $i,\;j$ $\in$ $\{1,\;...,\;n\}$, $\rho _{ij}$ $=\rho _{ji}$, $\rho _{ii}$$=0)$, a tarefa passa por encontrar a permutação $\pi \in S_{n}=\{s:\{1,...,n\}\rightarrow \{1,...,n\}\}$ que faça com que a função objectivo (distância do circuito) $f:S_{n}\rightarrow \mathbb {R}$, onde

         $f(\pi )=\sum _{i=1}^{n-1}\rho \pi (i),\pi (i+1)+\rho \pi (n),\pi (1)$,

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

         $(n-1)!/2\approx {1 \over 2}{\sqrt {2\pi (n-1)}}\left({\frac {n-1}{e}}\right)^{n-1}$

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:

         ${\vec {x}}\in [u,v]^{n};u,v\in \mathbb {R}$

Partindo de $\ {\vec {x}}\ =(x_{1},...,x_{n})\in [u,v]^{n}\$ , uma permutação $\pi$ pode ser obtida através de uma ordenação das componentes do vector, que originam um novo vector ${\vec {x}}^{\prime }\ =(x_{\pi (1)},...,x_{\pi (n)})$ de tal forma que $\ x_{\pi (1)}\;<\;x_{\pi (2)}\;<\;x_{\pi (n)}\$. A nova ordem $\ \pi (1),\;\pi (2),\;\pi (n)\$ é interpretada como o circuito resultante da permutação (Bäck, 1996).

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 $|V|\geq 3$ e custos $c_{ij}$, $\left(i,\;j\right)$ $\in E$, 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 $[(n-1)!/2]$ 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 (Guedes, 2005).

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. Para formular o PCV assimétrico em m cidades, introduzem-se variáveis zero ou um:

         $x_{ij}={\begin{cases}1,&{\mbox{se }}i\rightarrow j{\mbox{ existe}}\\0,&{\mbox{se }}i\rightarrow j{\mbox{ não existe}}\end{cases}}$

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:

Figura 2. Entrada e saída de uma seta por cada nó.

${\rm {min}}\sum _{j=1}^{m}\sum _{i=1}^{m}c_{ij}x_{ij}$ ${\rm {Sujeito}}\,{\rm {a}}:\sum _{j=1}^{m}x_{ij}=1\qquad \qquad \forall i=1,...,m$ $\sum _{i=1}^{m}x_{ij}=1\qquad \qquad \forall j=1,...,m$ $\sum _{i\in K}\sum _{j\in K}x_{ij}\leq |K|-1\qquad \qquad \forall i,j$ $x_{ij}=\{0,1\}\qquad \qquad \forall i,j$

Onde:

• K é um subconjunto não vazio apropriado das cidades 1, ..., m;
• O custo $c_{ij}$ pode ser diferente do custo $c_{ji}$;
• 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 $c_{ij}$ = $c_{ji}$. 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, $x_{j}\ \varepsilon \ {0,1}$ é a variável de decisão onde j percorre todos os arcos E do grafo, sem direcção, e $c_{j}$ é 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 $G^{V}$ 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:

${\rm {min}}\ {\frac {1}{2}}\sum _{j=1}^{m}\sum _{k\in J(j)}c_{k}\ x_{k}$ ${\rm {Suj.a:}}\sum _{k\in J(j)}x_{k}=2\qquad \qquad \forall j=1,...,m$ $\sum _{j\in E(K)}x_{j}\leq |K|-1\qquad \qquad \forall K\subset {1,...,m}$ $x_{j}=\{0,1\}\qquad \qquad \forall j\varepsilon E$

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 «branch-and-bound» (em inglês). , isto é, de enumeração implícita em árvore onde é necessário inserir um limite inferior, no leque de soluções do problema. Existem limites inferiores triviais, como por exemplo, o elemento mínimo das soluções encontradas. Contudo, este tipo de métodos demonstram muita dificuldade quando aplicados a problemas muito complexos, isto é, um PCV com muitas cidades, uma vez que a árvore de enumeração é muito extensa (Conway, 2003). 

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 (Cunha, 2002) e (Goodrich, 1899).
• 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.

Para além deste método, existem outros métodos de melhorias baseados em metaheurísticas do tipo simulated annealing e busca tabu. Estes, para além de se basearem no desenvolvimento k-opt, procuram uma solução que não a dada pelos métodos anteriores. No simulated annealing é utilizado um controlo de possibilidades de solução melhores partindo de piores, no início. Na busca tabu os movimentos considerados tabu, isto é, que não se podem efectuar, mesmo que melhorem a solução são temporariamente interditos com o objectivo de se alcançar soluções piores no início que no final poderão ser consideradas melhores (Laporte, 2002) e (Heslgaun, 2000), citados por (Cunha, 2002).

Exemplos

WRNN e WTA

A rede neural periódica de Wang, do inglês Wang Recurrent Neural Network (WRNN), com o princípio Winner Takes All (WTA), pode ser aplicada para a resolução do PCV. Além disso, a utilização do princípio WTA nas soluções encontradas pelo WRNN faz com que as mesmas formem circuitos exequíveis. Como tal, este é um método de construção (WRNN) e de melhoria (WTA) de circuitos.

O número médio de iterações necessárias para a resolução do PCV utilizando o WRNN é de 4463, com o WRNN + WTA é de 41, isto em problemas que variam entre 3 x 3 e 20 x 20.

A WRNN é caracterizada por uma equação diferencial, que engloba uma função do tipo sigmóide. Os vários parâmetros incluídos nas equações afectam a convergência da rede, pois trata-se de factores penalizantes pelas violações às restrições do problema, de controlo para a minimização da função objectivo, entre outros. Esta formulação possui ainda um termo que avalia as violações às restrições do problema dando a indicação do cumprimento das mesmas, após um certo número de iterações. Depois de encontrados tais parâmetros, aplica-se o princípio WTA que pode ser dado através do seguinte algoritmo:

1) Determinar o número máximo de circuitos r_max e encontrar uma solução para o problema utilizando a técnica WRNN. Se o termo que avalia as restrições for satisfeito, segue-se para o passo 2, caso contrário encontra-se outra solução x.

2) Dada uma matriz de decisão, considera-se uma matriz ${\overline {x}}$, onde ${\overline {x}}$ = x = $x$;

3) Escolhe-se uma linha k na matriz de decisão ${\overline {x}}$. Faz-se p = k, $x^{\prime }(m)=k$:

4) Encontra-se o maior elemento da linha k, ${\overline {x}}_{kl}$. O valor deste elemento é dado por metade do somatório de todos os elementos da linha k:

         ${\overline {x}}_{kl}={\frac {1}{2}}\left(\sum _{i=1}^{n}x_{il}+\sum _{j=1}^{n}x_{kj}\right)$

Os outros elementos da linha k e da coluna l passam a ser nulos. Para que não exista a formação de sub circuitos os elmentos da coluna k têm, também, que ser nulos. Depois destas condições, faz-se $x^{\prime }(m+1)=l$ e avança-se para o passo 5.

5) Se m < n, então faz-se m = m + 1 e retorna-se ao passo 4. Caso contrário, aplica-se a seguinte expressão:

         ${\overline {x}}_{kp}={\frac {1}{2}}\left(\sum _{i=1}^{n}x_{ip}+\sum _{j=1}^{n}x_{kj}\right)$

A equação $x^{\prime }(n+1)=p$ determina o custo do circuito, z.

6) Se z <z_min, faz-se z_min = z e x = ${\overline {x}}$. De seguida verifica-se se r <r_max pela equação r = r + 1. Se tal acontecer, inicia-se o procedimento do WRNN no passo 2, caso contrário finaliza-se o algoritmo.

Este procedimento pode ser aplicado tanto ao PCV simétrico como ao assimétrico (Siqueira, 2006).

Algoritmos genéticos

Os algoritmos genéticos (AGs) são um dos vários métodos que se utilizam para a resolução de problemas complexos. Este método tem por base um processo iterativo sobre uma determinada população fixa, denominados por indivíduos, que representam as várias soluções do problema. Esta técnica advém do processo de evolução dos seres vivos demonstrada por Darwin.

Da mesma forma que os sistemas biológicos, ao longo da sua evolução, tiveram que se «moldar» às alterações ambientais para a sua sobrevivência, os AGs acumulam a informação sobre o ambiente com o intuito de se adptarem ao novo meio. Tal informação funciona como um sistema de triagem para a obtenção de novas soluções exequíveis.

O método dos algoritmos genéticos é muito utilizado devido à simplicidade de operação, eficácia pela determinação de um máximo global e aplicabilidade em problemas onde se desconhece o modelo matemático ou onde o mesmo se torna impreciso em funções lineares e não-lineares (Costa, 2003).

Método de aplicação

A formação de um algoritmo genético convencional desenvolve-se através dos seguintes passos:

1. Representação de uma solução (Loco) na estrutura do cromossoma;
2. Construção de uma população (indivíduos) inicial de cromossomas;
3. Mecanismo para avaliação dos cromossomas mediante as suas características;
4. Mecanismo para reprodução de cromossomas, designado por operador genético;
5. Definição dos parâmetros de um AG.

Para o desenvolvimento do primeiro passo, deve-se ter em consideração que a representação tradicional de um algoritmo genético é feita por binários (zero-um). Esta representação, embora eficiente, torna-se cada vez mais limitada à medida que o número de restrições do problema cresce. Desta forma, convencionou-se a utilização de um vector, formado por números inteiros, para a representação de um cromossoma.

Qualquer que seja a representação escolhida, a mesma deve verificar uma associação correcta com as soluções do problema em estudo. Isto é, para cada solução deve existir um cromossoma associado, atribuído pelo AG, e vice-versa.

Para o PCV a representação que mais se adequa é a dos números inteiros. Tal facto, deve-se à possibilidade de obtenção de soluções, por sequência de três bits, além do número de cidades do problema.

Para a construção de uma população inicial de cromossomas (passo 2), o AG demonstra uma capacidade bastante alta. Pegando num exemplo de um PCV com n cidades, a tarefa de se obter k soluções exequíveis numa estrutura de k cromossomas, mediante a utilização da representação por números inteiros, tem o mesmo significado que a obtenção de k vectores com n números inteiros, de 1 a n e diferentes entre eles. Caso a obtenção da população inicial de cromossomas seja difícil, isto é, caso o problema tenha vários parâmetros e restrições, torna-se mais fácil e rápido a utilização de heurísticas simples.

A avaliação dos cromossomas num AG, faz-se considerando a capacidade de sobrevivência dos cromossomas. Num PCV, esta capacidade de sobrevivência é relativa ao valor da função objectivo, que por sua vez, é avaliada pelo cromossoma associado. Para um PCV com n igual a 5 cidades, por exemplo, a capacidade do cromossoma é avaliada consoante o custo D, referente à soma das distâncias ($d_{ij}$):

         $D=d_{12}+d_{23}+d_{34}+d_{45}+d_{51}$

Assim, quanto menor o D, maior é o nível de aptidão do cromossoma.

O operador genético é o núcleo de um AG e o seu objectivo passa pela produção de novos cromossomas, com propriedades superiores relativamente aos que lhes deram origem.

Figura 3. Exemplo de crossover de um ponto, ou seja, um crossover com apenas uma quebra no cromossoma.

Nos AG convencionais, os operadores genéticos mais utilizados são a mutação e o «crossover» (em inglês). (Figura 3). O primeiro consiste numa alteração de genes de um cromossoma consoante a função probabilidade. O crossover consiste na produção de um ou dois cromossomas filhos, denominados como offsprings, com base nas informações dos dois cromossomas pais. Este operador demonstra uma determinada eficiência consoante a representação utilizada. Salienta-se que caso a representação adoptada seja a binária, é normal a produção de soluções não exequíveis, como referido anteriormente. 

Estes dois tipos de operadores, embora simples, têm a particularidade de não conseguirem dar uma resposta adequada quando confrontados com problemas de elevada complexidade.

Os parâmetros de um algoritmo genético que se devem ter em consideração, aquando da sua implementação, diferem entre autores. De uma maneira geral, os parâmetros são os seguintes:

• Tamanho da população;
• Selecção dos cromossomas reprodutores;
• Critério de sobrevivência dos cromossomas;
• Critério de finalização de um AG.

Sendo o PCV um problema de optimização muito complexo, o AG convencional é um método relativamente ineficaz quando comparado com outras heurísticas desenvolvidas. Desta forma, o AG sofreu vários desenvolvimentos com o intuito de dar resposta às condições propostas pelos problemas. A este conjunto de algoritmos genéticos dá-se o nome de algoritmos genéticos não convencionais (Ochi, 1998).

Algoritmo ACO

O PCV tem um papel importante na optimização das colónias de formigas, «ant colony optimization (ACO)» (em inglês). , desde o primeiro algoritmo ACO, chamado «Sistema de Formigas», do inglês Ant System, até aos mais recentes. 

O PCV foi escolhido por muitas razões:

• É um problema para o qual os algoritmos ACO são facilmente aplicados;
• É um problema de optimização NP-difícil;
• Serve de teste para a aplicação de novos algoritmos, e um bom desempenho no PCV é muitas vezes tido em consideração como prova da sua utilidade;
• É um problema facilmente perceptível, o que faz com que a linha de desenvolvimento de um algoritmo não se difunda em demasiados aspectos técnicos.

Nos algoritmos ACO, as formigas são simples agentes que, no caso do PCV, constroem circuitos através do movimento entre cidades no grafo do problema. A solução construída pelas formigas é elaborada por trilhos de feromonas (artificiais) e pela disponibilidade de informação heurística, à priori. Quando o algoritmo ACO é aplicado, é associada uma força da feromona , onde $\tau _{ij}(t)$ é uma informação numérica que é modificada durante o algoritmo, e t é o contador das iterações.

Para o PCV simétrico, o algoritmo ACO caracteriza-se por $\tau _{ij}(t)=\tau _{ji}(t)$. No assimétrico a igualdade pode ser desfeita por $\neq$ $\tau _{ji}(t)$.

Inicialmente, cada uma das m formigas é colocada numa cidade, de forma aleatória, aplicando-se depois, de modo iterativo, uma regra de transição de estado para cada uma das cidades.

Uma formiga constrói um circuito da seguinte forma. Na cidade i a formiga escolhe uma cidade j que ainda não tenha visitado. Esta escolha é feita probabilisticamente segundo a força da feromona $\tau _{ij}(t)$ no arco entre as cidades i e j, e a informação heurística disponível localmente, que é função do comprimento do arco. As formigas, de um modo probabilístico, preferem as cidades que estejam mais próximas e ligadas por arcos com grande força de feromona. Para construir um solução exequível, cada formiga possui uma forma de memória limitada, chamada tabu list onde é guardada o corrente circuito parcial. A memória é utilizada para determinar, a cada passo da construção, o conjunto de cidades que têm ainda que ser visitadas e para garantir que é elaborada uma solução exequível. Adicionalmente, permite à formiga refazer o seu circuito, assim que esteja completo.

Depois de todas as formigas terem construído um circuito, as feromonas são actualizadas. Isto é tipicamente elaborado através da descida da força dos trilhos das feromonas, através de um factor constante, e depois é dada liberdade para que as formigas depositem as suas feromonas nos arcos que visitaram. A actualização dos trilhos é feita de tal forma que os arcos mais curtos, ou visitados por muitas formigas, recebem quantidades maiores de feromonas e por isso são escolhidas com uma maior probabilidade nas iterações posteriores (Figura 4). Neste sentido, a quantidade de feromonas $\tau _{ij}(t)$ representa o desejo instruído de escolher a próxima cidade j quando a formiga estiver na cidade i.

Figura 4. Efeito do algoritmo ACO para a constituição do circuito preferencial.

Os algoritmos ACO que melhor desempenho têm no PCV, melhoram os circuitos construídos pelas formigas através da aplicação de algoritmos de procura local. Estes algoritmos são na verdade algoritmos híbridos que combinam a construção da solução de modo probabilístico com algoritmos de procura local.

No aspecto geral, todos os algoritmos ACO para o PCV seguem o esquema de um algoritmo específico. Depois de iniciados o rasto de feromonas e alguns parâmetros, o circuito principal é repetido até que a condição seja conhecida e rescindida. No circuito principal, primeiro as formigas constroem circuitos exequíveis, depois os circuitos produzidos são melhorados pela aplicação de uma procura local, e finalmente, os rastos de feromonas são actualizados. De facto, a maior parte dos algoritmos ACO que melhor se desenvolvem nos problemas NP-difícil seguem este esquema algorítmico.

Por fim é de salientar que as meta-heurísticas ACO são mais generalizados que o esquema algorítmico dado anteriormente (Stützle, 1999).

Algoritmo por programação dinâmica

Se pensarmos em um abordagem de força bruta, temos que avaliar todas as possíveis jornadas e retornar a melhor encontrada. Essa abordagem utiliza tempo O(n!).

Em programação dinâmica temos uma solução muito mais rápida, embora não polinomial.

A programação dinâmica reduz o número de possíveis combinações eliminando as que não poderão fazer parte de uma solução ótima do problema, dando assim origem a algoritmos mais eficientes.

A ideia básica é construir por etapas uma resposta ótima combinando respostas já obtidas para partes menores. Assim, é possível escolher subproblemas de modo que a informação vital seja recordada e levada a diante.

Precisamos saber todas as cidades visitadas, para que não repitamos nenhuma delas. Veja um subproblema apropriado:

Para um subconjunto de cidades $S\subseteq {1,2,...,n}$ que inclui $1$ e $j\in S$, seja $C(S,j)$ o comprimento do caminho mínimo visitando cada nó em $S$ exatamente uma vez, começando em $1$ e terminando em $j$.

Vamos expressar $C(S,j)$ em termos de subproblemas menores. Precisamos começar em $1$ e terminar em $j$; qual devemos escolher como a penúltima cidade? Ela tem de ser algum $i$ $\in S$, tal que o comprimento total seja a distância de $1$ até $i$, ou seja $C(S-\{j\},i)$, mais o comprimento da aresta final, $d_{ij}$. Temos de selecionar o melhor tal que:

$C(S,j)=\min _{i\in S,i\neq j}C(S-\{j\},i)+dij$

Pseudocódigo:

Os problemas são ordenados por |S|:

   C({1},1) = 0:
   Para s = 2 até n:
           Para todos os subconjuntos S $\subseteq$ {1,2,...,n} de tamanho s e contendo 1:
               C(S,1) = $\infty$:
               Para todo j $\in$ S, i $\neq$ j:
                      C(S,j) = min{C(S - {j},i) + d$_{ij}$: i $\in$ S, i $\neq$ j}
   Retornar min$_{j}$ C({1,...,n},j) + d$_{ij}$

Referências gerais

• APPLEGATE, David L. [et al.] – The travelling salesman problem: a computational Study. Princeton: Princeton University Press, 2006. ISBN 978-0-691-12993-8
• BäCK, Thomas – Evolutionary algorithms in theory and practice. New York: Oxford University Press, 1996. ISBN 978-0-195-09971-3
• CONWAY, Richard Walter; MAXWELL, William L.; MILLER, Louis W. – Theory of scheduling. Reading, [Mass]: Edição de Courier Dover Publications, 2003. ISBN 978-0-486-42817-8
• COSTA, Fredson Vieira; VIDAL, Fábio Silveira; ANDRÉ, Claudomiro Moura Gomes – SLAG – Resolvendo o problema do caixeiro viajante utilizando algoritmos genéticos [Em Linha]. Tocantins [Brasil]: Sistemas e Computação - Pós-Graduação, 2003. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.de9.ime.eb.br/~fsvidal/trabpub/slag.pdf>
• CUNHA, Claudio Barbieri da; BONASSER, Ulisses de Oliveira; ABRAHÃO, Fernando Teixeira Mendes – Experimentos computacionais com heurísticas de melhorias para o problema do caixeiro viajante [Em Linha]. São Paulo: ANPET, 2002. [Consult. 13 Abr. 2009]. Disponível em WWW: <URL:http://www.ptr.poli.usp.br/ptr/docentes/cbcunha/files/2-opt_TSP_Anpet_2002_CBC.pdf>
• GUEDES, Allison da Costa Neves; LEITE, Jéssica Neiva de Figueiredo; ALOISE, Dário José – Um algoritmo genético com infecção viral para o problema do caixeiro viajante [Em Linha]. Natal [Brasil]: Revista On Line de Iniciação Científica, 2005. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.propesq.ufrn.br/publica/artigos-1edicao/et/MSIC-ET-011.pdf>
• GOODRICH, Michael T.; TAMASSIA, Roberto – Estruturas de Dados E Algoritmos Em Java . 4ª ed.. São Paulo: Edição de Bookman, 1899. ISBN 978-0-471-73884-8
• HOFFMAN, Karla; PADBERG, Manfred – Traveling salesman problem [Em Linha]. Fairfax [Virgínia]: Department of Electrical and Computer Engineering - George Mason University, 2000. [Consult. 13 Abr. 2009]. Disponível em WWW: <URL: http://iris.gmu.edu/~khoffman/papers/trav_salesman.html>
• NILSSON, Nils J. – Principals of artificial intelligence. New York: edição de Birkhauser, 1982. ISBN 978-3-540-11340-9
• OCHI, Luiz Satoru – Algoritmos genéticos: origem e evolução [Em Linha]. São Paulo: Sociedade Brasileira de Matemática Aplicada e Computacional, 1998. [Consult. 18 Abr. 2009]. Disponível em WWW: <URL:http://www.sbmac.org.br/bol/bol-2/artigos/satoru/satoru.html#caixeiro>
• SIQUEIRA, Paulo Henrique; STEINER, Maria Teresinha Arns; SCHEER, Sérgio – A new approach to solve the traveling salesman problem [Em Linha]. Amsterdam: ScienceDirect - Neurocomputing: A new approach to solve the traveling salesman problem, 2006. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:http://www.sciencedirect.com/science?_ob=ArticleURL&_udi=B6V10-4M7CMDB-1&_user=2975255&_rdoc=1&_fmt=&_orig=search&_sort=d&view=c&_acct=C000057395&_version=1&_urlVersion=0&_userid=2975255&md5=c0e8406e94b63d03d280bac5311d805e>
• STÜTZLE, Thomas; DORIGO, Marco – ACO Algorithms for the traveling salesman problem [Em Linha]. New York: Swarm Intelligence Resources, 1999. [Consult. 17 Abr. 2009]. Disponível em WWW: <URL:http://staff.washington.edu/paymana/swarm/stutzle99-eaecs.pdf>

Bibliografia

• CERVIERI, Alexandre; PY, Mónica – Algoritmo para a resolução do problema do caixeiro viajante [Em Linha]. Porto Alegre: Instituto de Informática - UFRGS, 2000. [Consult. 15 Abr. 2009]. Disponível em WWW: <URL:https://web.archive.org/web/20040926043051/http://www.inf.ufrgs.br/procpar/disc/cmp134/trabs/T2/001/mpisalesman/mpisalesman.pdf>
• REEVES, Colin R., ed. – Modern heuristic techniques for combinatorial problems. Ed. Colin R. Reeves. London: McGraw-Hill Book, 2000. XIII, 320 p..( Advanced Topic in Computer Science). ISBN 978-0-077-09239-9
• LAWLER, Eugène L.; RINNOOY-KAN, A. H. G.; LENSTRA, Jan Karel; SHMOYS, David B. – The Traveling salesman problem: a guided tour of combinatorial optimization. [S.l.]: Edição de Wiley, 1985. ISBN 978-0-471-90413-7

Ver também

• Algoritmo simplex
• Problema de roteamento de veículos
• Problema da mochila
• Problema do caminho mínimo
• Caminho hamiltoniano
• Sete pontes de Königsberg

Ligações externas

• «TSPLIB» (em inglês) 
• «TSP» (em inglês) 
• «Vida e obras de Hamilton» (em inglês)