Задача маршрутизации транспорта Целью задачи маршрутизации транспортных средств (Vehicle Routing Problem, vrp) является минимизация суммарной длины маршрутов транспортных средств, обслуживающих ряд клиентов [1], [2].

Вид материала

Задача

Содержание 2. Алгоритм муравьиных колоний 3. Применение алгоритма муравьиных колоний для решения задачи VRP 4. Локальная оптимизация маршрутов 5. Распараллеливание алгоритма муравьиных колоний 6. Вычислительный эксперимент

Подобный материал:

• Решение транспортных задач с использованием комбинированного генетического алгоритма*, 100.79kb.
• Аннотация программы дисциплины «Организация таможенного контроля товаров и транспортных, 43.72kb.
• Применение алгоритмов адаптивной маршрутизации в протоколе igrp, 37.51kb.
• Протоколы маршрутизации, 61.97kb.
• Плата за проверку технического состояния транспортных средств с использованием средств, 27.88kb.
• Правила охраны труда при эксплуатации и техническом обслуживании автомобилей и других, 888.02kb.
• Налог с владельцев транспортных средств и других самоходных машин и механизмов 37 Место, 260.74kb.
• Программа предмета «устройство и техническое обслуживание транспортных средств» раздел, 41.37kb.
• Вопросы организации сопровождения транспортных средств патрульными автомобилями Госавтоинспекции, 322.01kb.
• Ii перемещение через таможенную границу товаров и транспортных средств. Таможенные, 454.41kb.

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

А.Л. Игнатьев
Вычислительный центр РАН
ignatyev.alexander@gmail.com

1. Задача маршрутизации транспорта

Целью задачи маршрутизации транспортных средств (Vehicle Routing Problem, VRP) является минимизация суммарной длины маршрутов транспортных средств, обслуживающих ряд клиентов [1], [2]. Математически задачу можно представить как полный взвешенный граф _, где вершины представлены как _, а дуги как _. Транспортная база, являющаяся началом и концом каждого маршрута, представлена вершиной _, остальные вершины представляют _ клиентов. Для дуги (i, j) задано расстояние _. Для клиента i задан неотрицательный спрос _, грузоподъёмность каждого транспорта ограничена числом _. Также для задачи заданы следующие ограничения:

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

Частным случаем задачи VRP, когда спрос каждого клиента равен 0, является задача коммивояжера[3], [4].

Задача маршрутизации транспорта является комбинаторной задачей дискретной оптимизации, в которой число допустимых маршрутов экспоненциально растёт при увеличении числа клиентов, и принадлежит к классу сложности NP. Для таких задач использование эвристических алгоритмов представляется разумным, поэтому в данной работе мы рассмотрим применение алгоритма муравьиных колоний (Ant Colony Optimization, ACO).

2. Алгоритм муравьиных колоний

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

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

3. Применение алгоритма муравьиных колоний для решения задачи VRP

При решении задачи маршрутизации транспорта муравьи имитируют транспортные средства, маршруты строятся пошагово выбором следующего клиента до тех пор, пока не будут обслужены все клиенты. Изначально муравей стартует на базе и список клиентов, включённых в его маршрут, пуст. Муравей выбирает следующего клиента из списка доступных клиентов и обновляет свою текущую загрузку перед выбором следующего. Муравей возвращается в депо, когда достигнута его максимальная грузоподъёмность, либо все клиенты уже посещены. Суммарная длина _ рассчитывается как значение объектной функции полного маршрута k-го искусственного муравья. Алгоритм муравьиных колоний строит полный маршрут для первого муравья, перед тем как второй начнёт своё движение. Это продолжается до тех пор, пока заранее определённое число муравьёв _ не построят полный маршрут.

Выбор следующего клиента производится случайным образом на основе вероятностной формулы:




где _ - количество феромона на пути между текущей позицией i и возможной позиции j, _, параметры α и β соответственно означают относительные значимости количества феромона и расстояния при выборе следующего клиента. При _алгоритм вырождается в жадный, когда выбирается ближайший город без учета количества феромона.

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

Обновление следа феромона состоит из двух этапов: имитации испарения феромона и обновление следа в зависимости от качества получаемого решения. Имитация испарения феромона производится по следующей формуле:

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

Для дуги _ и маршрута _ количество откладываемого феромона задаётся в виде:




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



где m — количество муравьёв в колонии.

