Проблема путешествующего продавца (часто называемая TSP) - классическая алгоритмическая проблема в области вычислительной техники и исследования операций. Она ориентирована на оптимизацию. В этом контексте лучшее решение часто означает решение, которое дешевле, короче или быстрее. TSP является математической задачей. Легче всего она выражается в виде графика, описывающего расположение набора узлов.

Проблема путешествующего продавца была определена в 1800-х годах ирландским математиком У. Р. Гамильтоном и британским математиком Томасом Киркманом. Икосианская игра Гамильтона была рекреационной головоломкой, основанной на поиске цикла Гамильтона. Общая форма TSP, по-видимому, были впервые изучены математиками во время 1930-х годов в Вене и в Гарварде, в частности, Карл Менгер. Менгер определяет проблему, рассматривает очевидный алгоритм брутальной силы и наблюдает неоптимальность эвристики ближайшего соседа:

Обозначим задачей посланника (так как на практике этот вопрос должен решаться каждым почтальоном, во всяком случае, и многими путешественниками) задачу найти для многих точек, чье парное расстояние известно, кратчайший маршрут, соединяющий эти точки. Конечно, эта проблема решается бесконечно многими испытаниями. Неизвестны правила, по которым количество испытаний опускалось бы ниже количества перестановок в заданных точках. Правило, по которому нужно сначала пройти от начальной точки до ближайшей, затем до ближайшей точки и т.д., в общем случае, не дает кратчайшего маршрута.

Хасслер Уитни из Принстонского университета вскоре представил проблему с именем продавца путешествий.