автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Эффективные алгоритмы планирования транспортировки продукции

На правах рукописи

Сластников Сергей Александрович

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

05.13.01 - «Системный анализ, управление и обработка информации»

(управление)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

5 Фс.'В 2015

Москва 2014

005558502

Работа выполнена на кафедре «Кибернетика» Московского института электроники и математики Национального исследовательского университета «Высшая школа экономики».

Научный руководитель: Белов Александр Владимирович,

кандидат технических наук, доцент, декан факультета Прикладной математики и кибернетики МИЭМ НИУ ВШЭ

Официальные оппоненты: Лупян Евгений Аркадьевич,

доктор технических наук, заместитель директора ФГБУН «Институт космических исследований» РАН

Фролов Евгений Борисович, доктор технических наук, профессор, кафедра «Информационные технологии и вычислительные системы» МГТУ «Станкин»

Ведущая организация: ФГБУН «Вычислительный центр им. А. А.

Дородницына» Российской академии наук

Защита состоится 10 марта 2015 года в 11:00 часов на заседании диссертационного совета Д002.086.02 Федерального государственного бюджетного учреждения науки Институт системного анализа Российской академии наук (ИСА РАН) по адресу: 117312, Москва, проспект 60-летия Октября, 9.

С диссертацией можно ознакомиться в библиотеке ИСА РАН.

Электронные версии диссертации и автореферата размещены на официальном сайте ИСА РАН http://www.isa.ru.

Электронная версия автореферата отправлена для размещения на официальном сайте ВАК Министерства образования и науки РФ по адресу referat_vak@mon.gov.ru_декабря 2014 года.

Отзывы и замечания по автореферату в двух экземплярах, заверенные печатью, просьба высылать по адресу 117312, Москва, проспект 60-летия Октября, 9, ИСА РАН, диссертационный совет.

Автореферат разослан дьлЬхрд 201,£года.

Ученый секретарь

диссертационного совета Д002.086.02 л О

д.т.н., профессор Пропой А.И.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

• транспортные средства, осуществляющие перевозку, состоят из одной или нескольких раздельных секций;

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

На практике подобные ограничения встречаются в задачах развозки нефтепродуктов, некоторых видов спиртов (в частности, бутилового спирта) и сжиженных газов и обусловлены соображениями безопасности транспортировки.

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

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

Задачами нахождения маршрутов развозки продукции минимальной стоимости с одного склада множеству клиентов интенсивно занимаются с тех пор, как ее впервые поставил Данциг в 1959 году. Она является обобщением известной задачи коммивояжёра и, следовательно, принадлежит к классу NP-полных задач. Сначала активно развивались точные методы решения, идеи которых были заимствованы из методов решения задачи коммивояжера. Среди них можно выделить методы ветвей и границ (Augerat Р., 1995; Rinaldi G., 1989; Меламед И.И., Сигал И.Х., 1997), динамического программирования (Christofides N., Mingozzi A., Toth P., 1981) и целочисленного линейного программирования (Desrochers М., Laporte G., Nobert Y., 1985; Desrosiers J., Solomon M., 1992). Однако, начиная уже с 60-х годов, основные усилия были брошены на разработку приближенных алгоритмов — эвристик. Их можно разбить на 3 большие группы: конструктивные алгоритмы (Clarke G., Wright J., 1964; Solomon M., 1987), двухфазные (Gillett В., Miller L., 1974; Fisher M., Jaikumar R., 1981) и улучшающие алгоритмы (Kinderwater G., Savelsbergh M., 1997). Метаэвристические алгоритмы начали активно разрабатываться после 1990-х годов. Большинство известных метаэвристик были предложены на основе идей, возникших при наблюдении процессов живой и неживой природы (Glover F., 1989; Dueck G., 1993; Gendreau M., Hertz A., Laporte G., 1994; Dorigo M., Gambardella L.M., 1997; Курейчик B.M., 2002; Bräysy O., Gendreau M., 2008; Nguyen Q.C., Ong Y.S., Lim M.H., 2009).

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

правилами перевозки. Для достижения указанной цели были поставлены следующие задачи:

- исследование существующих методов конструирования маршрутов в задачах развозки продукции;

