Problema do caixeiro viajante

O problema do caixeiro viajante (TSP) faz a seguinte pergunta: "Dada uma lista de cidades e as distâncias entre cada par de cidades, qual é a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade de origem?" É um problema NP-difícil em otimização combinatória, importante na ciência da computação teórica e na pesquisa operacional.

O problema do comprador viajante e o problema de roteamento de veículos são generalizações do TSP.

Na teoria da complexidade computacional, a versão de decisão do TSP (onde dado um comprimento L, a tarefa é decidir se o gráfico tem um percurso de no máximo L) pertence à classe dos problemas NP-completos. Assim, é possível que o tempo de execução do pior caso para qualquer algoritmo do TSP aumente superpolinomialmente (mas não mais que exponencialmente) com o número de cidades.

O problema foi formulado pela primeira vez em 1930 e é um dos problemas mais intensamente estudados em otimização. É usado como referência para muitos métodos de otimização. Embora o problema seja computacionalmente difícil, muitas heurísticas e algoritmos exatos são conhecidos, de modo que algumas instâncias com dezenas de milhares de cidades podem ser completamente resolvidas e até mesmo problemas com milhões de cidades podem ser aproximados dentro de uma pequena fração de 1%.

O TSP tem diversas aplicações mesmo em sua formulação mais pura, como planejamento, logística e fabricação de microchips. Ligeiramente modificado, aparece como um subproblema em muitas áreas, como no sequenciamento de DNA. Nessas aplicações, o conceito cidade representa, por exemplo, clientes, pontos de solda ou fragmentos de DNA, e o conceito distância representa tempos ou custos de viagem, ou uma medida de similaridade entre Fragmentos de DNA. O TSP também aparece na astronomia, pois os astrônomos que observam muitas fontes desejarão minimizar o tempo gasto movendo o telescópio entre as fontes; nesses problemas, o TSP pode ser incorporado em um problema de controle ótimo. Em muitas aplicações, podem ser impostas restrições adicionais, como recursos limitados ou janelas de tempo.

Histórico

As origens do problema do caixeiro viajante não são claras. Um manual para caixeiros viajantes de 1832 menciona o problema e inclui exemplos de passeios pela Alemanha e Suíça, mas não contém nenhum tratamento matemático.

O TSP foi formulado matematicamente no século XIX pelo matemático irlandês William Rowan Hamilton e pelo matemático britânico Thomas Kirkman. O jogo icosiano de Hamilton era um quebra-cabeça recreativo baseado na descoberta de um ciclo hamiltoniano. A forma geral do TSP parece ter sido estudada pela primeira vez por matemáticos durante a década de 1930 em Viena e em Harvard, nomeadamente por Karl Menger, que define o problema, considera o algoritmo de força bruta óbvio e observa a não otimização do mais próximo. heurística vizinha:

Nós denotamos problema do mensageiro (uma vez que na prática esta questão deve ser resolvida por cada postman, de qualquer maneira também por muitos viajantes) a tarefa de encontrar, para finitamente muitos pontos cujas distâncias pares são conhecidas, a rota mais curta conectando os pontos. Naturalmente, este problema é solvável por muitas tentativas finitas. Regras que empurram o número de julgamentos abaixo do número de permutações dos pontos dados, não são conhecidas. A regra de que um primeiro deve ir do ponto de partida para o ponto mais próximo, então ao ponto mais próximo disso, etc., em geral não cede a rota mais curta.

Foi considerado matematicamente pela primeira vez na década de 1930 por Merrill M. Flood, que procurava resolver um problema de roteamento de ônibus escolar. Hassler Whitney, da Universidade de Princeton, gerou interesse no problema, que ele chamou de “problema dos 48 estados”. A publicação mais antiga usando a frase "problema do caixeiro viajante [ou viajante]' foi o relatório da RAND Corporation de 1949, de Julia Robinson, “Sobre o jogo hamiltoniano (um problema do caixeiro viajante”).

Nas décadas de 1950 e 1960, o problema tornou-se cada vez mais popular nos círculos científicos da Europa e dos Estados Unidos depois que a RAND Corporation em Santa Monica ofereceu prêmios pelas etapas de solução do problema. Contribuições notáveis foram feitas por George Dantzig, Delbert Ray Fulkerson e Selmer M. Johnson da RAND Corporation, que expressaram o problema como um programa linear inteiro e desenvolveram o método do plano de corte para sua solução. Eles escreveram o que é considerado o artigo seminal sobre o assunto, no qual, com esses novos métodos, resolveram uma instância com 49 cidades até a otimização, construindo um tour e provando que nenhum outro tour poderia ser mais curto. Dantzig, Fulkerson e Johnson, no entanto, especularam que, dada uma solução quase ótima, poderíamos ser capazes de encontrar a otimização ou provar a otimização adicionando um pequeno número de desigualdades extras (cortes). Eles usaram essa ideia para resolver seu problema inicial de 49 cidades usando um modelo de cordas. Eles descobriram que precisavam apenas de 26 cortes para encontrar uma solução para o problema das 49 cidades. Embora este artigo não fornecesse uma abordagem algorítmica para problemas de TSP, as ideias contidas nele eram indispensáveis para a criação posterior de métodos de solução exatos para o TSP, embora levasse 15 anos para encontrar uma abordagem algorítmica na criação desses cortes. Além dos métodos de plano de corte, Dantzig, Fulkerson e Johnson usaram algoritmos de ramificação e limite, talvez pela primeira vez.

Em 1959, Jillian Beardwood, J.H. Halton e John Hammersley publicaram um artigo intitulado "O caminho mais curto através de muitos pontos" no jornal da Cambridge Philosophical Society. O teorema de Beardwood-Halton-Hammersley fornece uma solução prática para o problema do caixeiro viajante. Os autores derivaram uma fórmula assintótica para determinar o comprimento do caminho mais curto para um vendedor que começa em uma casa ou escritório e visita um número fixo de locais antes de retornar ao ponto inicial.

Nas décadas seguintes, o problema foi estudado por muitos pesquisadores de matemática, ciência da computação, química, física e outras ciências. Na década de 1960, entretanto, foi criada uma nova abordagem que, em vez de buscar soluções ótimas, produziria uma solução cujo comprimento fosse comprovadamente limitado por um múltiplo do comprimento ideal e, ao fazê-lo, criaria limites inferiores para o problema; esses limites inferiores seriam então usados com abordagens de ramificação e limite. Um método para fazer isso foi criar uma árvore geradora mínima do grafo e depois duplicar todas as suas arestas, o que produz o limite de que o comprimento de um percurso ideal é no máximo duas vezes o peso de uma árvore geradora mínima.

Em 1976, Christofides e Serdyukov, independentemente um do outro, fizeram um grande avanço nessa direção: o algoritmo Christofides-Serdyukov produz uma solução que, no pior dos casos, é no máximo 1,5 vezes mais longa que a solução ótima. Como o algoritmo era simples e rápido, muitos esperavam que ele desse lugar a um método de solução quase ideal. No entanto, esta esperança de melhoria não se concretizou imediatamente, e Christofides-Serdyukov permaneceu como o método com o melhor cenário de pior caso até 2011, quando um algoritmo de aproximação (muito) ligeiramente melhorado foi desenvolvido para o subconjunto de dados "gráficos&#34.; TSPs. Em 2020, esta pequena melhoria foi estendida ao TSP completo (métrico).

