Особенности применения метода роевого интеллекта для решения задачи маршрутизации транспорта с ограничением грузоподъемности

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

Введение

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

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

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

1. Актуальность задачи маршрутизации транспорта в современном мире

1.1 Место задачи маршрутизации транспорта в логистических цепочках поставки продукции

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

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

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

В условиях рыночной конкуренции компаниям необходимо снижать свои расходы, для того чтобы обеспечить выгодное предложение потребителям. Среднее число расходов на логистику предприятий колеблется между 5 и 35% в зависимости от таких факторов, как: объем производимой продукции, географическое расположение, используемые ресурсы, отрасль, тип бизнеса и т.д. Это часть расходов уступает только затратам на материалы и сырье. Затраты на транспортную логистику могут составлять до 50% расходов на логистику в целом.

При рассмотрении экономики макроуровня можно заметить, что расходы на логистику также велики. Например, в США в 2014 году объем расходов на логистику составлял 8,3% ВВП. Из них более 60% расходов на логистику составляют расходы на транспортную логистику.

На сегодняшний день уровень логистических расходов в производственном комплексе РФ - один из самых высоких в мире. Общие внутренние и внешние затраты на транспорт и логистику составляют около 20% ВВП, тогда как в Китае - 15%, в странах Европы - 7-8%. При этом на 2013 год 23% перевозок приходится на автотранспорт.

Разница между российскими и мировыми показателями отчасти связана с обширностью территории страны, но в основном - низкой эффективностью ее транспортно-логистической системы. По оценке Всемирного банка, в 2014 году Россия заняла 90-е место из 160 по уровню логистической системы, соседствуя при этом в рейтинге с Шри-Ланкой и Уругваем. Характерно, что другие страны, также обладающие обширной территорией, расположились на значительно более высоких позициях в рейтинге: США заняли 9-е место, Канада - 12-е, Австралия - 16-е, Китай - 28-е, Бразилия - 65-е.

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

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

Более того, создание и использование эффективных оптимизационных алгоритмов способно улучшить транспортно-логистическую ситуацию в стране, а, следовательно, общее экономическое положение: «Если РФ снизит затраты на транспортировку и логистику до среднемирового уровня (порядка 11% ВВП), это высвободит порядка 180 млрд. долл. ежегодно. Для сравнения: ежегодные инвестиции в инфраструктуру составляют в России порядка 45 млрд. долл.».

1.2 Постановка задачи маршрутизации транспорта с ограничением грузоподъемности

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

В задаче присутствует такое понятие, как суммарная стоимость объезда последовательности вершин транспортным средством.

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

Для решения задачи и исследования эффективности алгоритмов не важно, что за ним стоит на самом деле.

Мы принимаем его как обобщение всех видов затрат на передвижение. В работе для простоты рассмотрим этот параметр как расстояние между клиентами.

Единственное ограничение связано с тем, что стоимость проезда (расстояние) не может быть отрицательной.

Рис. 1

Прежде всего сформулируем общую постановку ЗМТ.

1. Задаётся -- множество всех вершин. -- вершина, в которой начинаются и заканчиваются маршруты. Назовём её “депо”.

2. -- множество из n целевых вершин, которые нужно посетить.

3. Задаётся -- матрица стоимостей переезда между вершинами (расстояний); -- стоимость переезда (расстояние) между вершинами и .

4. Имеется автомобилей в парке.

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

Постановка задачи маршрутизации транспорта с ограничением грузоподъёмности транспортных средств.

1. Задаётся -- множество всех вершин. -- вершина, в которой начинаются и заканчиваются маршруты. Назовём её “депо”.

2. -- множество из n целевых вершин, которые нужно посетить.

3. Задаётся -- матрица стоимостей переезда между вершинами (расстояний); -- стоимость переезда (расстояние) между вершинами и .

4. Задаётся величина , которая является значением грузоподъёмности транспортных средств.

5. Задаётся множество чисел , где определяет величину потребности в товаре вершины . должно быть строго больше нуля.

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

Математическая постановка задачи маршрутизации транспорта с ограничением грузоподъёмности.

Минимизируем целевую функцию:

При следующих ограничениях:

Если то:

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

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

1.3 Алгоритмическая сложность задачи маршрутизации транспорта

Задача маршрутизации транспорта -- широко известная задача целочисленного программирования, которая относится к классу NP-трудных задач. Это означает, что вычислительная сложность задачи зависит от размера входных данных экспоненциально.

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

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

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

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

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

Впервые математическая модель для транспортной задачи была предложена 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. Процесс повторяется до выполнения критерия остановки.

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

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

3. Алгоритм стаи рыб для задачи маршрутизации транспорта

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

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

Основная идея алгоритма состоит в том, чтобы имитировать такое поведение рыб как: поиск еды, объединение в рой и следование за компаньонами. Каждая рыбка осуществляет локальный поиск для достижения глобального оптимума (Li 2003). Например, в природе рыба может обнаружить более питательную область путем индивидуального поиска или следования за другой рыбой, площадь с гораздо большим количеством рыбы обычно наиболее питательна.

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