— конструирование эффективных алгоритмов построения (суб)оптимальных маршрутов транспортных средств на основе существующих подходов;

- адаптация построенных алгоритмов под специфические ограничения транспортировки;

— проведение вычислительных экспериментов для подтверждения эффективности разработанных алгоритмов;

— создание программной библиотеки, реализующей предложенные алгоритмы;

- разработка архитектуры системы планирования доставки продукции;

- проектирование интерфейса рабочего места диспетчера, отвечающего за транспортировку.

Методика исследования. В диссертации были использованы методы математического моделирования, итерационные методы дискретной оптимизации, методы математической статистики и объектно-ориентированного программирования.

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

Практическая и теоретическая значимость. Теоретическая ценность исследования заключается в том, что предложенная модификация алгоритма

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

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

Основные защищаемые положения:

1. Модификация метаэвристического алгоритма муравьиных колоний для решения задачи маршрутизации транспорта с ограничениями грузоподъемности и подтверждение его эффективности.

2. Зависимости управляющих параметров алгоритма от числа клиентов задачи.

3. Двухфазный алгоритм, основанный на предложенной модификации.

4. Реализация предложенных алгоритмов в виде программной библиотеки.

5. Архитектура системы планирования доставки продукции.

Внедрепие результатов работы

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

2. Полученные в диссертации результаты использованы в учебном процессе на кафедре «Кибернетика» МИЭМ НИУ ВШЭ в рамках дисциплин «Корпоративные информационные системы», «Проектирование информационно-управляющих систем».

3. Полученные в диссертации результаты использованы в учебном процессе в институте ИБС НИТУ «МИСиС» на кафедре «Информационные бизнес системы» в рамках дисциплины «Архитектура предприятия и проектирование КИС».

Апробация результатов. Основные положения и отдельные результаты были представлены на конференциях:

1. VIII Всероссийская научно-практическая конференция (с участием стран СНГ) «СИСТЕМЫ АВТОМАТИЗАЦИИ в образовании, науке и производстве» — Новокузнецк, 2011 г.

2. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ — Москва, 2011 г.

3. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ — Москва, 2012 г.

4. Четвертая ежегодная научно-практическая конференция «Информационные бизнес-системы» — Москва, 2012 г.

5. International Scientific-Practical Conference «Innovative information technologies» — Prague, 2012 г.

6. Международная научно-практическая конференция «Инновации на основе информационных и коммуникационных технологий» — Сочи, 2012 г.

7. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ НИУ ВШЭ - Москва, 2013 г.

8. 2nd International Conference on Information Technology and Quantitative Management, ITQM - Moscow, 2014 r.

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

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения и списка литературы. Работа содержит 112 страниц, включает в себя 23 рисунка и 3 таблицы. Список литературы состоит из 93 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы диссертационной работы, сформулированы цели работы, методика исследования, научная новизна, практическая и теоретическая значимость, достоверность полученных

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

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

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

В разделе 1.2 приведен обзор существующих программных систем управления транспортировкой. На основании этого обзора выявлены недостатки таких систем. Один из них состоит в том, что автоматическое осуществление маршрутизации заказов не гарантирует оптимизацию транспортных расходов, так как используемые алгоритмы скрыты и не могут быть проанализированы. Кроме того, большинство из этих систем являются дополнительными модулями к системам класса ЕЯР (планирование ресурсов предприятия) и/или \VAfS (систем управления складом), что предполагает их совместное использование и ограничивает возможности для интеграции. Этим отчасти объясняется тот факт, почему данные решения с богатым набором функциональных возможностей не получили должного признания в России, а положительные опыты их практического внедрения единичны.

В разделе 1.3 в качестве примера приведена постановка задачи развозки нефтепродуктов от нефтебаз до автозаправочных станций. Опишем ее:

• имеется N нефтебаз, с которых М видов топлива развозятся по п АЗС;

• задан неотрицательный спрос Яц — ¿-ой АЗС на топливо типа у (¿=1,...,л,

/=1 ,-М)\

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

8

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

• бензовоз выходит на линию из автопарка и возвращается в парк, количество автопарков равно К, в парке £ имеется бензовозов (£=1,...,£);