Richard M. Karp mostrou em 1972 que o problema do ciclo hamiltoniano era NP-completo, o que implica a dureza NP do TSP. Isto forneceu uma explicação matemática para a aparente dificuldade computacional de encontrar passeios ideais.

Grande progresso foi feito no final da década de 1970 e 1980, quando Grötschel, Padberg, Rinaldi e outros conseguiram resolver com exatidão instâncias com até 2.392 cidades, usando aviões de corte e branch-and-bound.

Na década de 1990, Applegate, Bixby, Chvátal e Cook desenvolveram o programa Concorde que tem sido usado em muitas soluções de gravação recentes. Gerhard Reinelt publicou o TSPLIB em 1991, uma coleção de exemplos de referência de dificuldade variada, que tem sido usada por muitos grupos de pesquisa para comparar resultados. Em 2006, Cook e outros calcularam um percurso ideal através de uma instância de 85.900 cidades dada por um problema de layout de microchip, atualmente a maior instância TSPLIB resolvida. Para muitos outros casos com milhões de cidades, podem ser encontradas soluções que garantem estar dentro de 2 a 3% de um percurso ideal.

Descrição

Como um problema gráfico

O TSP pode ser modelado como um grafo ponderado não direcionado, de modo que as cidades são os vértices do grafo, os caminhos são as arestas do grafo e a distância de um caminho é a aresta. peso. É um problema de minimização que começa e termina em um vértice especificado após terem visitado cada um dos outros vértices exatamente uma vez. Freqüentemente, o modelo é um grafo completo (ou seja, cada par de vértices é conectado por uma aresta). Se não existir nenhum caminho entre duas cidades, adicionar uma aresta suficientemente longa completará o gráfico sem afetar o percurso ideal.

Assimétrico e simétrico

No TSP simétrico, a distância entre duas cidades é a mesma em cada direção oposta, formando um gráfico não direcionado. Essa simetria reduz pela metade o número de soluções possíveis. No TSP assimétrico, os caminhos podem não existir em ambas as direções ou as distâncias podem ser diferentes, formando um grafo direcionado. Colisões de trânsito, ruas de mão única e tarifas aéreas para cidades com taxas de partida e chegada diferentes são exemplos de como essa simetria pode ser quebrada.

Problemas relacionados

• Uma formulação equivalente em termos de teoria dos grafos é: Dado um grafo ponderado completo (onde os vértices representariam as cidades, as bordas representariam as estradas, e os pesos seriam o custo ou distância dessa estrada), encontrar um ciclo Hamiltoniano com o menor peso.
• A exigência de retornar à cidade inicial não muda a complexidade computacional do problema, veja o problema do caminho Hamiltoniano.
• Outro problema relacionado é o problema do vendedor de viagem gargalo (tSP de bottleneck): Encontre um ciclo Hamiltoniano em um grafo ponderado com o peso mínimo da borda mais pesada. Por exemplo, evitando ruas estreitas com grandes ônibus. O problema é de considerável importância prática, além de áreas de transporte e logística evidentes. Um exemplo clássico está na fabricação de circuitos impressos: agendamento de uma rota da máquina de perfuração para furos em um PCB. Em aplicações de usinagem ou perfuração robótica, as "cidades" são peças para máquinas ou furos (de diferentes tamanhos) para perfurar, e o "custo de viagem" inclui tempo para reequilibrar o robô (problema de sequenciamento de trabalho de máquina única).
• O problema generalizado do vendedor, também conhecido como o "problema político viajante", lida com "estados" que têm (um ou mais) "cidades" e o vendedor tem que visitar exatamente uma "cidade" de cada "estado". Uma aplicação é encontrada para ordenar uma solução para o problema de estoque de corte, a fim de minimizar as mudanças de faca. Outro está preocupado com a perfuração na fabricação de semicondutores, ver por exemplo, EUA Patente 7,054,798. Noon e Bean demonstraram que o problema de vendedor de viagens generalizada pode ser transformado em um TSP padrão com o mesmo número de cidades, mas uma matriz de distância modificada.
• O problema de ordenação sequencial lida com o problema de visitar um conjunto de cidades onde existem relações de precedência entre as cidades.
• Uma questão de entrevista comum no Google é como direcionar dados entre nós de processamento de dados; rotas variam por tempo para transferir os dados, mas nós também diferem por seu poder de computação e armazenamento, agravando o problema de onde enviar dados.
• O problema do comprador viajante lida com um comprador que é cobrado com a compra de um conjunto de produtos. Ele pode comprar esses produtos em várias cidades, mas a preços diferentes e nem todas as cidades oferecem os mesmos produtos. O objetivo é encontrar uma rota entre um subconjunto das cidades que minimiza o custo total (custo de viagem + custo de compra) e permite a compra de todos os produtos necessários.

Formulações de programação linear inteira

O TSP pode ser formulado como um programa linear inteiro. São conhecidas diversas formulações. Duas formulações notáveis são a formulação Miller – Tucker – Zemlin (MTZ) e a formulação Dantzig – Fulkerson – Johnson (DFJ). A formulação DFJ é mais forte, embora a formulação MTZ ainda seja útil em determinados contextos.

Comum a ambas as formulações é que se rotula as cidades com os números 1,...... ,nNão. e leva 0}" xmlns="http://www.w3.org/1998/Math/MathML">cEu...JJ>0{displaystyle c_{ij}>0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2d754e494ca2548ccbf2dc5613444c9d28d6039" style="vertical-align: -1.005ex; width:6.745ex; height:2.843ex;"/> para ser o custo (distância) da cidade Eu...Não. cidade JJNão.. As principais variáveis nas formulações são:

xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1o caminho vai da cidadeEu...cidadeJJ0caso contrárioNão. x_{ij}={begin{cases}1&{text{the path goes from city }}i{text{ to city }}j&{text{otherwise}}end{cases}}}

É por serem variáveis 0/1 que as formulações se tornam programas inteiros; todas as outras restrições são puramente lineares. Em particular, o objectivo do programa é

minimizar o comprimento da turnê Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nGerenciamento Gerenciamento JJ≠ ≠ Eu...,JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1ncEu...JJxEu...JJ{displaystyle sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}}.

