Яка історія проблеми мандрівного продавця протягом багатьох років в короткому списку?
Походження проблеми мандрівного продавця незрозумілі. Посібник для мандрівників з 1832 року згадує про проблему і включає в себе прикладні поїздки по Німеччині та Швейцарії, але не містить математичного лікування.


Вільям Роуан Гамільтон
TSP була математично сформульована в 19 столітті ірландським математиком Вільямом Рованом Гамільтоном і британським математиком Томасом Кіркманом. Ікозійська гра Гамільтона була розважальною головоломкою, заснованою на знаходженні гамільтонського циклу. Загальна форма TSP, здається, була вперше вивчена математиками в 1930-х роках у Відні і Гарварді, зокрема Карлом Менгером, який визначає проблему, розглядає очевидний алгоритм брутто-сили і спостерігає за неоптимальністю найближчого сусіда евристики:

Ми називаємо проблемою посланця (оскільки на практиці це питання має вирішувати кожен поштарець, в будь-якому випадку також і багато мандрівників) завдання знайти, для кінцевого числа точок, чиї відстані в парах відомі, найкоротший маршрут, що з'єднує точки. Звичайно, цю проблему можна вирішити кінцевим числом випробувань. Правила, які могли б підштовхнути кількість випробувань нижче кількості пермутацій даних точок, не відомі. Правило про те, що спочатку потрібно йти від початкової точки до найближчої точки, потім до найближчої до неї точки і т. д., не дає найкоротшого маршруту.

Вона була вперше розглянута математично в 1930-х роках Мерріллом М. Флодом, який прагнув вирішити проблему маршрутування шкільних автобусів. Хаслер Вітні з Принстонського університету викликав інтерес до проблеми, яку він назвав "проблемою 48 штатів". Найбільш ранньою публікацією, що використовувала фразу «проблема подорожуючого продавця», був звіт корпорації RAND 1949 року Джулії Робінсон «Про гамільтонівську гру (проблема подорожуючого продавця).»

У 1950-х і 1960-х роках проблема стала все більш популярною в наукових колах Європи і США після того, як корпорація RAND в Санта-Моніці запропонувала нагороди за кроки у вирішенні проблеми. Значні внески зробили Джордж Данциг, Дельберт Рей Фулкерсон і Селмер М. Джонсон з корпорації RAND, які висловили проблему як цілісну лінійну програму і розробили метод різання площини для її вирішення. Вони написали те, що вважається основним документом на тему, в якому за допомогою цих нових методів вони вирішили випадок з 49 містами до оптимальності, побудуючи тур і доводячи, що жоден інший тур не міг бути коротшим. Данциг, Фулкерсон і Джонсон, однак, спекулювали, що при наближенні оптимального рішення ми можемо знайти оптимізм або довести оптимізм, додавши невелику кількість додаткових нерівностей (різів). Вони використовували цю ідею, щоб вирішити свою початкову проблему міста 49 за допомогою моделі струн. Вони виявили, що їм знадобилося лише 26 скорочень, щоб прийти до вирішення їхньої проблеми з 49 містами. Хоча ця стаття не давала алгоритмічного підходу до проблем TSP, ідеї, що лежали в ній, були незамінними для подальшого створення точних методів вирішення для TSP, хоча знадобилося б 15 років, щоб знайти алгоритмічний підхід у створенні цих скорочень. Крім методів різання площини, Данциг, Фулкерсон і Джонсон вперше використовували алгоритми галузей і зв'язків.

1959 — Джилліан Бердвуд, Дж. Холтон і Джон Хаммерслі опублікували статтю під назвою «Найкоротший шлях через багато точок» в журналі Кембриджського філософського товариства. Теорема Beardwood-Halton-Hammersley надає практичне рішення проблеми подорожуючого продавця. Автори отримали асимптотичну формулу для визначення довжини найкоротшого маршруту для продавця, який починається вдома або в офісі і відвідує фіксовану кількість місць, перш ніж повернутися до початку.

