Задача о коммивояжере (traveling salesman problem) состоит в отыскании оптимального маршрута для коммивояжера. Ему необходимо объехать все порученные города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд.
На математическом языке она формулируется как поиск пути, который связывает два или более узла, при этом выполняется оптимальным способом. Алгоритмы решения этой задачи применяются при выборе оптимальных маршрутов автотранспорта, при кольцевой доставке продукции потребителям.
В 1832 году издана книга с названием «Коммивояжёр — как он должен вести себя и что должен делать для того, чтобы доставлять товар и иметь успех в своих делах — советы старого курьера» (нем. Der Handlungsreisende – wie er sein soll und was er zu tun hat, um Aufträge zu erhalten und eines glücklichen Erfolgs in seinen Geschäften gewiß zu sein – von einem alten Commis-Voyageur), в которой описана задача. В ней предложены примеры маршрутов для некоторых регионов Германии и Швейцарии.
Позднее эта задача появилась как математическая. Первые постановки в качестве математической задачи на оптимизацию принадлежат Карлу Менгеру, который сформулировал её на математическом коллоквиуме в 1930 году так: «Мы называем задачей посыльного (поскольку этот вопрос возникает у каждого почтальона, в частности, её решают многие путешественники) задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно».
Задача коммивояжёра относится к числу трансвычислительных. При относительно небольшом числе городов (>66) задача не может быть решена методом перебора вариантов никакими теоретически мыслимыми компьютерами за время, меньшее нескольких миллиардов лет.
В марте 2005 года задача с 33 810 точками была решена программой Конкорд. Вычислили путь с 66 048 945 точками, доказано отсутствие более коротких путей. В апреле 2006 было найдено решение для варианта задачи с 85 900 точками.
Благодаря решениям этой задачи, найденным алгоритмам у современного горожанина теперь есть навигатор. В логистических компаниях применяют такие алгоритмы для построения оптимальных маршрутов по времени, объёму груза и топливу.
Один из следующих обзоров посвятим обзору другой комбинаторной задачи, которая называется «задача о рюкзаке». Ее применяют для моделирования большого числа практических задач, в том числе в логистике.