научная статья по теме ПРИМЕНЕНИЕ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА Экономика и экономические науки

Текст научной статьи на тему «ПРИМЕНЕНИЕ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА»

ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2014, том 50, № 1, с. 117-126

МЕТОДЫ ОПТИМИЗАЦИИ

ПРИМЕНЕНИЕ МЕТАЭВРИСТИЧЕСКИХ АЛГОРИТМОВ ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА

© 2013 г. С.А. Сластников1

(Москва)

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

Ключевые слова: задача маршрутизации транспорта, метаэвристические алгоритмы, алгоритм муравьиных колоний.

Классификация JEL: C61, R42.

ВВЕДЕНИЕ

Проблема оптимизации поставок продукции всегда привлекала повышенное внимание экономистов, специалистов по логистике и математиков. Среди экономистов это обусловлено важностью транспортировки товаров и связанных с ней издержек (Бауэрсокс, Клосс, 2008, с. 47). Для математиков этот интерес вызван ее значительной сложностью. В литературе рассматриваемая задача известна как задача маршрутизации транспорта (Vehicle Routing Problem); ее не следует путать с транспортной задачей (иногда называемой задачей Монжа-Канторовича), которой посвящено много книг и работ, в том числе известная монография (Гольштейн, Юдин, 1969).

В разд. 1 дана постановка задачи, описана классификация существующих методов решения. В разд. 2 приведен краткий обзор основных метаэвристических методов: имитации отжига, детерминированного отжига, генетического алгоритма, метода поиска с запретами. В разд. 3 представлен классический алгоритм муравьиных колоний и его модификация. Результаты вычислительного эксперимента с использованием модифицированного алгоритма приведены в разд. 4.

1. ЗАДАЧА МАРШРУТИЗАЦИИ ТРАНСПОРТА

1.1. Постановка задачи. Задача маршрутизации транспорта (ЗМТ) является обобщением известной задачи коммивояжера и, следовательно, принадлежит к классу NP-полных задач. Это означает, что для нее не найден алгоритм решения за полиномиальное время и не доказано, что такого алгоритма не существует.

Опишем постановку задачи маршрутизации транспорта с ограничениями грузоподъемности (capacitated vehicle routing problem, CVRP). Задан граф G = (V, A, D), где V = {v0,...,vn} - множество вершин (v0 - склад, остальные вершины - клиенты); A - набор дуг, соединяющих соответствующие вершины графа; D = {dj, i, j = 0, 1,...,n} - множество неотрицательных чисел, которые чаще всего имеют смысл длины пути, времени или стоимости перевозки по дуге между вершинами vt и v (далее для краткости будем называть их просто i и j). Для исследования не

1 Автор выражает искреннюю благодарность Е.Г. Гольштейну за внимание к данной работе и ценные замечания по ее улучшению.

так важно конкретное содержание величин djj, поэтому их можно рассматривать как обобщение всех видов затрат на передвижение из j вj. В дальнейшем, если не оговорено противное, под dij будет пониматься расстояние между вершинами j и j. Для клиента в вершине j (клиента j) задан неотрицательный спрос е{ на некую продукцию или товар. На складе имеется т транспортных средств, грузоподъёмность каждого из которых ограничена числом Ск (к = 1,..., т). Также для задачи заданы следующие ограничения:

- каждый клиент должен быть посещён ровно один раз;

- местом начала и окончания всех маршрутов транспортных средств является склад.

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

Построим математическую модель задачи. Ее можно сформулировать следующим образом:

при ограничениях

т п п

р=///Х - т1п

к=1j=0]=0

пп

/сг /хк <Ск 6к = 1, ..., т,

j=1 j=о

п

/Х*- < 1 6к = 1, ..., т,

j = 1 п

/Хко< 1 6к = 1, ..., т,

j = 1 тп

//хк = 1 6 = 1, ..., п,

к=1j=0

jо = jl +1 = 0, (j, j) = (¡п jr+1), Г < I.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

/хкн - /хкк] = 0 6к = 1, ..., п, 6к = 1, ..., т,

j=0 j=0

Хк е {0,1} = 0, ..., п, 6к = 1, ..., т,

