Задача коммивояжёра - это задача комбинаторной оптимизации, направленная на поиск наиболее оптимального маршрута, который хотя бы по одному разу проходил через определенные города с последующим возвратом в исходный город.
Общие сведения о задаче коммивояжера
Логистика имеет тесные связи с математикой и другими точными науками, поскольку по большей части вопросов пытается найти оптимальные значения действий экономических субъектов и результатов их хозяйственной деятельности. Одним из примеров подобного поиска в логистике является задача коммивояжера.
Задача коммивояжера представляет собой одну из самых известных задач комбинаторной оптимизации. Суть этой задачи сводится к поиску самого выгодного маршрута, который хотя бы единожды проходил через указанные города и в конце путешествия возвращался в исходный город.
При формулировки конкретной задачи из категории задачи коммивояжера важно указать критерий, по которому будут определять самый выгодный маршрут. В большинстве случаев используют один из следующих критериев:
- Кратчайший маршрут (т.е. тот маршрут, который требует преодоления наименьшего расстояния);
- Быстрейший маршрут (т.е. тот маршрут, на преодоление которого требуется затратить наименьшее время);
- Самый дешевый маршрут (т.е. тот маршрут, на преодоление которого требуется затратить наименьший объем финансовых средств);
- Совокупный (интегральный) критерий и т.д.
Помимо этого, в условиях задачи указываются соответствующие матрицы расстояний, стоимости и тому подобного. Обычно указанию подлежит однократное прохождение маршрута через каждый город. В этом случае выбор осуществляется среди гамильтоновых циклов (т.е. замкнутого пути, простого цикла, в который входят все вершины графа).
Рассматриваемая нами задача была названа в честь профессии коммивояжера - посредника между продавцом товара и покупателем, который действовал, как правило, по поручению фирмы, занимался сбытом товара, т.е. разъезжал и предлагал покупателям товары по образцам и каталогам.
На данный момент существует несколько частных случаев общей постановки задачи коммивояжера. Например, часто решают, так называемую геометрическую (планетарную, евклидовую) задачу коммивояжера. Она соответствует ситуации, когда матрица расстояний отражает расстояния между точками на плоскости.
Еще отдельно рассматривают и решают метрическую задачу коммивояжера. Согласно ее условиям, на матрице стоимостей выполняется неравенство треугольника. Еще существуют симметричная, асимметричная и обобщенная задачи коммивояжёра.
Оптимизационная постановка задачи коммивояжёра относится к классу NP-трудных задач. Кроме того, она считается трансвычислительной задачей, поскольку уже при сравнительно малом числе городов (больше 65) ее решение не может быть найдено через перебор вариантов никакими компьютерными программами за время, меньшее нескольких миллиардов лет.
История задачи коммивояжера
Определенную связь с задачей коммивояжёра имеет задача о поиске гамильтонового цикла. В данную категорию входят задача о ходе коня, которая известна науке с XVIII века, и задача икосиан (XIX век). Последняя представляет собой математическую головоломку, в которой надо пройти по графу с 20 вершинами, побывав в каждой из них только один раз.
В 1832 г. была опубликована книга с советами старого курьера, в которой рассказывалось о задаче, похожей на задачу коммивояжера, однако инструменты математики для её решения не использовали. Первые упоминания задачи коммивояжера в качестве математической задачи на оптимизацию принадлежат австрийско-американскому математику Карлу Менгеру-младшему, который сформулировал её на математическом коллоквиуме в 1930 году.
В 1950-60-е гг. задача коммивояжёра привлекла внимание американских и европейских ученых. Большой вклад в изучение и решение задачи принадлежит Дж. Данцигу, Д. Р. Фалкерсону и С. Джонсону, которые в 1954 году сформулировали задачу в виде задачи дискретной оптимизации и для её решения использовали метод отсечений.
В итоге ученые смогли построить путь коммивояжёра для одной частной постановки задачи с 49 городами и обосновать его оптимальность. В 1960-70-е гг. задача изучалась многими учеными как в теоретической плоскости, так и для практического использования ее результатов в сферах экономики, информатики, биологии и химии.
Методы решения задачи коммивояжера
Все эффективные методы решения задачи коммивояжёра, которые сокращают полный перебор, являются эвристическими методами. Большая их часть позволяет найти не самый эффективный маршрут, а только приближённое решение. Кроме того, большое распространение получили, так называемые, any-time-алгоритмы, которые постепенно улучшают некоторое текущее приближенное решение.
Для достаточно больших задач оптимальные или приблизительные решения позволяют находить методы дискретной оптимизации, в частности, ветвей и границ. Применение этого метода впервые было предложено в 1963 г. группой авторов (К. Кэрол, Д. Суини, К. Мурти, Дж. Литл).
Однако метода ветвей и границ для быстрого поиска маршрутов обычно недостаточно. Поэтому для поиска маршрутов приемлемой длины возможно комбинированное применение точных методов с эвристическими.
В 1987 году для решения задачи коммивояжёра использовали метод эластичной сети, который базируется на использовании механизмов установления упорядоченных нейронных связей. Каждый из маршрутов рассматривался как отображение окружности на плоскость. Соседние точки на окружности должны отображаться в точки, по возможности ближайшие.
Также стоит указать, что математики предлагали для решения задачи коммивояжера использование, так называемых, муравьиного алгоритма, генетического алгоритма, алгоритма динамического программирования.
