Автореферат (Эффективные алгоритмы планирования транспортировки продукции (на примере продуктов с особыми условиями перевозки)), страница 4

Задаем значения параметров , , q0 .2. Вычисляем начальное значение феромона0по формуле (15).3. Цикл по всем итерациям (пока не выполнено правило остановки).173.1. Цикл по всем «муравьям» (k=1,…,m).3.1.1. Множество M k клиентов, включенных в маршрут «муравья» k,полагаем пустым.3.1.2. Цикл по одному «муравью» (пока не исчерпана грузоподъемность«муравья» k или не осталось необслуженных клиентов).Пополняем множество M k (следующих клиентов для посещения) поформулам (10), (16), (17).3.1.3.

Конец цикла по одному «муравью».3.1.4. Обновляем феромон локально по формуле (12).3.2. Конец цикла по «муравьям».3.3. Находим лучший и худший (среди всех «муравьев») маршруты.3.3. Обновляем феромон глобально по формуле (13).4. Конец цикла по итерациям.5. Определяем лучший результат из всех итераций.В разделе 3.7 представлен двухфазный модифицированный алгоритм,основанный на предложенной модификации из 3.6. Как было отмечено,муравьиныеалгоритмыхорошосочетаютсясклассическимиметодамилокального поиска. Для улучшения качества получаемых решений можновоспользоваться каким-либо из таких методов. При этом нельзя допустить того,чтобы время работы алгоритма значительно увеличилось. Для предлагаемогоалгоритма был выбран метод двухточечной локальной оптимизации.

Онзаключается в перестановке двух клиентов в рамках маршрута одноготранспортного средства. Сложность данной процедуры не превосходит O(n 2 ) , гдеn — число клиентов.Таким образом, двухфазный алгоритм в целом описывается блок-схемой,представленной на рисунке 2.18Начало алгоритмаВычисление начального значения феромона0Инициализация следов феромона на всехучастках значением 0Встречен критерийостановки?ДАНЕТНЕТЕсть свободные ТС?ДАЕсть допустимыенеобслуженныеклиенты?НЕТДАВыбор клиента и добавление его в маршруттекущего ТСЛокальная оптимизация маршрута одного ТСЛокальное обновление феромонаВыбор лучшего маршрута одного ТС иглобальное обновление феромонаВозврат лучшего из всех решенийКонец алгоритмаРис. 2.

Блок-схема двухфазного модифицированного алгоритма19В разделе 3.8 описана реализация предложенных алгоритмов в видепрограммной динамической (shared object) библиотеки.В 3.9 представлены результаты вычислительных экспериментов для задачимаршрутизации транспорта с ограничениями грузоподъемности. Для этогоиспользовались так называемые модельные задачи из двух разных групп: Augeratet al. и Christofides and Eilon. Они представляют собой набор специальноразработанных тестовых примеров, для которых известно оптимальное (илилучшее из полученных) значение целевой функции и минимальное числоиспользуемых транспортных средств. Клиенты и склад задаются декартовымикоординатами на плоскости, расстояние между ними вычисляется по евклидовойметрике. Модельные задачи группы Augerat et al.

разделены на три класса: A, B иP. В задачах из класса A расположение клиентов и их спрос случайны, в задачахкласса B клиенты расположены кластерно, т.е. их можно легко разделить нагруппы по их местоположению друг относительно друга. Задачи класса Pпредставляют собой модифицированные задачи других примеров из литературы.Было взято 16 примеров из группы Augerat et al. (5 задач класса A, 3 — класса B, 8— класса P) и 5 примеров из группы Christofides and Eilon (класс E). Размерностьэтих задач (число клиентов) находится в пределах от 15 до 100.Кроме реализованных в виде программной библиотекb модифицированныхмуравьиныхалгоритмов,былтакжереализованклассическийалгоритммуравьиных колоний, описанный в 3.3.

Программы исполнялись на персональномкомпьютере с процессором Dual-Core AMD Opteron 2.8 GHz. Время решениязадачи составляло от 5 сек. (для 15–16 клиентов) до 10 мин. (для 100 клиентов).В разделе представлены результаты решения всех рассматриваемыхмодельных задач двумя алгоритмами: классическим муравьиным алгоритмом(КМА) и модифицированным муравьиным алгоритмом (ММА).Параметры алгоритмов0.1, параметр, q0 варьировались в пределах от 0 до 1 с шагомменялся от 0 до 5 с шагом 0.1 на отрезке [0;1] и с шагом 0.2 наинтервале (1;5). Число итераций в обоих случаях устанавливалось равным 10000,число доступных транспортных средств принималось равным 20.20Из 21 задачи в 14 случаях модифицированным муравьиным алгоритмомбыли получены лучшие значения, чем классическим, в 3 случаях значениясовпали, и лишь для 4 задач классический муравьиный алгоритм построил лучшеерешение, чем предложенная модификация.

Кроме того, для 20 задач оптимальноечисло используемых транспортных средств было получено обоими алгоритмами,а для одной задачи (E-n30-k3) оптимальное число используемых транспортныхсредств было получено только предложенной модификацией. Аналогичнымобразом были получены результаты для двухфазного модифицированногомуравьиного алгоритма (ДММА).В таблице ниже представлены отклонения полученных в экспериментезначений целевой функции F от оптимальных Fopt для всех трех версийалгоритма (классического, модифицированного и двухфазного) по некоторыммодельным задачам. Отклонение было рассчитано по формулеGapFFoptFopt(18)100%.Таблица 1.