Таким образом, по сумме двух этапов количество феромона задаётся формулой:



4. Локальная оптимизация маршрутов

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

5. Распараллеливание алгоритма муравьиных колоний

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

A) начальная подготовка, включающая в себя загрузку и начальную инициализацию данных,

B) последовательное построение и улучшение созданных маршрутов, непосредственно сам вычислительный этап,

C) обработка и вывод полученных результатов.

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

6. Вычислительный эксперимент

Для вычислительного эксперимента были отобраны три задачи, описанные в работе [1]. В качестве тестовой системы использовалась рабочая станция с 4-ядерным процессором Intel Core 2 Quad 9550 2.83 ГГц и 4 Гб оперативной памяти.

В ходе численного эксперимента было отслежено влияние значений параметров α и β на качество получаемого решения.

Для первых трех наборов тестов была выбрана задача с 50 клиентами E051-05e, значение лучшего известного решения которой равно 524.61.

В первом наборе тестов проверялось влияние параметра α (параметр значимости количества феромона при выборе следующего клиента). Значения параметра α менялось от 1 до 10, остальные параметры были зафиксированы: β = 1, p = 0.2, O = 524. Таб. 1 показывает, что увеличение параметра α приводит к существенному ухудшению решений.

α	1	3	5	7	9
L	585.7	774.5	1229.3	1113.9	1145.9

Таб. 1. Влияние параметра α на качество решения L.


Во втором наборе тестов проверялось влияние параметра β (параметр значимости расстояния при выборе следующего клиента). Значения параметра β менялось от 1 до 10, остальные параметры были зафиксированы: α = 1, p = 0.2, O = 524. Как легко можно заметить из Таб. 2 изменение значения β практически не влияет на решение, лучшее решения достигается при значениях параметра 3 и 5.

β	1	3	5	7	9
L	585.7	567.4	567.3	576.2	583.0

Таб. 2. Влияние параметра β на качество решения L.

На рис. 1 графически отображены результаты предыдущих наборов тестов.




Рис. 1. Влияние параметров α и β на качество решения.


В таб. 3 приведены некоторые результаты для различных комбинаций α и β:

α	β	L
2	3	569.1
2	4	603.3
2	5	606.8
2	8	579.0
2	10	568.8
2	12	582.7
3	5	603.0
3	10	564.7
3	12	605.9
3	15	605.9

Таб. 3. Влияние комбинаций параметров α и β
на качество решения L.


В заключение приведем значения лучших решений, полученных для 3 тестовых задач:

Задача	Лучшее известное решение	Лучшее полученное решение
E051-05e	524.6	564.7
076-10e	835.3	956.5
E101-08eE	826.1	969.7

Таб. 4. Лучшие полученные решения.

При проведении вышеописанных наборов тестов на оставшихся двух примерах наблюдается аналогичное поведение: при увеличении параметра α решение задачи резко ухудшается, изменение β в свою очередь подобного эффекта не дает.

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

Задача	Время выполнения на 1 ядре, с.	Время выполнения на 4 ядрах, с.	Коэффициент масштабируемости (ускорение)
E051-05e	20	6	3.33
076-10e	70	18	3.88
E101-08eE	152	39	3.89

Таб. 5. Время выполнения на 1 и 4 ядрах.

7. Заключение

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

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

Литература

[1] Gendreau, M., Laporte, G., Potvin, J.-Y. Metaheuristics for the Capacitated VRP // The Vehicle Routing Problem, P. Toth and D. Vigo, eds., SIAM Monographs on Discrete Mathematics and Applications, 2002, pp. 129-154.

[2] Bell, J. E., Mcmullen, P. R. Ant colony optimization techniques for the vehicle routing problem // Adv. Eng. Inf. , V. 18, N. 1, 2004, 41-48.

[3] Игнатьев А.Л. Параллельные методы решения задачи коммивояжера // Труды 51-й научной конференции МФТИ «Современные проблемы фундаментальных и прикладных наук»: Часть IX. Инновации и высокие технологии. — М.: МФТИ. — 2008. — С. 4-6.

[4] A.L. Ignatyev, M.A. Posypkin, I.Kh. Sigal, Solving the Travelling Salesman Problem on Shared and Ditstributed Memory Systems // In Proc. of Optimization and applications (OPTIMA-2009), Petrovac, Montnegro, Sept. 21-25, 2009, pp. 37-38.