Обзор существующих алгоритмов решения

Впервые математическая модель для транспортной задачи была предложена G.B. Dantzig и J.H. Ramser в 1959 году. Сегодня выделяют 3 основных класса алгоритмов решения задачи маршрутизации транспорта: точные, эвристические, метаэвристические.

Точные алгоритмы.

Как ясно из названия, такой подход перебирает все возможные решения для поиска лучшего. Наиболее известными точными методами являются метод ветвей и границ и метод ветвей с отсечением.

Метод ветвей и границ (Branch and bound).

Впервые данный метод для решения задачи маршрутизации транспорта был предложен в 1960 году учеными A.H. Land и A.G. Doig. Для задачи на поиск минимума функции основная идея алгоритма состоит в применении двух процедур: ветвление и нахождение границ. Первая процедура делит множество допустимых решений на подмножества, затем процедура применяется рекурсивно к каждому подмножеству. Так множество подмножеств образует дерево ветвей и границ (дерево поиска), узлы — этого отдельные подмножества. Процедура нахождения границ вычисляет верхнюю и нижнюю границы подмножеств. Далее исключаются подмножества, на которых нижняя граница больше верхней на любом из других подмножеств. По существу, этот метод является вариацией полного перебора с исключением подмножеств допустимых решений, которые заведомо не содержат оптимальные решения.

Метод ветвей и границ показывает хорошие результаты для задач небольшой размерности. Поскольку время вычислений растет слишком быстро, данный алгоритм невозможно применять для задач с более чем 25−30 вершинами.

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

Эвристические алгоритмы.

Эвристический алгоритм — это алгоритм решения задач, который для большинства случаев дает приемлемое, но не обязательно «правильное» решение.

Эвристический алгоритм осуществляет относительно ограниченный поиск в пространстве решений, при этом дает хорошие решения за приемлемое время.

Стоит отметить, что эвристические алгоритмы, в отличие от точных, обладают следующими свойствами:

• · Они не гарантируют нахождение лучшего решения.
• · Они не гарантируют нахождение решения вообще, даже если оно заведомо существует.
• · Они могут давать неверные решения в некоторых случаях.

В свою очередь, эвристические алгоритмы делят еще на 3 типа: конструктивные алгоритмы, двухфазные (кластерные) алгоритмы и улучшающие алгоритмы.

Конструктивные алгоритмы.

Выполняют постепенное построение решения, при этом отслеживают рост его стоимости. Такие алгоритмы не имеют фазы дальнейшего улучшения. Примерами таких алгоритмов являются алгоритм Кларка-Райта, последовательный алгоритм вставки Моля-Джеймсона, последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса.

Алгоритм Кларка-Райта.

Алгоритм Кларка-Райта (Clarke and Wright) был предложен в 1964 году. Он является одним из самых известных методов решения ЗМТ. Основная идея алгоритма основана на процессе слияния нескольких мелких маршрутов в один до тех пор, пока это уменьшает суммарную стоимость объезда. Алгоритм сначала строит опорное решение, при котором одно транспортное средство посещает одну вершину, т. е. создается n маршрутов транспортных средств. Далее считаются «сбережения» (savings). Эта величина показывает, насколько снизится общая стоимость решения при объединении двух маршрутов в один, т. е.. Полученные сбережения выстраиваются в порядке убывания и просматриваются сверху вниз. Для текущего сбережения ищутся 2 маршрута, содержащие дуги и соответственно. Если возможно, найденные маршруты объединяются в один путем удаления дуг и и добавлением дуги. Объединение повторяется до тех пор, пока это возможно.

Преимущества алгоритма Кларка-Райта состоят в его простоте и надежности. При этом главным недостатком считается резкое падение эффективности работы по мере приближения к концу вычислений. Поэтому данный алгоритм обычно не используется для поиска конечного решения, но он часто берется в качестве алгоритма для поиска опорного решения. А дальнейшие улучшениями производятся более эффективными методами.

Двухфазные (кластерные) алгоритмы.

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

• 1) сначала происходит кластеризация, затем выполняется поиск решения ЗК;
• 2) сначала ищется решение ЗК, а затем оно делится на несколько маршрутов. При этом ЗК решается на всем исходном множестве вершин.

Примеры: алгоритм заметания, алгоритм Фишера-Джекумера, алгоритм Брамела-Симчи-Леви.

Алгоритм заметания.

Алгоритм заметания (sweep algorithm) предложил Рен (Wren) в 1971 году, но обычно его авторство относят Жиллету и Миллеру (Gillett and Miller), поскольку алгоритм стал популярным после их статьи 1974 года.

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

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

Алгоритм можно описать таким образом:

Шаг 1: Выбираем транспортное средство, которое еще не было использовано.

Шаг 2: Выбираем не сгруппированные вершины в порядке возрастания их полярных углов и определяем их в группу к транспортному средству, пока транспортное средство не будет заполнено, то есть, пока сумма потребностей в товаре этих вершин не превысит грузоподъемность транспортного средства. Если не сгруппированные вершины еще есть, перейти к Шагу 1.

Шаг 3: Каждая полученная группа решается одним точным или приближённым алгоритмом (ЗК).

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

Также, в некоторых модификациях алгоритма для улучшения конечного решения добавляется фаза последующей оптимизации, в которой производится обмен вершинами между соседними кластерами. После этого производится корректировка маршрутов и уже выдается конечный ответ.

Улучшающие алгоритмы.