Sem restrições adicionais, o (xEu...JJ?Eu...,JJNão. {x_{ij}}_{i,j}} Contudo efetivamente variar sobre todos os subconjuntos do conjunto de bordas, que está muito longe dos conjuntos de bordas em um passeio, e permite um mínimo trivial onde todos xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0- Sim.. Portanto, ambas as formulações também têm as restrições que lá em cada vértice é exatamente uma borda de entrada e uma borda de saída, que pode ser expressa como o 2nNão. equações lineares

Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,Eu...≠ ≠ JJnxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle sum _{i=1,ineq j}^{n}x_{ij}=1} para JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,nNão. e Gerenciamento Gerenciamento JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,JJ≠ ≠ Eu...nxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle sum _{j=1,jneq Eu sei. para Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n- Sim..

Isso garante que o conjunto de arestas escolhido localmente se pareça com o de um passeio, mas ainda permite soluções que violam o requisito global de que haja um passeio que visite todos os vértices, já que as arestas escolhidas poderiam faça vários passeios, cada um visitando apenas um subconjunto dos vértices; sem dúvida é este requisito global que torna o TSP um problema difícil. As formulações MTZ e DFJ diferem na forma como expressam este requisito final como restrições lineares.

Formulação de Miller-Tucker-Zemlin

Além do xEu...JJ{displaystyle x_{ij}} variáveis como acima, há para cada Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2,...... ,n- Sim. uma variável fictícia uEu...Não. u_{i}} que mantém o controle da ordem em que as cidades são visitadas, contando da cidade 1Não. 1; a interpretação é que <math alttext="{displaystyle u_{i}uEu...<uJJNão. u_{i}<u_{j}}<img alt="{displaystyle u_{i} implica cidade Eu...Não. é visitada antes da cidade JJNão.. Para um determinado passeio (como codificado em valores do xEu...JJ{displaystyle x_{ij}} variáveis), pode-se encontrar valores satisfatórios para o uEu...Não. u_{i}} variáveis fazendo uEu...Não. u_{i}} igual ao número de arestas ao longo dessa excursão, quando vai da cidade 1Não. 1 cidade Eu...Não..

Porque a programação linear favorece desigualdades não restritas (≥ ≥ - Sim.) sobre estrito (}" xmlns="http://www.w3.org/1998/Math/MathML">>Não. " aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1b27b77ab4e3293ea9ce65cef60fea655c398423" style="vertical-align: -0.338ex; width:1.808ex; height:1.843ex;"/>), gostaríamos de impor restrições ao efeito de que

uJJ≥ ≥ uEu...+1{displaystyle u_{j}geq} - Sim. se xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle x_{ij}=1}.

Apenas exigindo uJJ≥ ≥ uEu...+xEu...JJ{displaystyle u_{j}geq} u_{i}+x_{ij}} se não alcançar isso, porque isso também requer uJJ≥ ≥ uEu...{displaystyle u_{j}geq u_{i}} quando xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0- Sim., que não está correto. Em vez disso MTZ usar o (n- Sim. - Sim. 1)(n- Sim. - Sim. 2)(n-1)(n-2)} restrições lineares

uJJ+(n- Sim. - Sim. 2)≥ ≥ uEu...+(n- Sim. - Sim. 1)xEu...JJ(n-2)geq u_{i}+(n-1)x_{ij}} para todos os distintos Eu...,JJ∈ ∈ (2,...... ,n?{displaystyle i,jin {2,dotscn}}

onde o termo constante n- Sim. - Sim. 2Não. fornece slack suficiente que xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0- Sim. não impõe uma relação entre uJJ{displaystyle u_{j}} e uEu...Não. u_{i}}.

A forma como uEu...Não. u_{i}} variáveis então impõem que uma única turnê visita todas as cidades é que elas aumentam (pelo menos) 1Não. 1 para cada passo ao longo de um passeio, com uma diminuição apenas permitida onde o passeio passa pela cidade1Não. 1. Essa restrição seria violada por cada turnê que não passa pela cidade1Não. 1, então a única maneira de satisfazê-lo é que o passeio passando a cidade1Não. 1 também passa por todas as outras cidades.

A formulação MTZ do TSP é, portanto, o seguinte problema de programação linear inteira:

minGerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nGerenciamento Gerenciamento JJ≠ ≠ Eu...,JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1ncEu...JJxEu...JJ:: xEu...JJ∈ ∈ (0,1?Eu...,JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n;uEu...∈ ∈ Z.Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2,...... ,n;Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,Eu...≠ ≠ JJnxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n;Gerenciamento Gerenciamento JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,JJ≠ ≠ Eu...nxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n;uEu...- Sim. - Sim. uJJ+(n- Sim. - Sim. 1)xEu...JJ≤ ≤ n- Sim. - Sim. 22≤ ≤ Eu...≠ ≠ JJ≤ ≤ n;2≤ ≤ uEu...≤ ≤ n2≤ ≤ Eu...≤ ≤ n.{displaystyle {begin{aligned}min sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}&colon &&x_{ij}in {}&{0,1}&i,j=1,ldotsn\u_{i}in {}&mathbf {Z} &i=2,ldot _{i=1,ineq j}^{n}x_{ij}={}&1&&j=1,ldotsn;\sum _{j=1,jneq i}^{n}x_{ij}={}&1&&i=1,ldotsn;u_{i}-u_{j}+(n-1)x_{ij}leq {}&n-2&2leq ineq jleq n;2leq u_{i}leq {}&n&&2leq ileq n.end{aligned}}}

O primeiro conjunto de equalidades exige que cada cidade é chegada a partir de exatamente uma outra cidade, e o segundo conjunto de equalidades exige que de cada cidade há uma partida para exatamente uma outra cidade. Os últimos constrangimentos impõem que há apenas um único passeio cobrindo todas as cidades, e não dois ou mais passeios disjuntos que apenas cobrem coletivamente todas as cidades. Para provar isso, é mostrado abaixo (1) que cada solução viável contém apenas uma seqüência fechada de cidades, e (2) que para cada turnê cobrindo todas as cidades, há valores para as variáveis fictícias uEu...Não. u_{i}} que satisfazem as restrições.

Para provar que cada solução viável contém apenas uma seqüência fechada de cidades, basta mostrar que cada subtour em uma solução viável passa pela cidade 1 (desde que a igualdade assegure que só pode haver uma dessas turnês). Pois se resumirmos todas as desigualdades correspondentes a xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle x_{ij}=1} para qualquer subtour de k passos não passando pela cidade 1, obtemos:

(n- Sim. - Sim. 1)k≤ ≤ (n- Sim. - Sim. 2)k,(n-1)kleq (n-2)k,}

o que é uma contradição.

Agora deve ser mostrado que para cada turnê que cobre todas as cidades, há valores para as variáveis fictícias uEu...Não. u_{i}} que satisfazem as restrições.

Sem perda de generalidade, defina o passeio como originário (e final) na cidade 1. Escolha uEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =)Não. Não. se cidade Eu...Não. é visitado no passo )(Eu...,)= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =2,3,...... ,n)(i,t=2,3,ldotsn)}. Então...

uEu...- Sim. - Sim. uJJ≤ ≤ n- Sim. - Sim. 2,Não. u_{i}-u_{j}leq n-2,}

desde então uEu...Não. u_{i}} não pode ser maior do que nNão. e uJJ{displaystyle u_{j}} pode ser não menos do que 2; daí as restrições são satisfeitas sempre que xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =0.{displaystyle x_{ij}=0.} Para xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1{displaystyle x_{ij}=1}, temos:

