Logística/Sistemas de distribuição/Problema do caixeiro viajante

O problema do caixeiro-viajante (PCV), em inglês travelling salesman problem (TSP), é considerado um problema de optimização que, consiste em encontrar um circuito que possua a menor distância entre os vários pontos de paragem. Apesar de parecer pouco, este problema é, na realidade, um dos mais investigados, por parte w:cientistas!cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e genética, entre outros (Applegate et al., cop. 2006, p. 1).

O problema pertence à categoria de NP-difícil, «NP-hard» (em inglês), que o remete para um campo de complexidade exponencial, isto é, o esforço computacional que é necessário para a sua resolução cresce de forma exponencial com o tamanho do problema. Quanto mais complexo o problema, maior o esforço necessário à sua resolução. Assim, dado que é difícil, se não mesmo impossível, determinar a solução óptima desta tipo de problemas, os métodos de resolução passam pelas heurísticas e afins que, dum ponto de vista matemático, não garantem a obtenção de uma solução óptima (Cunha, 2002).

A origem do nome «travelling salesman problem» é desconhecida. Não se conhece qualquer documento que prove quem foi o autor ou criador do nome do problema. Merril Flood, da Universidade de Princeton, um dos investigadores mais proeminentes nas primeiras aplicações do problema referiu, 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).

O desenvolvimento dos problemas relacionados com o PVC, tiveram inicio em 1800 pela mão de dois matemáticos: o escocês William Rowan Hamilton e o britânico Thomas Penyngton Kerkman. Enquanto que a sua forma geral parece ter sido estudado pela primeira vez em 1930, em Harvard e Viena. O problema foi posteriormente estudado por Hassler Whitney e Merril Flood em Princeton. Pode-se que o nome do problema ficou definitivamente concluido no ano 1950 (Applegate et al., cop. 2006, p.2).