Результаты экспериментовGap, %ЗадачаКМАММАДММАA-n32-k57.76.75A-n39-k511.1105.5A-n54-k712.610.18.2B-n43-k66.26.35.4B-n45-k55.95.54.1P-n23-k80.90.90.4P-n40-k511.711.37.7P-n60-k1011.1117.6P-n76-k52113.610E-n30-k35.94.94.2E-n51-k514.313.87.721Как видно из таблицы, эффективность предложенной модификации и еедвухфазного варианта может в 2 раза превосходить эффективность классическогомуравьиного алгоритма (с точки зрения отклонения от оптимума).Одним из самых сложных вопросов при практическом применениимуравьиныхалгоритмовявляетсяопределениеоптимальныхзначенийуправляющих параметров алгоритма.

В используемых нами муравьиныхалгоритмах критерием остановки является заранее предопределенное числоитераций, которое напрямую связано с допустимым временем решения задачи.Число итераций для задачи будем считать оптимальным в том случае, когдазначениецелевойфункцииперестаетуменьшатьсяболеечемна1%(относительно текущего значения). По данному критерию было определенооптимальное число итераций (в интервале от 0 до 50000 с шагом 500) для каждойиз 21-ой рассматриваемой модельной задачи.

На основании полученных данныхбыло построено корреляционное поле зависимости оптимального числа итерацийN optотчислафункциональномклиентов.видеБылисделанырассматриваемойразличныезависимости,предположениядляовычислениякоэффициентов соответствующих уравнений использовался метод наименьшихквадратов. Поскольку коэффициент детерминации R 2 оказался наибольшим(равным 0.546) для логарифмической формы зависимости, в качестве формулы,приближенно определяющей оптимальное число итераций алгоритма поразмерности задачи, было выбрано соотношение:N(23.10 ln(n) 64.78) 103 (при 15 n 100 ),(19)где n — число обслуживаемых клиентов.Наоснованииданныхвычислительногоэкспериментабылотакжепостроено корреляционное поле зависимости оптимального значения параметраq0 ,характеризующегосоотношениемеждудетерминированнымистохастическим принципом выбора следующего клиента при построениимаршрута, от размерности задачи.

Аналогично были найдены уравнения дляразных форм зависимости и соответствующие коэффициенты детерминации.22КоэффициентR2получился наибольшим (0.692) для степенной формызависимости, поэтому в качестве формулы, оценивающей оптимальное значениепараметра q0 в зависимости от размерности задачи, было выбрано соотношение:q00.12 n0.44 (при 15 n 100 ).(20)Для определения оценок функциональных зависимостей оптимальных значенийпараметровиот размерности задачи были проведены дополнительныевычислительные эксперименты, в результате которых были получены уравнения:0.0007 n 2 0.1015 n 0.49580.0096 n 0.0406(при 15 n 100 ),(при 15 n 100 ).(21)(22)В 3.10 представлены выводы по третьей главе, в которых отмечено, чтоэффективностьпредложенныхмодификацийподтвержденарезультатамивычислительных экспериментов. Кроме того, удалось провести процедуруоптимизации и найти вид оценок функциональной зависимости управляющихпараметров предложенного алгоритма от размерности задачи.

Тем самымчастично преодолен один из существенных недостатков муравьиных алгоритмов вцелом, связанный с выбором управляющих параметров.В четвертой главе проектируется система планированиядоставкипродукции. В разделе 4.1 описаны требования, которые к этой системепредъявляются. В 4.2 предложена архитектура такой системы. В разделе 4.3описана платформа, выбранная для разработки системы, удовлетворяющаятребованиям и поддерживающая предложенную архитектуру. В 4.4 представленспроектированный интерфейс системы.23ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫВ ходе выполнения работы:на примере задачи развозки нефтепродуктов показано, как задачутранспортировки продукции с особыми условиями перевозки можносвести к задаче маршрутизации транспорта с ограничениямигрузоподъемности;разработан алгоритм решения задачи маршрутизации транспорта сограничениямигрузоподъемностинаосновемодификацииметаэвристического алгоритма муравьиных колоний;разработан двухфазный модифицированный алгоритм того жепорядка сложности, улучшающий качество полученных решений;проведены вычислительные эксперименты, которые подтвердилиэффективность предложенных алгоритмов;для предложенных алгоритмов найдены оценки функциональныхзависимостей оптимальных значений управляющих параметровалгоритма от размерности задачи;разработана программная библиотека, реализующая предложенныеалгоритмы;спроектированаархитектурасистемыпланированиядоставкипродукции и выбрана технологическая платформа для ее разработки;разработан интерфейс рабочего места диспетчера, ответственного затранспортировку;результаты, полученные в ходе диссертационного исследования,использовались при разработке системы управления деятельностьюрознично-сбытовой сети АЗК "GAS Complex System" и учебномпроцессе ИИБС НИТУ «МИСиС», МИЭМ НИУ ВШЭ, чтоподтверждается соответствующими актами.СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ24Публикации в журналах, входящих в перечень ВАК:1.