O [i]problema do caixeiro-viajante (PCV) [/i]consiste na procura de um circuito que possua a menor distância, começando numa qualquer cidade, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial (Nilsson, 1982).
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 PCV, [i]travelling salesman problem[/i] (TSP) em inglês, é um problema de optimização que, apesar de parecer modesto é, na realidade, muito investigado por cientistas, matemáticos e investigadores de diversas áreas, tais como: logística, genética e produção, entre outros (Applegate et al., cop. 2006, p. 1).
([url]http://www.clube.spm.pt/arquivo/876[/url] , Fevereiro de 2016)