uEu...- Sim. - Sim. uJJ+(n- Sim. - Sim. 1)xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =())- Sim. - Sim. ()+1)+n- Sim. - Sim. 1= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =n- Sim. - Sim. 2,Não. u_{i}-u_{j}+(n-1)x_{ij}=(t)-(t+1)+n-1=n-2,}

satisfazendo a restrição.

Formulação de Dantzig–Fulkerson–Johnson

Rotule as cidades com os números 1,…, n e defina:

xEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =(1o caminho vai da cidadeEu...cidadeJJ0caso contrárioNão. x_{ij}={begin{cases}1&{text{the path goes from city }}i{text{ to city }}j&{text{otherwise}}end{cases}}}

Toma. 0}" xmlns="http://www.w3.org/1998/Math/MathML">cEu...JJ>0{displaystyle c_{ij}>0}0}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d2d754e494ca2548ccbf2dc5613444c9d28d6039" style="vertical-align: -1.005ex; width:6.745ex; height:2.843ex;"/> para ser a distância da cidade Eu... cidade JJ. Então o TSP pode ser escrito como o seguinte problema de programação linear inteiro:

minGerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1nGerenciamento Gerenciamento JJ≠ ≠ Eu...,JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1ncEu...JJxEu...JJ:: Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,Eu...≠ ≠ JJnxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n;Gerenciamento Gerenciamento JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,JJ≠ ≠ Eu...nxEu...JJ= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1,...... ,n;Gerenciamento Gerenciamento Eu...∈ ∈ QGerenciamento Gerenciamento JJ≠ ≠ Eu...,JJ∈ ∈ QxEu...JJ≤ ≤ |Q|- Sim. - Sim. 1Gerenciamento de contas Gerenciamento de contas Q⊊ ⊊ (1,...... ,n?,|Q|≥ ≥ 2{displaystyle {begin{aligned}min &sum _{i=1}^{n}sum _{jneq i,j=1}^{n}c_{ij}x_{ij}colon &&&\um _{i=1,ineq j}^{n}x_{ij}=1&&j=1,ldotsn;&sum _{j=1,jneq i}^{n}x_{ij}=1&&i=1,ldotsn;&sum _{iin Q}{sum _{jneq i,jin Q}{x_{ij}}}leq |Q|-1&forall Qsubsetneq {1,ldotsn},|Q|geq 2\end{aligned}}}

A última restrição da formulação DFJ - chamada de restrição de eliminação de subtour - garante que nenhum subconjunto adequado Q possa formar um subtour, de modo que a solução retornada é um único tour e não a união de circuitos menores. passeios. Como isso leva a um número exponencial de restrições possíveis, na prática é resolvido com a geração de linhas.

Calculando uma solução

As linhas tradicionais de ataque para problemas NP-difíceis são as seguintes:

• Desenvolvendo algoritmos exatos, que funcionam razoavelmente rápido apenas para pequenos tamanhos de problemas.
• Desenvolvendo algoritmos "suboptimal" ou heurística, ou seja, algoritmos que oferecem soluções aproximadas em um tempo razoável.
• Encontrando casos especiais para o problema ("subproblemas") para os quais são possíveis heurísticas melhores ou exatas.

Algoritmos exatos

A solução mais direta seria tentar todas as permutações (combinações ordenadas) e ver qual delas é mais barata (usando busca por força bruta). O tempo de execução para esta abordagem está dentro de um fator polinomial O(n!)O(n)}, o factorial do número de cidades, então esta solução torna-se impraticável mesmo para apenas 20 cidades.

Uma das primeiras aplicações da programação dinâmica é o algoritmo Held-Karp que resolve o problema no tempo O(n22n)(n^{2}2^{n})}. Este limite também foi alcançado pela Exclusão-Inclusão em uma tentativa anterior à abordagem de programação dinâmica.

Melhorar estes limites de tempo parece ser difícil. Por exemplo, não foi determinado se um algoritmo exato clássico para TSP que é executado no tempo O(1.99n)(em inglês) ? existe. O melhor algoritmo exato quântico atualmente para TSP devido a Ambainis et al. corre no tempo O(1.728n)(1.728^{n})}.

Outras abordagens incluem:

• Vários algoritmos ramificados, que podem ser usados para processar TSPs contendo 40–60 cidades.

• Algoritmos de melhoria progressiva que usam técnicas reminiscentes de programação linear. Funciona bem para até 200 cidades.
• Implementações de geração de corte específica de ramo e problema (branch-and-cut); este é o método de escolha para resolver grandes instâncias. Esta abordagem contém o registro atual, resolvendo uma instância com 85.900 cidades, veja Applegate et al. (2006).

Uma solução exata para 15.112 cidades alemãs do TSPLIB foi encontrada em 2001 usando o método do plano de corte proposto por George Dantzig, Ray Fulkerson e Selmer M. Johnson em 1954, baseado em programação linear. Os cálculos foram realizados em uma rede de 110 processadores localizados na Rice University e na Princeton University. O tempo total de computação foi equivalente a 22,6 anos em um único processador Alpha de 500 MHz. Em maio de 2004, o problema do caixeiro viajante de visitar todas as 24.978 cidades da Suécia foi resolvido: foi encontrado um passeio com aproximadamente 72.500 quilômetros e ficou provado que não existe um passeio mais curto. Em março de 2005, o problema do caixeiro viajante de visitar todos os 33.810 pontos em uma placa de circuito foi resolvido usando o Concorde TSP Solver: foi encontrado um tour com 66.048.945 unidades e ficou comprovado que não existe um tour mais curto. O cálculo levou aproximadamente 15,7 anos de CPU (Cook et al. 2006). Em abril de 2006, uma instância com 85.900 pontos foi resolvida usando o Concorde TSP Solver, consumindo mais de 136 anos de CPU, veja Applegate et al. (2006).

Algoritmos heurísticos e de aproximação

Várias heurísticas e algoritmos de aproximação, que rapidamente produzem boas soluções, foram desenvolvidos. Isso inclui o algoritmo multifragmento. Os métodos modernos podem encontrar soluções para problemas extremamente grandes (milhões de cidades) dentro de um tempo razoável, que estão, com alta probabilidade, a apenas 2–3% da solução ideal.

Várias categorias de heurísticas são reconhecidas.

Heurísticas construtivas

O algoritmo vizinho mais próximo (NN) (um algoritmo ganancioso) permite que o vendedor escolha a cidade não visitada mais próxima como seu próximo movimento. Este algoritmo produz rapidamente uma rota eficazmente curta. Para cidades N distribuídas aleatoriamente em um avião, o algoritmo em média produz um caminho 25% mais longo do que o caminho mais curto possível. No entanto, existem muitas distribuições de cidade especialmente organizadas que fazem o algoritmo NN dar a pior rota. Isso é verdade para TSPs assimétricos e simétricos. Rosenkrantz et al. mostrou que o algoritmo NN tem o fator de aproximação Θ Θ (log⁡ ⁡ |V|)Não. Theta (log |V|)} por exemplo, satisfazendo a desigualdade de triângulo. Uma variação do algoritmo NN, chamado de fragmento mais próximo (NF), que conecta um grupo (fragmento) de cidades não visitadas mais próximas, pode encontrar rotas mais curtas com sucessivas iterações. O operador NF também pode ser aplicado em uma solução inicial obtida pelo algoritmo NN para melhoria adicional em um modelo elitista, onde apenas soluções melhores são aceitas.