Хк = 0 6 = 0, ..., п, 6к =1, ..., т,

если 5к = {(', j): Хк = 1}, то

6к = 1, ..., т V(j, ]) е 5к ф 07(]р, ]р+1) е ^ (р = 0, ..., I ):

Таким образом, Хк принимает значение 1, если транспортное средство к следует от клиента j к клиенту j, и 0 в противном случае. Бк - множество пар вершин, определяющих маршрут машины к Целевая функция (1) минимизирует стоимость всех маршрутов всех транспортных средств. Неравенство (2) гарантирует, что выполняются ограничения грузоподъемности каждого транспортного средства. Ограничения (3) и (4) определяют, что каждое транспортное средство не может покинуть склад и вернуться на склад более 1 раза. Равенство (5) показывает, что каждый клиент обслуживается только одним транспортным средством и только один раз. Условие (6) означает, что если транспортное средство прибывает в вершину, то оно так же и покидает данную вершину. Условие (9) исключает возможность расщепления маршрута транспортного средства на несвязные циклы.

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

- точные методы;

- классические эвристические методы;

- метаэвристические методы.

Поскольку ЗМТ является обобщением задачи коммивояжера, идеи многих точных алгоритмов решения ЗМТ были заимствованы из методов решения этой задачи. До конца 1980-х годов наиболее эффективными точными методами решения ЗМТ являлись методы ветвей и границ, основанные на базовых комбинаторных упрощениях для задачи о назначениях, задачи минимального обхода графа, а также на методе сокращения пространства состояний. К настоящему времени предложены более сложные границы, основанные на лагранжевых релаксациях и аддитивном подходе, что позволило решать задачи существенно большей размерности (Toth, Vigo, 2002, p. 29). Однако для решения практических задач точные методы используются крайне редко, так как они применимы при некоторых дополнительных предположениях, чувствительны к любым дополнительным ограничениям, а время вычислений (в силу NP-полноты задачи) растет слишком быстро при увеличении размерности задачи.

Классические эвристики (разработаны в 1960-1990-х годах) можно разбить на следующие группы: конструктивные алгоритмы, двухфазные алгоритмы и улучшающие алгоритмы (Laporte, Semet, 1999).

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

Метаэвристические алгоритмы впервые начали разрабатываться после 1990-х годов. Большинство этих алгоритмов были предложены на основе идей, возникших при наблюдении процессов живой и неживой природы. В метаэвристиках акцент делается на проведение глубоких исследований в наиболее перспективных областях пространства решений. Эти методы обычно сочетают сложные правила поиска, структуры данных и рекомбинации решений. Качество получаемых с помощью этих методов решений, как правило, намного выше, чем у классических эвристик, но и время вычислений при этом возрастает. Более того, некоторые метаэвристики зависят от контекста конкретной задачи и требуют тонко настроенные управляющие параметры, что может сделать трудным их распространение на другие задачи. В некотором смысле, метаэвристики это не более чем усложненные улучшающие алгоритмы, и они могут рассматриваться как естественные усовершенствования классических эвристик (Laporte, Gendreau et al., 2000).

2. МЕТАЭВРИСТИЧЕСКИЕ АЛГОРИТМЫ

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

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

решение задачи x* на шаге i, произвольно выбирается новое решение xi+1 ! O(x*). Выбранное решение становится текущим со следующей вероятностью:

P =

1, если F(xi+1) < F(x*):

exp(-(F(xt+i)- F(x*))/6,.), если F(x.+1 )> F(x*),

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

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

2.2. Детерминированный отжиг. Несмотря на успешное применение в различных комбинаторных задачах методы имитации отжига часто работают медленно в силу стохастического механизма выбора текущего решения. Алгоритмы детерминированного отжига (deterministic annealing) пытаются преодолеть этот недостаток, используя детерминированные критерии выбора текущего решения. Наиболее известными из них являются алгоритм порогового принятия (Dueck, Scheurer, 1990) и алгоритм движения от рекорда к рекорду (Dueck, 1993).

В этих алгоритмах новое решение x.+1 ! O(x*) становится текущим, если F(x.+1) - F(x*) < 6, где 6 > 0 - величина порога (для алгоритма по

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком