9.2. Маршрут коммивояжера

В транспортной логистике чрезвычайно часто возникают задачи, когда прохождение транспорта по всем дорогам обслуживаемой сети вовсе не обязательно, однако важен факт заезда в каждый из обслуживаемых объектов. Иногда дополнительно уточняется, что по некоторым причинам в каждый город можно заезжать не более одного раза. Именно так и была сформулирована так называемая задача коммивояжера, поставленная еще в 1934 году и ставшая впоследствии весьма знаменитой.

Введем некоторые термины. Объекты пронумерованы числами j, . Тур коммивояжера может быть описан циклической перестановкой , ,причем все – разные номера. Повторяющийся в начале и концепоказывает, что перестановка зациклена. Расстояния между парами вершин образуют матрицу С. Задача состоит в том, чтобы найти тур , минимизирующий функционал

, где .

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

В ряде отраслей промышленности, особенно фармацевтического и химического плана, возникает внешне совсем иная задача планирования производства. Допустим, нужно произвести ряд продуктов, используя единственный тип аппаратуры или реактор. Аппарат должен (или не должен) быть перенастроен (очищен) после того, как произведен продукт p_i, но до того, как началось производство продукта p_j. Допустим, стоимость перенастройки аппаратуры постоянна и не зависит от сочетания только что произведенного и готовящегося к производству продукта (или просто неизвестна и берется какое-то усредненное ее значение). Разумеется, не требуется никаких затрат, если перенастройка аппаратуры не нужна. Пусть такие продукты по технологическим соображениям производятся в некотором цикле, т.е. после производства N продуктов снова возобновляется производство в том же фиксированном порядке. Возможна внешне совсем иная ситуация, которая однако решается тем же самым методом. Возникает вопрос, может ли быть найдена циклическая последовательность производства продуктов p_j, не требующая перенастройки аппаратуры? Если такой последовательности не существует, то какова должна быть очередность производства продуктов с наименьшими затратами на перенастройку?

НЕОБХОДИМЫЕ УТОЧНЕНИЯ

Цикл, проходящий через все вершины неориентированного графа ровно по одному разу, называется гамильтоновым циклом. Цикл, проходящий через все вершины ориентированного графа ровно по одному разу, называется гамильтоновым контуром. Незамкнутый гамильтонов цикл (контур) называется "гамильтоновой цепью" ("гамильтоновым путем").

Обычно под понятием веса ребра подразумевают расстояние , откуда с точки зрения логики следует выполнение нескольких условий:

1. Неотрицательность, т.е. для всех : ,.

2. Симметричность, т.е. для всех : .

3. Соответствие неравенству треугольника, т.е. для всех :.

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

ПОСТАНОВКА ЗАДАЧИ

1. Дан ориентированный граф G, требуется найти в нем гамильтонов цикл или все существующие гамильтоновы циклы.

2. Дан полный ориентированный граф G, дугам которого приписаны произвольные веса . Найти гамильтонов цикл с наименьшим суммарным весом (минисуммная постановка).

3. Дан полный ориентированный граф G, дугам которого приписаны произвольные веса . Найти гамильтонов цикл, в котором самая длинная дуга минимальна (минимаксная постановка).

Рис. 9.2. Решение задачи коммивояжера

Естественно, если граф не полный, то при необходимости его можно рассматривать как полный, приписывая отсутствующим дугам бесконечный вес.

В общем случае, точное решение задачи коммивояжера – это перебор всех возможных гамильтоновых циклов. Его можно либо усовершенствовать для снижения размерности, либо заменить на приближенные или эвристические методы, что в некоторых случаях может быть целесообразно.

Решение задачи коммивояжера для 40 точек приведено на рис. 9.2.