O passeio bitônico de um conjunto de pontos é o polígono monótono de perímetro mínimo que tem os pontos como vértices; pode ser calculado de forma eficiente por programação dinâmica.

Outra heurística construtiva, Match Twice and Stitch (MTS), realiza duas correspondências sequenciais, onde a segunda correspondência é executada após a exclusão de todas as arestas da primeira correspondência, para produzir um conjunto de ciclos. Os ciclos são então costurados para produzir o passeio final.

O Algoritmo de Christofides e Serdyukov

O algoritmo de Christofides e Serdyukov segue um esquema semelhante, mas combina a árvore geradora mínima com uma solução de outro problema, a correspondência perfeita de peso mínimo. Isto proporciona um tour TSP que é no máximo 1,5 vezes o ideal. Foi um dos primeiros algoritmos de aproximação e foi em parte responsável por chamar a atenção para algoritmos de aproximação como uma abordagem prática para problemas intratáveis. Na verdade, o termo "algoritmo" não foi comumente estendido a algoritmos de aproximação até mais tarde; o algoritmo Christofides foi inicialmente referido como heurística Christofides.

Este algoritmo olha para as coisas de forma diferente usando um resultado da teoria dos grafos que ajuda a melhorar no limite inferior do TSP que se originou da duplicação do custo da árvore de exploração mínima. Dado um grafo euleriano podemos encontrar uma excursão euleriana em O(n)O(n)} Hora. Então, se tivéssemos um gráfico euleriano com cidades de um TSP como vértices, então podemos facilmente ver que poderíamos usar tal método para encontrar um tour euleriano para encontrar uma solução TSP. Por desigualdade triangular, sabemos que a turnê TSP não pode ser mais do que a turnê Eulerian e, como tal, temos um limite inferior para o TSP. Tal método é descrito abaixo.

1. Encontre uma árvore de spanning mínima para o problema
2. Criar duplicatas para cada borda para criar um gráfico euleriano
3. Encontre uma excursão Eulerian para este gráfico
4. Converta para TSP: se uma cidade é visitada duas vezes, crie um atalho da cidade antes disso na excursão para a uma após isso.

Para melhorar o limite inferior, é necessária uma forma melhor de criar um grafo euleriano. Por desigualdade triangular, o melhor grafo euleriano deve ter o mesmo custo que a melhor turnê de vendedor itinerante, portanto, encontrar gráficos eulerianos ideais é pelo menos tão difícil quanto o TSP. Uma maneira de fazer isso é por correspondência de peso mínimo usando algoritmos de O(n3)(n^{3})}.

Transformar um gráfico em um gráfico Euleriano começa com a árvore geradora mínima. Então todos os vértices de ordem ímpar devem ser pares. Portanto, uma correspondência para os vértices de graus ímpares deve ser adicionada, o que aumenta a ordem de cada vértice de grau ímpar em um. Isso nos deixa com um gráfico onde cada vértice é de ordem par e, portanto, euleriano. A adaptação do método acima fornece o algoritmo de Christofides e Serdyukov.

1. Encontre uma árvore de spanning mínima para o problema
2. Crie uma correspondência para o problema com o conjunto de cidades de ordem estranha.
3. Encontre uma excursão Eulerian para este gráfico
4. Converta para TSP usando atalhos.

Troca em pares

A troca de pares ou técnica 2-opt envolve a remoção iterativa de duas arestas e sua substituição por duas arestas diferentes que reconectam os fragmentos criados pela remoção das arestas em um passeio novo e mais curto. Da mesma forma, a técnica 3-opt remove 3 arestas e as reconecta para formar um tour mais curto. Estes são casos especiais do método k. O rótulo Lin–Kernighan é um nome impróprio frequentemente ouvido para 2-opt. Lin – Kernighan é na verdade o método k-opt mais geral.

Para as instâncias euclidianas, as heurísticas de 2 pontos oferecem soluções médias que são cerca de 5% melhores do que o algoritmo de Christofides. Se começarmos com uma solução inicial feita com um algoritmo ganancioso, o número médio de movimentos diminui muito e é O(n)O(n)}. Para partidas aleatórias no entanto, o número médio de movimentos é O(nlog⁡ ⁡ (n))(nlog(n)}. No entanto, enquanto em ordem este é um pequeno aumento no tamanho, o número inicial de movimentos para pequenos problemas é 10 vezes maior para um início aleatório em comparação com um feito de uma heurística gananciosa. Isto porque tais heurísticas 2-opt exploram partes "maus" de uma solução como cruzamentos. Estes tipos de heurística são frequentemente usados dentro do problema de roteamento de veículos heurísticas para reotimizar soluções de rota.

Heurística K-opt ou heurística Lin-Kernighan

A heurística Lin-Kernighan é um caso especial da técnica V ou opção variável. Envolve as seguintes etapas:

1. Dado um passeio, excluir k bordas mutuamente disjuntas.
2. Remontar os fragmentos restantes em uma excursão, não deixando subtours disjuntos (isto é, não conecte os terminais de um fragmento juntos). Isso simplifica o TSP em consideração em um problema muito mais simples.
3. Cada ponto final do fragmento pode ser conectado a 2k- 2 outras possibilidades: de 2k pontos finais de fragmento total disponíveis, os dois pontos finais do fragmento em consideração são desalvados. Tal constrangido 2k-city TSP pode então ser resolvido com métodos de força bruta para encontrar a recombinação de menor custo dos fragmentos originais.

O mais popular dos métodos k-opt é o 3-opt, introduzido por Shen Lin do Bell Labs em 1965. Um caso especial de 3-opt é onde as arestas não são disjuntas (duas das arestas são adjacentes uma à outra). Na prática, muitas vezes é possível obter melhorias substanciais em relação ao 2-opt sem o custo combinatório do 3-opt geral, restringindo as 3-alterações a este subconjunto especial onde duas das arestas removidas são adjacentes. Essa chamada opção de duas opções e meia normalmente fica aproximadamente no meio do caminho entre 2 opções e 3 opções, tanto em termos da qualidade dos passeios alcançados quanto do tempo necessário para realizá-los.

Heurística V-opt