• длины маршрутов от автопарков до нефтебаз, от нефтебаз до АЗС и между всеми АЗС заданы соответствующими матрицами 4 (£ = 1,7 =1,...,Л0, < (г = 1,...,ЛГ, _/' = 1,...,и), а\ (/,/ = 1,...,«).

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

Кроме того, в 1.3 показано, что данную задачу (со многими видами продукции) можно свести к задаче развозки одного вида продукции, если ввести «фиктивных клиентов» и использовать ограничение, запрещающее частичный слив из бензовоза. Таким образом, поставленная задача развозки нефтепродуктов от нефтебаз до АЗС (размерности п) сводится к задаче маршрутизации транспорта (размерности М -п).

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

Задан граф С=(У, А, О), где V = {у0,...,у,} — множество вершин (у0 — склад, остальные вершины — клиенты); А — набор дуг, соединяющих соответствующие вершины графа; О = , = 0,1,...,«} — множество

неотрицательных чисел, которые чаще всего имеют смысл длины пути, времени или стоимости перевозки по дуге между вершинами V, и уу (далее для краткости будем называть их просто ( и _/'), их можно рассматривать как обобщение всех видов затрат на перевозку продукции из £ в Для клиента в вершине £ (клиента £) задан неотрицательный спрос с,, на некую продукцию или товар. На складе

имеется т транспортных средств, грузоподъёмность каждого из которых ограничена величиной Ск (к = \,...,т). Для задачи заданы следующие ограничения:

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

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

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

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

• нахождение оптимальных или субоптимальных решений для задачи развозки продукции (в том числе с особыми условиями транспортировки);

• возможность ее применения независимо от способа организации логистической цепочки доставки продукции;

• инвариантность относительно используемых других информационных систем.

Во второй главе представлен обзор и анализ методов решения задачи маршрутизации транспорта (ЗМТ).

В разделе 2.1 приведена классификация существующих методов решения. Их можно разбить на:

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

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

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

Подробное описание методов в каждой группе приводится в разделах 2.3 - 2.5.

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

т п и

->т!п а)

4=1 ,=0 у=0

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

Ук = 1,...,т, (2)

1=1 ]=о

Ук = \,...,т, (3)

м

¿Х*<1 Чк = 1,...,т, (4)

1=1

т п

У/ = 1,...,«, (5)

У/г = 1,...,77, Ук = 1,...,т, (6)

¿=0 /=0

Х*е{0,1} 4^ = 0Ук = \,...,т, (7)

Х*=0 VI =0,...,и, Vfc=l,...,m, (8)

если 5, ={(/,/)то

\/к = \,...,т 0 = 0,...,/):

Уо = Ум=°> (и-) = (Л,Л+,), (9)

Величина X,* принимает значение 1, если транспортное средство А: следует от клиента г к клиенту у, и 0 в противном случае. — множество пар вершин, определяющих маршрут машины к. Целевая функция (1) минимизирует стоимость всех маршрутов всех транспортных средств. Неравенство (2) гарантирует, что выполняются ограничения грузоподъемности каждого

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

В разделе 2.3 приведен обзор точных методов решения ЗМТ, которые могут быть разбиты на 3 большие группы: методы прямого поиска в дереве, динамическое программирование и целочисленное линейное программирование.

В разделе 2.4 приведен обзор классических эвристических алгоритмов для ЗМТ, среди которых: конструктивные алгоритмы — Кларка-Райта и Соломона; двухфазные алгоритмы — заметания и Фишера-Джекумера; улучшающие алгоритмы.

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

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

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

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

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

Источник -Муравейник

пищи

*> *> #> Ь) *>

<# <* •т * ?

Рис. 1. Динамика поведения муравьев при возникновении препятствия

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

Раздел 3.3 содержит описание классического алгоритма муравьиных колоний непосредственно для задачи маршрутизации транспорта с ограничениями грузоподъемности. Каждый «муравей» рассматривается как модель транспортного средства. Изначально, каждый «муравей» к начинает свой маршрут со склада, причем множество Мк — клиентов, включенных в его маршрут, пусто. Далее «муравей», находящийся у клиента ¡', выбирает следующего клиента у, который будет посещен, по вероятностному критерию ащшах[хш(л,„)13] с вероятностью <?0,

ичМк

J=\ (Ю)

5 с вероятностью 1 - ц0, где тш — количество феромона на пути между клиентами г и и; г\1и — величина, обратно пропорциональная расстоянию между клиентами (ее иногда называют «видимостью» между клиентами г и и, можно взять, например, Г|ш = 1 / с1ш); р — параметр, характеризующий относительную «важность» расстояния по сравнению с количеством феромона (при (3 = 0 муравей ориентируется только на

количество феромона); да (0<д0 <1) — вероятность использования детерминированного принципа при выборе следующего клиента; 5 — случайная величина, подчиняющаяся следующему закону распределения вероятностей:

Р {5 = *} = Л(/,л) =

^Оь,)" / X ^(П*)"» если 5 *Мк>

(11)

О, если я еМк,

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

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

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

т^ = (1-а)т;и+ат0, (12)

где а — параметр, характеризующий скорость испарения феромона, т0 — начальное значение феромона.

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

т^=(1-а)т;и+-р (13)

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

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

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

- успешное применение к множеству задач дискретной оптимизации (в том числе к задаче коммивояжера и ЗМТ);

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

- легкая адаптация к дополнительным ограничениям и динамическому изменению исходных данных.

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

ИтР*(А„) = 1, (14)

Я-* 00

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

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

В разделе 3.6 представлен модифицированный алгоритм муравьиных колоний для задачи маршрутизации транспорта с ограничениями грузоподъемности. Начальное значение феромона в нем определяется по формуле:

т0=((я + 1)1шп^)-1, (15)

"*)

где п — число клиентов. Кроме того, распределение вероятностей, которое определяет выбор следующего клиента, заданное формулой (11), изменяется следующим образом:

-после построения полного маршрута каждым «муравьем» предлагается запоминать лучший и худший маршруты одного муравья (среди всех муравьев), Ь и 7?, соответственно, затраты на этих маршрутах;

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

отношению затрат лучшего маршрута к худшему, т.е.

и \

(16)

-в остальных случаях ($ ^ распределение имеет вид

О, если 5 е Мк.

если

* (17)

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

1. Задаем значения параметров а, (3, ца.

2. Вычисляем начальное значение феромона т0 по формуле (15).

3. Цикл по всем итерациям (пока не выполнено правило остановки).

3.1. Цикл по всем «муравьям» (к=1,...,т).

3.1.1. Множество Мк клиентов, включенных в маршрут «муравья» к, полагаем пустым.

3.1.2. Цикл по одному «муравью» (пока не исчерпана грузоподъемность «муравья» к или не осталось необслуженных клиентов).

Пополняем множество М к (следующих клиентов для посещения) по формулам (10), (16), (17).

3.1.3. Конец цикла по одному «муравью».

3.1.4. Обновляем феромон локально по формуле (12).

3.2. Конец цикла по «муравьям».

3.3. Находим лучший и худший (среди всех «муравьев») маршруты.

3.3. Обновляем феромон глобально по формуле (13).

4. Конец цикла по итерациям.

5. Определяем лучший результат из всех итераций.

В разделе 3.7 представлен двухфазный модифицированный алгоритм, основанный на предложенной модификации из 3.6. Как было отмечено, муравьиные алгоритмы хорошо сочетаются с классическими методами локального поиска. Для улучшения качества получаемых решений можно воспользоваться каким-либо из таких методов. При этом нельзя допустить того, чтобы время работы алгоритма значительно увеличилось. Для предлагаемого алгоритма был выбран метод двухточечной локальной оптимизации. Он заключается в перестановке двух клиентов в рамках маршрута одного транспортного средства. Сложность данной процедуры не превосходит 0(п2), где п — число клиентов.

Таким образом, двухфазный алгоритм в целом описывается блок-схемой, представленной на рисунке 2.

Рис. 2. Блок-схема двухфазного модифицированного алгоритма

В разделе 3.8 описана реализация предложенных алгоритмов в виде программной динамической (shared object) библиотеки.

В 3.9 представлены результаты вычислительных экспериментов для задачи маршрутизации транспорта с ограничениями грузоподъемности. Для этого использовались так называемые модельные задачи из двух разных групп: Augerat et al. и Christofides and Eilon. Они представляют собой набор специально разработанных тестовых примеров, для которых известно оптимальное (или лучшее из полученных) значение целевой функции и минимальное число используемых транспортных средств. Клиенты и склад задаются декартовыми координатами на плоскости, расстояние между ними вычисляется по евклидовой метрике. Модельные задачи группы Augerat et al. разделены на три класса: А, В и Р. В задачах из класса А расположение клиентов и их спрос случайны, в задачах класса В клиенты расположены кластерно, т.е. их можно легко разделить на группы по их местоположению друг относительно друга. Задачи класса Р представляют собой модифицированные задачи других примеров из литературы. Было взято 16 примеров из группы Augerat et al. (5 задач класса А, 3 — класса В, 8 — класса Р) и 5 примеров из группы Christofides and Eilon (класс Е). Размерность этих задач (число клиентов) находится в пределах от 15 до 100.

Кроме реализованных в виде программной библиотеки модифицированных муравьиных алгоритмов, был также реализован классический алгоритм муравьиных колоний, описанный в 3.3. Программы исполнялись на персональном компьютере с процессором Dual-Core AMD Opteron 2.8 GHz. Время решения задачи составляло от 5 сек. (для 15-16 клиентов) до 10 мин. (для 100 клиентов).

В разделе представлены результаты решения всех рассматриваемых модельных задач двумя алгоритмами: классическим муравьиным алгоритмом (КМА) и модифицированным муравьиным алгоритмом (ММА).

Параметры алгоритмов a, qa варьировались в пределах от 0 до 1 с шагом 0.1, параметр р менялся от 0 до 5 с шагом 0.1 на отрезке [0;1] и с шагом 0.2 на интервале (1;5). Число итераций в обоих случаях устанавливалось равным 10000, число доступных транспортных средств принималось равным 20.

Из 21 задачи в 14 случаях модифицированным муравьиным алгоритмом были получены лучшие значения, чем классическим, в 3 случаях значения совпали, и лишь для 4 задач классический муравьиный алгоритм построил лучшее решение, чем предложенная модификация. Кроме того, для 20 задач оптимальное число используемых транспортных средств было получено обоими алгоритмами, а для одной задачи (Е-пЗО-кЗ) оптимальное число используемых транспортных средств было получено только предложенной модификацией. Аналогичным образом были получены результаты для двухфазного модифицированного муравьиного алгоритма (ДММА).

В таблице ниже представлены отклонения полученных в эксперименте значений целевой функции F от оптимальных Рор1 для всех трех версий

алгоритма (классического, модифицированного и двухфазного) по некоторым

модельным задачам. Отклонение было рассчитано по формуле

р_р*

Сар =-^-100%. (18)

Таблица 1. Результаты экспериментов

Задача вар, %

КМА ММА ДММА

А-п32-к5 7.7 6.7 5

А-п39-к5 11.1 10 5.5

А-п54-к7 12.6 10.1 8.2

В-п43-к6 6.2 6.3 5.4

В-п45-к5 5.9 5.5 4.1

Р-п23-к8 0.9 0.9 0.4

Р-п40-к5 11.7 11.3 7.7

Р-пбО-кЮ 11.1 11 7.6

Р-п76-к5 21 13.6 10

Е-пЗО-кЗ 5.9 4.9 4.2

Е-п51-к5 14.3 13.8 7.7

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

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

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

N = (23.10-1п(и)-64.78)-103 (при 15<и<100), (19)

где п — число обслуживаемых клиентов.

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

Коэффициент Л2 получился наибольшим (0.692) для степенной формы зависимости, поэтому в качестве формулы, оценивающей оптимальное значение параметра в зависимости от размерности задачи, было выбрано соотношение:

д0 =0.12-и044 (при 15<и<100). (20)

Для определения оценок функциональных зависимостей оптимальных значений параметров аир от размерности задачи были проведены дополнительные вычислительные эксперименты, в результате которых были получены уравнения: Р = -0.0007-л2 + 0.1015-л+ 0.4958 (при 15 <П <100), (21)

а = 0.0096 • п - 0.0406 (при 15 < п < 100). (22)

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

В ходе выполнения работы:

- на примере задачи развозки нефтепродуктов показано, как задачу транспортировки продукции с особыми условиями перевозки можно свести к задаче маршрутизации транспорта с ограничениями грузоподъемности;

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

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

- проведены вычислительные эксперименты, которые подтвердили эффективность предложенных алгоритмов;

- для предложенных алгоритмов найдены оценки функциональных зависимостей оптимальных значений управляющих параметров алгоритма от размерности задачи;

- разработана программная библиотека, реализующая предложенные алгоритмы;

- спроектирована архитектура системы планирования доставки продукции и выбрана технологическая платформа для ее разработки;

- разработан интерфейс рабочего места диспетчера, ответственного за транспортировку;

- результаты, полученные в ходе диссертационного исследования, использовались при разработке системы управления деятельностью рознично-сбытовой сети АЗК "GAS Complex System" и учебном процессе ИИБС НИТУ «МИСиС», МИЭМ НИУ ВШЭ, что подтверждается соответствующими актами.

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в журналах, входящих в перечень ВАК:

1. Сластников С.А. Анализ эвристических и метаэвристических методов для решения задачи распределения автомобильного топлива // Качество. Инновации. Образование. — 2012.-№ ц. с. 50-55.

2. Сластников С.А. Применение метаэвристических алгоритмов для задачи маршрутизации транспорта // Экономика и математические методы. - 2014. -№ 1. С. 117-126.

3. Сластников С.А. Решение задач маршрутизации транспорта методом муравьиных колоний // Мехатроника, автоматизация, управление. — 2014. — № 1.С. 18-21.

Другие публикации:

4. Сластников С.А. Анализ методов решения задачи маршрутизации транспорта // Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ: Тезисы докладов. — М.: МИЭМ, 2011. С.73-74.

5. Сластников С.А. Выбор методики интеграции логистической системы и ее применение // Труды VIII Всероссийской научно—практической конференции (с участием стран СНГ) AS'20U «СИСТЕМЫ АВТОМАТИЗАЦИИ в образовании, науке и производстве». Новокузнецк: Изд. центр СибГИУ, 2011. С. 291-295.

6. Сластников С.А. Проблема интеграции управления запасами и транспортировки автомобильного топлива // Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ: Тезисы докладов. -М.: МИЭМ, 2012. С.65-66.

7. Белов A.B., Сластников С.А. Использование концепции VMI в отрасли распределения автомобильного топлива // «Инновационные

информационные технологии»: Материалы международной научно-практической конференции. - М.: МИЭМ, 2012. С.561-563.

8. Сластников С.А. Проектирование системы планирования и диспетчирования доставки нефтепродуктов в рознично-сбытовых сетях АЗС // Материалы Всероссийской научно-практической конференции «Информационные бизнес-системы» — М.: АКАДЕМИЯ ИБС НИТУ «МИСиС», 2012. С.91-94.

9. Сластников С.А., Белов А.В. Разработка алгоритмического обеспечения и архитектуры автоматизированной системы диспетчирования доставки нефтепродуктов // Материалы международной научно-практической конференции «Инновации на основе информационных и коммуникационных технологий» — М.: МИЭМ НИУ ВШЭ, 2012. С. 222-226.

10. Сластников С.А. Применение алгоритма муравьиной колонии для решения задачи маршрутизации транспорта // Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ НИУ ВШЭ: Тезисы докладов. - М.: МИЭМ НИУ ВШЭ, 2013. С.62-63.

11. Belov A., Slastnikov S. A Metaheuristic Approach for the Problem of Motor Fuel Distribution // 2nd International Conférence on Information Technology and Quantitative Management, ITQM 2014, Volume 31. — Procedía Computer Science, 2014. P.143-150.

Подписано в печать 25.12.2014. Формат 60x90/16. Бумага офсетная. Гарнитура Тайме. 1,63 усл.-печ. л. Тираж 100 экз. Заказ № 134

Отпечатано в ООО «Гранат Принт» г.Москва, ул. Щёлковский проезд 9а тел.: (499) 343-36-51