Problema do caixeiro-viajante

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).

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). Dado um conjunto C = { c 1 , . . . , c n } {\displaystyle C=\{c_{1}\;,...,\;c_{n}\}} de n cidades ci e uma matriz de distâncias ( ρ i j ) {\displaystyle \left(\rho _{ij}\right)} , onde ρ i j = ρ ( c i , c j ) {\displaystyle \rho _{ij}=\rho (c_{i},\;c_{j})} ( {\displaystyle (} i , j {\displaystyle i,\;j} ∈ {\displaystyle \in } { 1 , . . . , n } {\displaystyle \{1,\;...,\;n\}} , ρ i j {\displaystyle \rho _{ij}} = ρ j i {\displaystyle =\rho _{ji}} , ρ i i {\displaystyle \rho _{ii}} = 0 ) {\displaystyle =0)} , a tarefa passa por encontrar a permutação π ∈ S n = { s : { 1 , . . . , n } → { 1 , . . . , n } } {\displaystyle \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 → R {\displaystyle f:S_{n}\rightarrow \mathbb {R} } , onde

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.