У наступні десятиліття проблема була вивчена багатьма дослідниками з математики, комп'ютерної науки, хімії, фізики та інших наук. Однак у 1960-х роках був створений новий підхід, який замість пошуку оптимальних рішень виробляв би рішення, довжина якого, ймовірно, обмежена множиною оптимальної довжини, і, роблячи це, створював би нижчі межі для проблеми; ці нижчі межі потім використовувалися б з підходами для галузей і зв'язків. Одним із способів зробити це було створити мінімальне обтяження дерева графу, а потім подвоїти всі його країни, що дає звіт про те, що довжина оптимального туру не більше ніж в два рази більше ваги мінімального обтяження дерева.

У 1976 році Крістофідіс і Сердюков незалежно один від одного зробили великий прогрес у цьому напрямку: алгоритм Крістофіда-Сердюкова дає рішення, яке, в гіршому випадку, триває в 1,5 рази довше оптимального рішення. Оскільки алгоритм був простим і швидким, багато хто сподівався, що він дасть місце для майже оптимального способу вирішення. Однак ця надія на поліпшення не реалізувалася відразу, і Крістофідес-Сердюков залишався методом з кращим найгіршим сценарієм до 2011 року, коли був розроблений (дуже) трохи покращений алгоритм наближення для піднабору «графічних» ТСП. У 2020 році це невелике поліпшення було розширено до повного (метричного) TSP.

Річард М. Карп показав в 1972 році, що проблема гамільтонівського циклу була NP-комплетною, що означає NP-твердість TSP. Це дало математичне пояснення очевидної обчислювальної складності пошуку оптимальних турів.

Великий прогрес був досягнутий в кінці 1970-х і 1980-х років, коли Grötschel, Padberg, Rinaldi та інші змогли точно вирішити випадки з до 2 392 містами, використовуючи різання літаків і гілок і кордонів.

У 1990-х Applegate, Bixby, Chvátal і Cook розробили програму Concorde, яка була використана в багатьох останніх рішеннях запису. Герхард Рейнельт опублікував TSPLIB в 1991 році, збірку референтних випадків різної складності, які були використані багатьма дослідницькими групами для порівняння результатів. У 2006 році Кук та інші обчислили оптимальний тур через 85,900-міський екземпляр, наданий проблемою розміщення мікрочіпа, в даний час найбільшим вирішеним екземпляром TSPLIB. Для багатьох інших випадків з мільйонами міст можна знайти рішення, які гарантовано знаходяться в межах 2-3% оптимального туру.
XIX століття — математично сформульована вперше ірландським математиком Вільямом Рованом Гамільтоном і британським математиком Томасом Кіркманом.
1930 - Спочатку вивчався математиками у Відні та Гарварді, особливо Карлом Менгером і Мерилом М. Флодом, які прагнули вирішити проблему маршрутування шкільних автобусів.
1959 — Джилліан Бердвуд, Дж. Холтон і Джон Хаммерслі опублікували статтю під назвою «Найкоротший шлях через багато точок» в журналі Кембриджського філософського товариства, яка надала перше практичне рішення.
* 1960-ті роки - створюється новий підхід, який виробляє розчин, довжина якого доведено обмежена множиною оптимальної довжини.
1972 р. Річард Карп показав, що проблема гамільтонського циклу NP-комплексна, що означає NP-жорсткість проблеми подорожуючого продавця.
1976 — Крістофідіс і Сердюков самостійно винайшли новий алгоритм, який дає рішення, яке в гіршому випадку не більше ніж в 1,5 рази довше оптимального рішення.
1990 - Applegate, Bixby, Chvátal і Cook розробили програму Concorde, яка була використана в багатьох останніх рішеннях запису.
1991 — Герхард Рейнельт опублікував TSPLIB, збірку референтних випадків різної складності, які використовувалися багатьма дослідницькими групами для порівняння результатів.
* 2006 - Кук та інші обчислили оптимальний тур через 85,900-міський випадок, наданий проблемою розміщення мікрочіпа, в даний час найбільшим вирішеним випадом TSPLIB.
2011 — Злегка поліпшений алгоритм наближення розроблено для підсуду проблеми «графічного» подорожуючого продавця.
* 2020 - Дещо поліпшений алгоритм наближення, розроблений для піднабору "графічного" розширюється, щоб охопити повну проблему подорожуючого продавця.