3.1 Общая идея алгоритма

Рис. 5

Искусственная рыбка осуществляет внешнее восприятие с помощью представления, показанного на рис. 5. - это положение.

Рыбки в данный момент времени, - это видимое расстояние, - это видимая позиция в какой-то момент времени.

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

Положим, и , тогда этот процесс может быть выражен следующим образом:



Где - это случайные числа от 0 до 1, - длина шага, - оптимизируемая переменная (рассматриваемый параметр рыбки), - число переменных (параметров рыбки).

Модель искусственной рыбки включается в себя переменные и функции.

Переменные: - текущая позиция рыбки, - длина шага перемещения, - видимая дистанция, - число попыток (итераций??) и - это фактор толпы .

Функции - это основные поведения искусственной рыбки, а именно: AF_Prey, AF_Swarm, AF_Follow.

Рассмотрим поведение стаи рыб во время добычи пищи. Это значит, что следующие утверждения приведены для задачи на поиск максимума.

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

Рассмотрим основные поведения рыбок для поиска пищи:

1 AF_Prey.

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



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

маршрутизация математический логистический эвристический

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

2 AF_Swarm:

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

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



В противном случае выполняется поведение AF_Prey. Фактор толпы ограничивает масштаб стаи и больше рыб собираются только в лучшем месте. Это гарантированно означает, что рыбка движется к оптимуму на большом пространстве. То есть, фактор толпы ограничивает падение рыбок в локальный минимум, не позволяя всем рыбкам сплыться туда.

3 AF_Follow.

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

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

В противном случае выполняется поведение AF_Prey.

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

3.2 Применение алгоритма стаи рыб для задачи маршрутизации транспорта с ограничением грузоподъемности

Для удобства вспомним общую постановку задачи маршрутизации транспорта.

1. -- множество всех вершин. -- “депо”.

2. -- множество n целевых вершин для посещения.

3. -- матрица стоимостей переезда между вершинами; -- стоимость переезда между вершинами и .

4. - величина грузоподъёмности для транспортных средств.

5. Множество чисел , где - строго положительная потребность в товаре для вершины .

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

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

Процесс итеративный, где одна итерация - это один полный набор маршрутов. Количество итераций задается значением IterCount и равно:

IterCount =

В основе идеи алгоритма лежит то, что рыбки движутся к еде, максимизируя целевую функцию. В то время, как целевая функция (суммарное расстояние) задачи стремится к минимуму. Значит, для данной задачи «еда» - это функция, обратная расстоянию.

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

1. Для каждого ребра инициализируется матрица .

2. В течение IterCount количества итераций происходит:

2.1. Сбрасываются параметры рыбки, посещенные точки, первая рыбка помещается в .

2.2. Матрица не меняется.

2.3. Пока все клиенты не будут посещены повторяется:

2.3.1. Происходит поиск доступных клиентов : которых еще не посещали и которые подходят по ограничению грузоподъемности.

2.3.2. Если у рыбки хватает места:

2.3.2.1. Выбираются «лучших клиентов».

2.3.2.2. Из них с учетом вероятностей случайно выбирается следующий клиент, где вероятность (при движении из ):

2.3.2.3. Рыбка плывет к клиенту.

2.3.2.4. Клиент помечается как уже посещенный.

2.3.2.5. Совершенная дорога записывается в массив .

2.3.2.6. У рыбки обновляется оставшийся свободный вес.

2.3.3. Если у рыбки не хватает места:

2.3.3.1. Рыбка плывет в депо.

2.3.3.2. Совершенная дорога записывается в массив .

2.3.3.3. Заполненный массив сохраняется в список всех дорог на этой итерации.

2.3.3.4. Выбирается следующая рыбка и помещается в депо.

2.4. Когда все клиенты посещены последняя рыбка едет в депо от последнего клиента.

2.5. Совершенная дорога записывается в массив .

2.6. Заполненный массив сохраняется в список всех дорог на этой итерации.

2.7. Происходит обновление матрицы :

,

где - потребность груза на вершинах этого маршрута:

3. Оптимальный маршрут составлен, ответ выводится на экран

Блок-схема алгоритма представлена на рис. 6.

Рис. 6

Заключение

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

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

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

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

Литература

1. Кощеев И.С. Оптимизация доставки груза потребителям с учетом его размещения внутри транспортных средств на основе эвристических методов.

2. Кузнецов А.В. Руководство к решению задач по математическому программированию. Мн.: Вышэйшая школа.

3. Трофимов Д., Федуков А. Задачи маршрутизации транспорта

4. Буэрсокс Д.Дж. Логистика: интегрированная цепь поставок. М.: ЗАО «Олимп-Бизнес».

5. Волков М. Логистика в России: новые пути раскрытия потенциала.

6. Пожидаев М.С. Алгоритмы решения задачи маршрутизации транспорта

7. Сластников С.А. Применение метаэвристических алгоритмов для задачи маршрутизации транспорта.

8. Сластников С.А. (2012) Анализ эвристических и метаэвристических методов для решения задачи распределения автомобильного топлива.

Размещено на Allbest.ru

...