O método variável-opt está relacionado e é uma generalização do método k-opt. Enquanto os métodos k-opt removem um número fixo (k) de arestas do tour original, os métodos de opção variável não fixam o tamanho da aresta definida para remover. Em vez disso, eles aumentam o conjunto à medida que o processo de busca continua. O método mais conhecido nesta família é o método Lin-Kernighan (mencionado acima como um nome impróprio para 2-opt). Shen Lin e Brian Kernighan publicaram seu método pela primeira vez em 1972, e foi a heurística mais confiável para resolver problemas de caixeiros viajantes por quase duas décadas. Métodos de opção variável mais avançados foram desenvolvidos no Bell Labs no final da década de 1980 por David Johnson e sua equipe de pesquisa. Esses métodos (às vezes chamados de Lin – Kernighan – Johnson) baseiam-se no método Lin – Kernighan, adicionando ideias de busca tabu e computação evolutiva. A técnica básica de Lin-Kernighan fornece resultados com garantia de pelo menos 3 opções. Os métodos Lin-Kernighan-Johnson calculam um passeio Lin-Kernighan e, em seguida, perturbam o passeio pelo que foi descrito como uma mutação que remove pelo menos quatro arestas e reconecta o passeio de uma maneira diferente, então V-optando pelo novo passeio. A mutação costuma ser suficiente para mover o passeio do mínimo local identificado por Lin – Kernighan. Os métodos V-opt são amplamente considerados as heurísticas mais poderosas para o problema e são capazes de abordar casos especiais, como o Problema do Ciclo de Hamilton e outros TSPs não métricos nos quais outras heurísticas falham. Durante muitos anos, Lin–Kernighan–Johnson identificou soluções ótimas para todos os TSPs onde uma solução ótima era conhecida e identificou as soluções mais conhecidas para todos os outros TSPs nos quais o método foi testado.

Melhoria aleatória

Algoritmos de cadeia de Markov otimizados que usam subalgoritmos heurísticos de busca local podem encontrar uma rota extremamente próxima da rota ideal para 700 a 800 cidades.

TSP é uma pedra de toque para muitas heurísticas gerais concebidas para otimização combinatória, como algoritmos genéticos, recozimento simulado, busca tabu, otimização de colônias de formigas, dinâmica de formação de rios (ver inteligência de enxame) e o método de entropia cruzada.

Heurística de inserção restritiva

Did you mean:

Start with a sub-tour such as the convex hull, insert other vertices.

Otimização da colônia de formigas

O pesquisador de inteligência artificial Marco Dorigo descreveu em 1993 um método para gerar heuristicamente "boas soluções" ao TSP usando uma simulação de uma colônia de formigas chamada ACS (sistema de colônias de formigas). Ele modela o comportamento observado em formigas reais para encontrar caminhos curtos entre as fontes de alimento e seu ninho, um comportamento emergente resultante da preferência de cada formiga em seguir a trilha de feromônios depositados por outras formigas.

ACS envia um grande número de agentes formigas virtuais para explorar muitas rotas possíveis no mapa. Cada formiga escolhe probabilisticamente a próxima cidade a visitar com base em uma heurística que combina a distância até a cidade e a quantidade de feromônio virtual depositado na periferia da cidade. As formigas exploram, depositando feromônio em cada borda que cruzam, até que todas completem um passeio. Neste ponto, a formiga que completou o percurso mais curto deposita feromônio virtual ao longo de sua rota completa (atualização da trilha global). A quantidade de feromônio depositado é inversamente proporcional à duração do percurso: quanto mais curto o percurso, mais ele deposita.

Casos especiais

Métrica

No TSP métrico, também conhecido como delta-TSP ou Δ-TSP, as distâncias intermunicipais satisfazem a desigualdade triangular.

Uma restrição muito natural do TSP é exigir que as distâncias entre as cidades formem uma métrica para satisfazer a desigualdade triangular; essa é a conexão direta de A para B nunca está mais longe do que a rota através do intermediário C:

DAB≤ ≤ DAC+DCBNão. d_{AB}leq d_{AC}+d_{CB}}.

As extensões de aresta criam então uma métrica no conjunto de vértices. Quando as cidades são vistas como pontos no plano, muitas funções de distância natural são métricas, e muitas instâncias naturais de TSP satisfazem esta restrição.

Did you mean:

The following are some examples of metric TAPs for various metrics.

• No TSP euclidiano (ver abaixo) a distância entre duas cidades é a distância euclidiana entre os pontos correspondentes.
• No TSP rectilinear a distância entre duas cidades é a soma dos valores absolutos das diferenças de sua x- e Sim.- coordenadas. Esta métrica é frequentemente chamada de distância Manhattan ou métrica de bloqueio da cidade.
• Na métrica máxima, a distância entre dois pontos é o máximo dos valores absolutos das diferenças x- e Sim.- coordenadas.

As duas últimas métricas aparecem, por exemplo, no roteamento de uma máquina que faz um determinado conjunto de furos em uma placa de circuito impresso. A métrica de Manhattan corresponde a uma máquina que ajusta primeiro uma coordenada e depois a outra, de modo que o tempo para passar para um novo ponto é a soma dos dois movimentos. A métrica máxima corresponde a uma máquina que ajusta ambas as coordenadas simultaneamente, pelo que o tempo para se deslocar para um novo ponto é o mais lento dos dois movimentos.

Em sua definição, o TSP não permite que as cidades sejam visitadas duas vezes, mas muitas aplicações não precisam dessa restrição. Nesses casos, uma instância simétrica e não métrica pode ser reduzida a uma métrica. Isso substitui o gráfico original com um gráfico completo em que a distância inter-cidade DAB{displaystyle d_{AB}} é substituído pelo caminho mais curto entre A e B no gráfico original.

Euclidiana

Para pontos no plano euclidiano, a solução ótima para o problema do caixeiro viajante forma um polígono simples passando por todos os pontos, uma poligonalização dos pontos. Qualquer solução não ótima com cruzamentos pode ser transformada em uma solução mais curta sem cruzamentos por otimizações locais. A distância euclidiana obedece à desigualdade triangular, então o TSP euclidiano forma um caso especial de TSP métrico. No entanto, mesmo quando os pontos de entrada possuem coordenadas inteiras, suas distâncias geralmente assumem a forma de raízes quadradas, e o comprimento de um percurso é uma soma de radicais, tornando difícil realizar o cálculo simbólico necessário para realizar comparações exatas dos comprimentos de passeios diferentes.

Assim como o TSP geral, o TSP euclidiano exato é NP-difícil, mas o problema com somas de radicais é um obstáculo para provar que sua versão de decisão está em NP e, portanto, NP-completa. Uma versão discretizada do problema com distâncias arredondadas para inteiros é NP-completa. Com coordenadas racionais e a métrica euclidiana real, o TSP euclidiano é conhecido por estar na Hierarquia de Contagem, uma subclasse do PSPACE. Com coordenadas reais arbitrárias, o TSP euclidiano não pode estar em tais classes, uma vez que existem inúmeras entradas possíveis. Apesar dessas complicações, o TSP euclidiano é muito mais fácil do que o caso métrico geral para aproximação. Por exemplo, a árvore geradora mínima do gráfico associada a uma instância do TSP euclidiano é uma árvore geradora mínima euclidiana e, portanto, pode ser calculada em O esperado (n log n) tempo para n pontos (consideravelmente menor que o número de arestas). Isso permite que o algoritmo simples de 2 aproximações para TSP com desigualdade triangular acima opere mais rapidamente.