Эвристические алгоритмы улучшения маршрута (improvement heuristics) являются классическими методами локального поиска. В свою очередь, улучшающие алгоритмы бывают параллельными или последовательными, то есть, улучшают за один шаг один маршрут или несколько маршрутов сразу.

Случай улучшения одного маршрута является по сути оптимизацией решения задачи коммивояжера. Основные методы описаны Лином (Lin) в 1967 году. Они основаны на исключении из маршрута дуг и различных их перестановках до тех пор, пока не будет найдено лучшее решение.

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

• o перекрещивание двух рёбер из двух маршрутов (рис. 2);
• o обмен вершинами между двумя маршрутами (рис. 3);
• o перенос вершин из одного маршрута в другой (рис. 4);
• o комбинации первых трех вариантов.

Рис. 2.

Рис. 3.

Рис. 4.

Поиск решений задачи маршрутизации транспорта начался в 60-е годы XX века. Эвристические методы, которые сейчас являются классическими, разработаны по большей части между 1960 и 1990 годом. В последние же двадцать лет усилия ученых направлены в основном создание так называемых метаэвристик.

Метаэвристики.

Из названия метаэвристик следует, что они не являются законченными эвристиками, готовыми для применения, а являются некоторым методом для построения законченной эвристики для конкретной задачи. Большинство из алгоритмов являются bio-inspired, что означает, что они вдохновлены явлениями живой и неживой природы. Наиболее интересными из них считаются следующие методы: поиск с исключениями, моделируемый и детерминированный отжиг, генетический алгоритм, алгоритм на основе муравьиных колоний.

Большое количество работ, посвящённых метаэвристикам, появляющихся в научном мире, не позволяет однозначно определить наилучший алгоритм для практического внедрения. Метаэвристики содержат большое количество дискретных и непрерывных параметров, управляющих их работой и требующие выполнения процедуры вариации значений для получения удачной законченной эвристики. Подбор параметров необходимо выполнять не только для разных типов задач, но зачастую даже для каждого нового набора входных данных. Например, поиск с исключениями содержит только 1−2 дискретных параметра, а моделируемый отжиг содержит ряд непрерывных параметров, делающих процедуру вариации практически невозможной. Генетический алгоритм и алгоритм на основе муравьиных колоний в процессе работы обрабатывают очень большой массив данных, приводящий к длительным вычислениям, а также содержат большое количество управляющих параметров. Это заметно усложняет использование подобных алгоритмов для решения реальных задач на практике, т. к. требует очень высокой квалификации пользователя программных пакетов на их основе. Это в некоторой степени является слабой стороной данного подхода.

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

Имитация отжига.

Идея метода имитации отжига или моделируемого отжига (simulated annealing) появилась при наблюдении процессов, происходящих в металле в ходе охлаждения после достижения им температуры плавления (Kirkpatrick, Gelatt, Vecchi, 1983). Этот метод является модификацией вероятностного метода градиентного спуска. Известно несколько вариантов метода для различных задач оптимизации и в частности для решения задачи маршрутизации транспорта. Рассмотрим общую идею данного метода. В первую очередь необходимо определить понятие окрестности решения. В окрестность входят те решения, которые могут быть получены из решения путём выполнения фиксированного набора элементарных преобразований. Преобразования могут различаться для разных вариантов алгоритма. Алгоритм является итеративным. Он начинается с выбора опорного решения задачи, которое на первой итерации считается текущим. Из окрестности текущего решения. на шаге случайным образом выбирается новое решение. Выбранное решение становится текущим со следующей вероятностью:

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

Что означает: если стоимость нового решения лучше текущего, оно принимается текущим. В противном случае решение принимается с вероятностью, заданной функцией. Правило, используемое для определения, называется «охлаждающее расписание» (cooling schedule). Начальное значение задаётся равным и после каждой итерации корректируется коэффициентом б (0 < б < 1) умножением. Таким образом уменьшается вероятность выбора наихудшего решения.

Алгоритм останавливается после заданного числа итераций.

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

Детерминированный отжиг.

Алгоритм детерминированного отжига работает на основе алгоритма имитации отжига, но для принятия решения о следующем текущем положении используется явно детерминированные критерии выбора решения. Существует 2 основных подхода детерминированного отжига: алгоритм порогового принятия (Dueck, Scheurer, 1990) и алгоритм хода от рекорда к рекорду (Dueck, 1993).

Для алгоритма порогового принятия новое решение становится текущим, если, где — величина порога, параметр, который указывается пользователем.

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

Генетический алгоритм.

Генетические алгоритмы (genetic algorithm) — это алгоритмы, которые ищут решение для аналитически трудно решаемых задач, используя механизмы, которые имитируют биологическую эволюцию, поведение особей в живой природе: наследование, скрещивание, мутация, отбор (Holland, 1975).

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

• 1. С помощью оператора селекции выбираются два родителя и .
• 2. Оператором скрещивания (crossover operator) порождается решение-потомок на основе решений-родителей.
• 3. Полученный потомок подвергается «мутациям», которые представляют собой небольшие стохастические модификации данного решения.
• 4. Новый потомок добавляется в популяцию, а решение с наихудшим показателем приспособленности (значением целевой функции) из популяции удаляется.
• 5. Процесс повторяется до выполнения критерия остановки.

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

Для решения поставленной задачи маршрутизации транспорта был выбран метод роевого интеллекта, а именно алгоритм стаи рыб. Он является одним из новых эвристических алгоритмов. Данный метод хорошо зарекомендовал себя в решении некоторых оптимизационных задач. Однако такой метод не был использован для решения задач маршрутизации транспорта, этим и обусловлен выбор метода решения поставленной задачи.