Em geral, para qualquer c > 0, onde d é o número de dimensões no espaço euclidiano, existe um algoritmo de tempo polinomial que encontra um percurso de comprimento no máximo (1 + 1/c) vezes o ideal para instâncias geométricas de TSP em

O(n(log⁡ ⁡ n)(O(cD))D- Sim. - Sim. 1),{displaystyle Oleft(n(log n)^{(O(c{sqrt {d}})^{d-1}}right),}

tempo; isso é chamado de esquema de aproximação em tempo polinomial (PTAS). Sanjeev Arora e Joseph SB Mitchell receberam o Prêmio Gödel em 2010 pela descoberta simultânea de um PTAS para o TSP euclidiano.

Did you mean:

In practice, simple heuristics with weaker guarantees continue to be used.

Assimétrico

Na maioria dos casos, a distância entre dois nós na rede TSP é a mesma em ambas as direções. O caso em que a distância de A a B não é igual à distância de B a A é chamado de assimétrico. TSP. Uma aplicação prática de um TSP assimétrico é a otimização de rotas usando roteamento no nível da rua (que é tornado assimétrico por ruas de mão única, estradas de acesso, rodovias, etc.).

Conversão para simétrico

Resolver um gráfico TSP assimétrico pode ser um tanto complexo. A seguir está uma matriz 3×3 contendo todos os pesos de caminho possíveis entre os nós A, B e C. Uma opção é transformar uma matriz assimétrica de tamanho N em uma matriz simétrica de tamanho 2N.

Pesos de caminho assimétricos

	A	B	C
A		1	2
B	6		3
C	5	4

Para dobrar o tamanho, cada um dos nós do gráfico é duplicado, criando um segundo nó fantasma, vinculado ao nó original com um nó "fantasma" borda de peso muito baixo (possivelmente negativo), aqui denotada −w. (Como alternativa, as arestas fantasmas têm peso 0 e o peso w é adicionado a todas as outras arestas.) A matriz 3×3 original mostrada acima é visível no canto inferior esquerdo e a transposição do original no canto superior direito. Ambas as cópias da matriz tiveram suas diagonais substituídas pelos caminhos de salto de baixo custo, representados por −w. No novo gráfico, nenhuma aresta vincula diretamente os nós originais e nenhuma aresta vincula diretamente os nós fantasmas.

Pesos do caminho simétricos

	A	B	C	A	B.	C.
A				- Sim.O quê?	6	5
B				1	- Sim.O quê?	4
C				2	3	- Sim.O quê?
A	- Sim.O quê?	1	2
B.	6	- Sim.O quê?	3
C.	5	4	- Sim.O quê?

O peso −O quê? das bordas "ghost" ligando os nós fantasma aos nós originais correspondentes devem ser baixos o suficiente para garantir que todas as bordas fantasma devem pertencer a qualquer solução TSP simétrica ideal no novo gráfico (w=0 nem sempre é baixo o suficiente). Como consequência, no passeio simétrico ideal, cada nó original aparece ao lado de seu nó fantasma (por exemplo, um caminho possível é A→ → A?→ → C→ → C?→ → B→ → B?→ → A{displaystyle mathrm {Ato A'to Cto C'to Bto B'to A} }) e fundindo os nós originais e fantasmas novamente, obtemos uma solução (optimal) do problema assimétrico original (no nosso exemplo, A→ → C→ → B→ → A{displaystyle mathrm {Ato Cto Bto A} }).

Did you mean:

Analyst 's problem

Há um problema análogo na teoria da medida geométrica que pergunta o seguinte: sob quais condições um subconjunto E do espaço euclidiano pode estar contido em uma curva retificável (isto é, quando existe uma curva com comprimento finito que visita todos os pontos em E)? Este problema é conhecido como problema do caixeiro viajante do analista.

Comprimento do caminho para conjuntos aleatórios de pontos em um quadrado

Suponha X1,...... ,Xn{displaystyle X_{1},ldots X_{n}} são nNão. variáveis aleatórias independentes com distribuição uniforme no quadrado Não.0,1]2Não. [0,1]^{2}}e deixar Ln∗ ∗ Não. L_{n}^{ast }} ser o comprimento de caminho mais curto (ou seja, solução TSP) para este conjunto de pontos, de acordo com a distância euclidiana habitual. Sabe-se que, quase certamente,

Ln∗ ∗ n→ → β β quandon→ → ∞ ∞ ,{displaystyle {frac {L_{n}^{*}}{sqrt {n}}}rightarrow beta qquad {text{quando }}nto infty}

Onde? β β - Sim. é uma constante positiva que não é conhecida explicitamente. Desde então Ln∗ ∗ ≤ ≤ 2n+2Não. L_{n}^{*}leq 2{sqrt {n}}+2} (ver abaixo), segue-se do teorema de convergência limitado que β β = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Limpar.n→ → ∞ ∞ ENão.Ln∗ ∗ ]/n{displaystyle beta =lim _{nto infty }mathbb {E} [L_{n}^{*}]/{sqrt {n}}}, daí limites inferiores e superiores em β β - Sim. seguir de limites em ENão.Ln∗ ∗ ]{displaystyle mathbb {E} [L_{n}^{*}]}.

O limite quase certo Ln∗ ∗ n→ → β β {displaystyle {frac {L_{n}^{*}}{sqrt {n}}}rightarrow beta } como n→ → ∞ ∞ {displaystyle nto infty } não existe se os locais independentes X1,...... ,Xn{displaystyle X_{1},ldots X_{n}} são substituídos por observações de um processo ergódico estacionário com marginais uniformes.

Limite superior

• Um tem L∗ ∗ ≤ ≤ 2n+2Não. L^{*}leq 2{sqrt {n}}+2}e, portanto, β β ≤ ≤ 2{displaystyle beta leq 2, usando um caminho ingênuo que visita monotonicamente os pontos dentro de cada um n- Sim. partes de largura 1/n{displaystyle 1/{sqrt {n}}} na praça.
• Poucos provaram Ln∗ ∗ ≤ ≤ 2n+1.75Não. L_{n}^{*}leq Sim., consequentemente β β ≤ ≤ 2- Sim. {2}, mais tarde melhorado por Karloff (1987): β β ≤ ≤ 0,9842{displaystyle beta leq 0.984{sqrt {2}}}.
• Fietcher mostrou um limite superior de β β ≤ ≤ 0,753...... {displaystyle beta leq 0.73dots }.

Limite inferior

• Observando isso ENão.Ln∗ ∗ ]{displaystyle mathbb {E} [L_{n}^{*}]} é maior do que nNão. vezes a distância entre X0Não. X_{0}} e o ponto mais próximo XEu...≠ ≠ X0{displaystyle X_{i}neq X_{0}}, um fica (depois de uma computação curta)

ENão.Ln∗ ∗ ]≥ ≥ 12n.{displaystyle mathbb {E} [L_{n}^{*}]geq {tfrac {1}{2}}{sqrt {n}}}

• Um limite inferior melhor é obtido observando que ENão.Ln∗ ∗ ]{displaystyle mathbb {E} [L_{n}^{*}]} é maior do que 12n(1}{2}}n} vezes a soma das distâncias entre X0Não. X_{0}} e os pontos mais próximos e mais próximos XEu...,XJJ≠ ≠ X0Não. X_{i},X_{j}neq X_{0}}, que dá

ENão.Ln∗ ∗ ]≥ ≥ (14+38)n= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =58n,{displaystyle mathbb {E} [L_{n}^{*}]geq left({tfrac {1}{4}+ {3}{8}}right){sqrt {n}}={tfrac {5}{8}}{sqrt {n}},}

• O limite mais baixo atualmente é

ENão.Ln∗ ∗ ]≥ ≥ (58+1951)n,{displaystyle mathbb {E} [L_{n}^{*}]geq ({tfrac {5}{8}}+{tfrac {19}{5184}}){sqrt {n}},}

• Held e Karp deram um algoritmo de tempo polinomial que fornece limites menores numéricos para Ln∗ ∗ Não. L_{n}^{*}}e, portanto, β β (≃ ≃ Ln∗ ∗ /n){displaystyle beta (simeq L_{n}^{*}/{sqrt {n}}} que parecem ser bons até mais ou menos 1%. Em particular, David S. Johnson obteve um limite inferior por experiência de computador:

Ln∗ ∗ ≳ ≳ 0,80n+0,522,Não. L_{n}^{*}gtrsim 0.7080{sqrt {n}}+0.522,}

onde 0,522 vem dos pontos próximos ao limite quadrado que têm menos vizinhos, e Christine L. Valenzuela e Antonia J. Jones obtiveram o seguinte outro limite inferior numérico:

Ln∗ ∗ ≳ ≳ 0078n+0.551Não. L_{n}^{*}gtrsim 0.7078{sqrt {n}}+0.551}.

Complexidade computacional

O problema mostrou ser NP-difícil (mais precisamente, é completo para a classe de complexidade FP^NP; veja problema de função), e a versão do problema de decisão ("dada os custos e um número x, decida se existe uma rota de ida e volta mais barata que x") é NP-completa. O problema do gargalo do caixeiro viajante também é NP-difícil. O problema permanece NP-difícil mesmo no caso em que as cidades estão no plano com distâncias euclidianas, bem como em vários outros casos restritivos. Removendo a condição de visitar cada cidade ‘apenas uma vez’; não remove a dureza NP, pois no caso planar existe um passeio ótimo que visita cada cidade apenas uma vez (caso contrário, pela desigualdade triangular, um atalho que pula uma visita repetida não aumentaria a duração do passeio).

Complexidade de aproximação

No caso geral, encontrar o passeio mais curto de um caixeiro viajante é uma tarefa NPO completa. Se a medida de distância for métrica (e, portanto, simétrica), o problema se torna APX-completo e o algoritmo de Christofides e Serdyukov o aproxima dentro de 1,5.

Se as distâncias forem restritas a 1 e 2 (mas ainda são métricas) a relação de aproximação se torna 8/7. No caso assimétrico com desigualdade de triângulo, até recentemente apenas as garantias de desempenho logarítmico eram conhecidas. Em 2018, uma aproximação constante do fator foi desenvolvida por Svensson, Tarnawski e Végh. O melhor algoritmo atual, por Traub e Vygen, atinge a relação de desempenho de 22+ε ε - Sim.. O limite mais conhecido de aproximação é de 75/74.

O problema de maximização correspondente de encontrar o mais longo viagem de vendedor é aproximável dentro de 63/38. Se a função de distância é simétrica, a turnê mais longa pode ser aproximada dentro de 4/3 por um algoritmo determinístico e dentro 125(33+ε ε )(33+varepsilon)} por um algoritmo randomizado.

Desempenho humano e animal

O TSP, em particular a variante euclidiana do problema, tem atraído a atenção de pesquisadores em psicologia cognitiva. Foi observado que os humanos são capazes de produzir soluções quase ótimas rapidamente, de forma quase linear, com desempenho que varia de 1% menos eficiente, para gráficos com 10 a 20 nós, a 11% menos eficiente para gráficos com 120 nós. A aparente facilidade com que os humanos geram com precisão soluções quase ótimas para o problema levou os pesquisadores a levantar a hipótese de que os humanos usam uma ou mais heurísticas, sendo as duas teorias mais populares, sem dúvida, a hipótese do casco convexo e a heurística de evitação de cruzamento. No entanto, evidências adicionais sugerem que o desempenho humano é bastante variado, e as diferenças individuais, bem como a geometria dos gráficos, parecem afetar o desempenho na tarefa. No entanto, os resultados sugerem que o desempenho do computador no TSP pode ser melhorado através da compreensão e emulação dos métodos utilizados pelos humanos para estes problemas, e também levaram a novos conhecimentos sobre os mecanismos do pensamento humano. A primeira edição do Journal of Problem Solving foi dedicada ao tema do desempenho humano no TSP, e uma revisão de 2011 listou dezenas de artigos sobre o assunto.

Um estudo de 2011 sobre cognição animal intitulado "Deixe o pombo dirigir o ônibus," batizado em homenagem ao livro infantil Don't Let the Pigeon Drive the Bus!, examinou a cognição espacial em pombos estudando seus padrões de voo entre vários comedouros em um laboratório em relação à viagem. problema do vendedor. No primeiro experimento, os pombos foram colocados no canto de uma sala de laboratório e deixados voar até comedouros próximos contendo ervilhas. Os pesquisadores descobriram que os pombos usavam amplamente a proximidade para determinar qual comedouro escolheriam em seguida. No segundo experimento, os comedouros foram dispostos de tal forma que voar até o comedouro mais próximo em todas as oportunidades seria bastante ineficiente se os pombos precisassem visitar todos os comedouros. Os resultados da segunda experiência indicam que os pombos, embora ainda favoreçam soluções baseadas na proximidade, “podem planear vários passos à frente ao longo da rota quando as diferenças nos custos de viagem entre rotas eficientes e menos eficientes baseadas na proximidade se tornam maiores”. 34; Estes resultados são consistentes com outras experiências feitas com não primatas, que provaram que alguns não primatas eram capazes de planear rotas de viagem complexas. Isto sugere que os não-primatas podem possuir uma capacidade cognitiva espacial relativamente sofisticada.

Cálculo natural

Quando apresentado a uma configuração espacial de fontes alimentares, o amebóide Physarum polycephalum adapta sua morfologia para criar um caminho eficiente entre as fontes alimentares, o que também pode ser visto como uma solução aproximada para o TSP.

Referências de referência

Para benchmarking de algoritmos TSP, TSPLIB é uma biblioteca de exemplos de instâncias do TSP e problemas relacionados são mantidos, consulte a referência externa TSPLIB. Muitos deles são listas de cidades reais e layouts de circuitos impressos reais.

Cultura popular

• Viajando Salesman, pelo diretor Timothy Lanzone, é a história de quatro matemáticos contratados pelo governo dos EUA para resolver o problema mais elusivo na história da ciência da computação: P vs. NP.
• As soluções para o problema são usadas pelo matemático Bob Bosche em um subgênero chamado arte TSP.