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

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

КОЩЕЕВ Иван Сергеевич

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

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

1 7 Ш

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

Уфа-2015

005570145

005570145

Работа выполнена на кафедре вычислительной математики и кибернетики Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Уфимский государственный авиационный технический университет»

Научный руководитель: д-р техн. наук, профессор

Валеева Аида Фаритовиа

Официальные оппоненты: д-р физ.-мат. наук, профессор

Спивак Семен Израилевпч Башкирский государственный университет, заведующий кафедрой математичес кого моделирования

д-р техн. наук, профессор Фроловский Владимир Дмитриевич

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

Ведущая организация: ФГАОУ ВПО «Уральский федеральный универ-

ситет имени первого Президента России Б. Н. Ельцина», г. Екатеринбург

Защита диссертации состоится 17 июня 2015 г. в 1000 часов на заседании диссертационного совета Д 212.288.03 на базе ФГБОУ ВПО «Уфимский государственный авиационный технический университет» по адресу: 450000, г. Уфа, ул. К. Маркса, 12.

С диссертацией можно ознакомиться в библиотеке ФГБОУ ВПО «Уфимский государственный авиационный технический университет» и на сайте www.ugatu.su.

Автореферат разослан «15» мая 2015 года.

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

диссертационного совета, /7 /М

д-р техн. наук, проф. ' В.В.Миронов

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

Актуальность темы исследования

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

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

1. Маршруты доставки для ТС.

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

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

Степень разработанности темы исследования

В ходе диссертационного исследования использовались работы отечественных и зарубежных авторов (JI. В. Канторович, В. А. Залгаллер, Э. А. Мухачева, И. В. Романовский, Ю. А. Кочетов, В. В. Мартынов, А. А. Петунин, В. М. Верхо-туров, А. Ф. Валеева, G. Sheithauer, Н. Dykhoff, М. Hifi, R. M'Hallah, Y. G. Stoyan, P. Gilmore, R. Gomory, G. Washer, M. Gany, D. Johnson, P. Toth, D. Vigo, G. Laporte, G. B. Dantzig и другие). Несмотря на значительные успехи в решении задач оптимизации (как задачи маршрутизации, так и задачи размещения) данные задачи нельзя считать решенными. Так актуальными остаются исследования, направленные на решение задач промышленных предприятий, одновременное решение задач маршрутизации и размещения большого числа грузов различной геометрической формы внутри транспортных средств.

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

Задачи исследования

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

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

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

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

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

5. Исследовать эффективность предложенных методов и алгоритмов с помощью численных экспериментов.

Научная новизна результатов работы

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

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

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

Теоретическая и практическая значимость

Теоретическую значимость имеют следующие результаты:

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

2. Результаты численных экспериментов, которые показали эффективность предложенных алгоритмов на известных тестовых наборах для класса ЗЬ-С\ГЯР задач маршрутизации.

Практическую значимость имеют следующие результаты:

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

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

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

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

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

На защиту выносятся:

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

2. Эвристический метод, основанный на процедурах эволюционного алгоритма и гиперэвристическом алгоритме, на основе «роевого» алгоритма, для решения задачи размещения груза при наличии технологических ограничений.

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

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

Степень достоверности и апробация полученных результатов

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

Работа выполнялась при поддержке фанта Российского фонда фундаментальных исследований (РФФИ), проект РФФИ № 13-07-00579 (2011-2013).

Результаты работы и отдельные ее разделы докладывались и обсуждались на следующих конференциях и семинарах: Международная конференция "Компьютерные науки и информационные технологии" (С81Т), Уфа, 2010-2012; Всероссийская конференция «Математическое программирование и приложения», Екатеринбург, 2011; VII Всероссийская зимняя школа аспирантов и молодых учёных, Челябинск, 2012; Зимняя школа для аспирантов и молодых ученых, Уфа, 2012, 2014; Международная молодежная конференция "Интеллектуальные технологии обработки информации и управления", Уфа, 2012; V Всероссийская конференция "Проблемы оптимизации и экономические приложения", Омск, 2012; Российская конференция "Дискретная оптимизация и исследование операций" (1ХХЖ-2013), Новосибирск, 2013; Международная конференция «Информационные технологии интеллектуальной поддержки принятия решений», Уфа, 2013; 1п-

ternational Conference «Optimization and applications» (OPTIMA-2013), Petrovac, Montenegro, 2013.

Публикации

По теме диссертации опубликовано 17 работ: 8 статей, в том числе 4 в рецензируемом журнале из перечня ВАК и 9 статей в сборниках трудов конференций, получено одно свидетельство регистрации программы для ЭВМ.

Объем и структура работы

Диссертация состоит из введения, четырех глав, выводов и списка литературы. Работа изложена на 138 страницах, содержит 38 рисунка и 12 таблиц. Библиографический список включает 179 наименований и занимает 16 страниц.

Благодарности. Автор выражает глубокую благодарность заведующему кафедрой вычислительной математики и кибернетики УГАТУ, доктору технических наук профессору Н. И. Юсуповой за консультации в области системного анализа.

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

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

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

1. Грузоподъемность используемых ТС, грузоподъемность поддонов, грузоподъемность погрузчика, разрешенная нагрузка на оси ТС

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

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

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

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

Для решения задачи размещения грузов внутри ТС был выбран эволюционный алгоритм ЕА в сочетании с декодером ABLP3D в связи с тем, что:

1. Эволюционные алгоритмы показывают хорошие решения для различных задач оптимизации.

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

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

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

Исходная информация задач может быть задана наборами следующего вида: G = (V, А) - граф с множеством вершин К и множеством дуг А\ V= {1.....п} - множество клиентов (вершин);

(W, L, Н, Q) - характеристики используемого ТС, где W- ширина используемого ТС, L - длина используемого ТС, Я - высота используемого ТС, Q - грузоподъемность ТС;

(wpal, Ipal, hpal, mpal, qpal, hpalmax) - характеристики используемых поддонов, wpal, Ipal, hpal — габариты поддонов, mpal — масса поддона, hpalmax — максимальная разрешенная высота

(rcfr тс к ) - характеристики к-то цилиндра, rch hck - радиус и ширина, тс к - масса цилиндра;

(wPk>lPk-hPk-mPk^-характеристикик-то параллелепипеда ; (dmcik)~ обозначает, что к-й цилиндр необходимо доставить i-му заказчику ; (dmpa) - означает, что к-й параллелепипед необходимо доставить i-му заказ-чкику;

Сд— время в пути между вершинами z и j; cost - стоимость часы аренды ТС. Введем ряд обозначений:

Xiji - переменная логического типа, принимающая значение 1, если ТС / перемещается в направлении от пункта i к пункту у, и 0 в противном случае,/, у е[1,и];

dp = (dp рц ) - элемент матрицы означает, что поддон р необходимо доставить в город i транспортным средством t, t~l,...,m;

dpc = (dpcpi) — элемент матрицы означает, что цилиндр i должен быть расположен на под доне р;

dpp = (dpppi)— элемент матрицы означает, что параллелепипед i должен

быть расположен на поддоне р;

(Ipal, wpal, hpal, mpal, qpal, hpalmax) - характеристики используемого поддона, где Ipal - длина поддона, шириной wpal, допустимой высотой hpal, массой mpal, грузоподъемностью qpal;

ра1={ра1р }, р=1, ...,пра1 - множество поддонов, где ра1р=(хра1, ура1, гра1) — координаты поддона, которые отсчитываются от ближнего нижнего правого края ТС. Ниже приведен поясняющий рисунок (Рисунок 1);

(хск.уск.гсь) - координаты к-го цилиндров (будем считать, что координата цилиндра — это координата центра его нижнего основания). Координаты цилиндров и параллелепипедов отсчитываются от поддона. Ниже приведен поясняющий рисунок (Рисунок 2);

(хРк>УРк>2Рк) ~ координаты к-го параллелепипеда, под которыми будем подразумевать координаты левого нижнего дальнего угла.

Рисунок 2 - Координаты предметов на поддонах

Требуется минимизировать следующие функции: п п т

X Т,сухт-*т1п; (1)

¿=1 у=1 ,=1

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

£ xijt = Xхjit £ 1.v' = 1.....m;

jeV jeV V '

спрос клиентов должен быть удовлетворен: т rtpal

Ё S HxijtdPpjtdPcpk =dmcfg-ykel...\Itemcy! \,VjeV/{0}, t-\ieV p

, (3)

m npal

X X Y,xijtdPpjtdPPpk = dmpjg У к e 1... | ltempal [,Vj &V/{ 0); f=lieP p

количество груза, размещенного в ТС t, не должно превышать грузоподъемности ТС:

npal npar npalncyl

Z X X "LxijtdPpjtdPcpkmck +Z Z I HxijtdPpjtdPPpkmPk ieV jeV p=1 k=1 ieF /eF p=l *=1

npal (4)

+ ZS X xijtdPkjt mpal <2.Vi = l.....от;

fc=l/eF yeK

удовлетворяются условия размещения продукции в ТС f:

1. Условие ортогональности поддонов

2. Поддоны не должны выходить за границы ТС

3. Поддоны не перекрываются друг с другом

4. Грузы на поддоне не должны превышать грузоподъемность поддонов

5. Условие ортогональности цилиндров, параллелепипедов

6. Цилиндры, параллелепипеды не выходят за границы поддонов

7. Грузы не перекрываются друг с другом

8. Должна соблюдаться нагрузка на оси ТС

Для рационального размещения груза в ТС разработан метод ABLPю, являющийся модификацией методов ABLP [М. Hifi, К M'Hallah] и ABLP*[Р. Файзрах-манов]. Основную идею алгоритма можно представить следующим образом:

1. Поместить первый предмет в угол контейнера, совпадающий с началом координат

2. Для всех неразмещенных предметов выполнить:

2.1. Для всех размещенных в контейнер предметов

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

3. Для всех пар размещенных предметов

3.1. Получить допустимые позиции П2 относительно пар уже размещенных предметов

4. Получить список допустимых позиций П*, удалив позиции, которые не обеспечивают допустимое размещение;

5. Удалить недопустимые позиции из списка niU П2,

6. Поместить предмет в лучшую позицию из списка П

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

1. Пусть первым в контейнер помещается параллелепипед. Если следующий предмет — цилиндр, то позиции его расположения относительно параллелепипеда определяются следующим образом: параллелепипед очерчивается плоскостями, проходящими через его стороны. Таким образом, в плоскости 7.=граг образуются позиции 1-4 (Рисунок 3) для размещения цилиндра, а в плоскости 2^грап+крап -еще одна позиция 5.

1 (хс'ьус1,)

гр>

УР>

(*Р,.УА) / 5

\ у ! /

\

чЬ^

X

хр.

Рисунок 3 - Определение позиций цилиндра относительно параллелепипеда

2. Если первым в контейнер помещается цилиндр, а следующим - также цилиндр, то для размещения второго цилиндра относительно первого создаются позиции 1—4 (Рисунок 4), а также позиция 5.

хс, х

Рисунок 4 - Определение позиций цилиндра относительно цилиндра

3. Если первым в контейнер помещается параллелепипед, а следующим -также параллелепипед, то для размещения второго параллелепипеда относительно первого создаются позиции 1-4 (Рисунок 5), а также позиция 5.

параллелепипеда

4. По аналогии определяются позиции параллелепипеда относительно цилиндра.

5. Позиции относительно пары цилиндров г, у определяются таким образом, чтобы, если это возможно, имелась одна точка касания с каждым из цилиндров (Рисунок 6).

Рисунок 6 - Позиции 1, 2 для размещения цилиндра относительно двух

цилиндров

В третьей главе рассматриваются известные эволюционные и sweep алгоритмы, их достоинства и недостатки.

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

шина задается координатами (б,-, рД где в1 - угловая координата (полярный угол, азимут), рг - радиальная координата (Рисунок 8).

Работа алгоритма состоит из следующих шагов:

1. Депо размещается в точку с координатами (0,0).

2. Рассчитать координаты всех клиентов на основе расположения депо.

3. Начинаем перебирать клиентов, увеличивая полярный угол.

4. Выбираем свободное транспортное средство

5. Добавляем следующего клиента в текущий кластер и соответственно в маршрут текущего транспортного средства

6. Проверяем возможность добавить следующего клиента в текущий маршрут (проверка на вместимость транспортного средства)

7. Шаги 4-6 повторяются до тех пор, пока не будут распределены все клиенты

Для решения задачи размещения груза внутри ТС применяется эволюционный алгоритм. Рассматривается как (л,/и)ЕА, так и (2 + /и)ЕА. Алгоригмы в целом похожи, поэтому приведем лишь один из них. Алгоритмы отличаются лишь тем, что на каждой итерации у алгоритма (X + ц) родительские решения автоматически не отбрасываются. Основная суть алгоритма (А,ц)ЕА выглядит следующим образом:

Процесс решения начинается с создания первой популяции размером X, обычно особи в этом решение генерируются случайным образом. Далее определяется значение фитнеса на каждой из особей. После этого в популяции оставляют (I лучших особей, остальные уничтожаются. На основе каждой из ц особей создается Х/ц с использованием оператора мутации. Фактически создается X новых решений, родительски решения при этом отбрасываются. Итерации повторяются, пока не будет выполнен критерий остановки. Следует заметить, что X должно быть кратно Приведем схему алгоритма.

Общая схема алгоритма (р., X) ЕА

Вход: Я, ¡л

Выход: лучшее решение

Алгоритм: Р^О

Повторить к раз do

Р *—Ри(новое случайное решение) Повторять

Повторить для каждого P¡£P

ВычислитъФитнес(Р¡) Если Best— 0 ИЛИ Fitness (Pi) > Fitness(Best)

Best*- P¡ Q<—best ¡i in P

P+-0

Повторить для каждого QjEQ Повторить Х/ц раз Р<-Р U{Mutate(Copy(Qj))} Пока НЕ Критерий_остановки Return best

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

Эксперимент № 1 ■ Решалась задача размещения кругов.

Эксперимент проводился на известных классах примеров SY1 — SY6 [Е. Hopper]. Для сравнения были также пред ставлены решения задачи размещения кругов, полученные генетическим алгоритмом CAGA [М. Hifi, R. M'Hallah], методом ветвей и границ S.Y. [Y. G. Stoyan, G. N. Yaskov], жадной эвристической процедурой В1.5 [W. Q. Huang, H.Akeb, Y. Li, С. M. Li], алгоритмом вероятностного поиска с запретами TABU SEARCH (TS) [Ю. А. Кочетов, А. С. Руднев], решения, найденные с помощью коммерческого пакета GAMS fhttp://www.gams.comA. метод основанный на алгоритме муравьев ACOGA [Р. И. Файзрахманов] (Рисунок 8). В качестве оценки применялась нижняя граница оптимальной длины полубеско-

Ё s,

нечной области LB, lb = —- («S,—площадь г-го круга, W- ширина полубско-

W

нечной области). В качестве критерия оценки выступает длина занятой части полубесконечной области L.

Эксперимент № 2. Решалась задача одновременного размещения кругов и прямоугольников.

В эксперименте проводилось сравнение работы алгоритмов TS [А. С. Руднев], ACOGA[Р. И. Файзрахманов] и коммерческого пакета GAMS. ¿B-нижняя и С/В-верхняя оценки [А. С. Руднев]; для алгоритмов TS, ACOGA, ЕА приведены результаты работы алгоритмов (Рисунок 9). При решении задач одновременного размещения кругов и прямоугольников в полубесконечную область алгоритму ЕА

удалось найти новые рекордные решения на классах задач: С114Р02; С118Р01; СК8Р02.

Рисунок 8 - Сравнение алгоритмов при размещении кругов Упаковку кругов и прямоугольников

Разница между целевой функцей и верхней границей

15 16 —»— 18" "19 20*

.Номер

Рисунок 9 - Сравнение алгоритмов упаковки кругов и прямоугольников

Эксперимент № 3. Решалась задача размещения параллелепипедов Эксперимент проводился на известных тестовых наборах из библиотеки OR-Library fhttp://people.bnmel.ac.uk/~mastiib/ieb/info.html'). Сравнивались следующие алгоритмы: PackingTreel-3[A. Lim, В. Rodrigues, Y. Yang], Hybrid Methaheurislic (GA+ACO)[S.-C. Liang, C.-Y. Lee, S.-W. Huang], HybridMethaheuristic(GA+ILP)[N. Nepomuceno, P. Pinheiro, A. L.V. Coelho], SH-ВРЩМ Латыпов, И.С. Кощеев]. Каждый набор тестов состоит из 100 примеров, количество предметов изменяется от теста к тесту.

Bischoff, Lim, Lim, Lim, Liang, Nepomuceno, Koshcheev,

B\R PT1 PT2 PT3 ACO\GA GA+ILP SH-BP

thpackl 85,4 74,9 79,9 87,4 88,7 87,5 . 86,3

thpack2 86,25 75,6 79,4 88,7 90,7 86,8 86,4

thpack3 85,86 76,9 78,9 89,3 91,6 89,2 87,9

thpack4 85,08 77,5 79,2 89,7 91,8 86,7 86,3

thpackS 85,21 76,7 78,6 89,7 91,7 87,0 85,7

Эксперимент № 4. Решалась задача класса 3L-CVRP

Эксперимент проводился на известных тестовых наборах из библиотеки института г. Болонья (http://www.or.deis.unibo.it/research.html). Предложенный алгоритм сравнивался с поиском с запретами Tabu Search [M. Gendreau, M. Iori, G. Laporte, S. Martello], ACO [G. Fuellerer, K. Doerner, R. Hartl, M. Iori], Guided Tabu Search [E. Zachariadis, С. Tarantilis, С. Kiranoudis], В первом столбце представлено число заказчиков, в остальных столбцах — значения целевой функции (Таблица 2).

Таблица 2 - Сравнение алгоритмов для решения задач класса ЗЬ-СУ11Р

п Tabu search ACO Guided Tabu Search Sweep-SH-BP

15 316.32 303.25 321.47 312.07

15 350.58 334.96 334.96 334.96

20 447.73 409.79 430.95 418.43

20 448.48 440.68 458.04 451.62

21 464.24 453.19 465.79 466.84

21 504.46 501.47 507.96 506.96

22 831.66 797.47 796.61 801.36

22 871.77 820.67 880.93 875.37

25 666.10 635.50 642.22 653.32

29 911.16 841.12 884.74 868.54

29 819.36 821.04 873.43 853.73

30 651.58 629.07 624.24 654.88

32 2928.34 2739.80 2799.74 2728.44

32 1559.64 1472.26 1504.44 1501.74

32 1452.34 1405.48 1415.42 1417.62

35 707.85 698.92 698.61 701.35

40 920.87 870.33 872.79 868.63

44 1400.52 1261.07 1296.59 1284.67

50 871.29 781.29 818.68 902.64

71 732.12 611.26 641.47 603.77

75 1275.20 1124.55 1159.72 1174.75

75 1277.94 1197.43 1245.35 1207.65

75 1258.16 1171.77 1231.92 1259.12

75 1307.09 1148.70 1201.96 1196.89

100 1570.72 1436.32 1457.46 1428.16

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

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

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

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

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

3. Разработанный метод и алгоритмы для решения доставки груза потребителям с учетом его размещения внутри транспортного средства при наличии технологических ограничений, а именно:

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

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

4. Разработано программное обеспечение, реализующее предложенные алгоритмы для решения задачи доставки груза потребителям с учетом его размещения внутри ТС при наличие технологических ограничений (per №2014613599 от 31 марта 2014 г).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ОПУБЛИКОВАНЫ В РАБОТАХ

В рецензируемых журналах из списка ВАК

1. Многокритериальная задача доставки грузов различным потребителям / Н. И. Юсупова, А. Ф. Валеева, Е. Ю. Рассадникова, И. М. Латыпов, И. С. Кощеев // Логистика и управление цепями поставок. 2011. Т. 05 (46). С. 60-82.

2. Разработка логистической транспортной системы для решения задачи доставки груза различными клиентами. Часть 1 / А. Ф. Валеева, Ю. А. Гончарова, И. С. Кощеев // Информационные технологии. 2013. № 12. С. 23-28.

3. Разработка логистической транспортной системы для решения задачи доставки груза различными клиентами. Часть 2 / А. Ф. Валеева, Ю. А. Гончарова, И. С. Кощеев // Информационные технологии 2014. №1. С. 9—14.

4. Improvements in the APLP-3D for three-dimensional packing problem of cylinders and parallelepipeds /1. S. Koshcheev // Вестник УГАТУ. 2013. Т. 17 № 6 (59). С. 101-102 (Статья на английском языке).

Объекты интеллектуальной собственности

5. Свид. об офиц. per. программы для ЭВМ № 2014613599. Логистическая система для решения задачи доставки груза различным потребителям / А. Ф. Валеева, Ю. А. Гончарова, И. С. Кощеев. М.: Роспатент, 2014.

В трудах всероссийских и международных конференций

6. Упаковка цилиндров и параллелепипедов в контейнеры с учетом технологических ограничений на основе эволюционных алгоритмов / А. Ф. Валеева, И. С. Кощеев // Методы оптимизации и их приложения: XV Байкальская международная школа-семинар (Листвянка. 23-29 июня 2011). Иркутск: ИДСТУ СО РАН, 2011.С. 54-58.

7. Задача доставки грузов транспортными средствами различной вместимости / Н. И. Юсупова, А. Ф. Валеева, И. М. Латыпов, Е. Ю. Рассадникова, И. С. Кощеев // Математическое программирование и приложения: Всероссийская конференция ( Екатеринбург, 28 февраля - 4 марта 2011). Екатеринбург: УМЦ УПИ, 2011. С. 226.

8. Задача доставки грузов различными транспортными средствами / А. Ф. Валеева, И. С. Кощеев // Актуальные проблемы науки и техники: VI Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 15-18 февраля 2011). Уфа: УГАТУ, 2011. С. 225-229.

9. Трехмерная упаковка в контейнеры с учетом технологических ограничений на основе эволюционных алгоритмов / А. Ф. Валеева, И. С. Кощеев // Мавлю-товские чтения: Всероссийская молодежная научная конференция (Уфа, 21-24 марта 2011). Уфа:УТАТУ, 2011. С. 97.

10. Решение задачи упаковки предметов в полубесконечный контейнер на основе эволюционного алгоритма (1+1)ЕА / А. Ф. Валеева, И. С. Кощеев // Информационные технологии и системы (Банное, Республика Башкортостан, 28 февраля - 4 марта 2012). Челябинск: ЧелГУ, 2012. С. 39-42.

11. Решение задачи упаковки предметов цилиндрической и параллелепи-педной формы в вагоны на основе эволюционного алгоритма (1+1)ЕА/ И. С. Кощеев // Актуальные проблемы науки и техшпеи: VII Всероссийская зимняя школа-семинар аспирантов и молодых ученых (Уфа, 14—16 февраля 2012) Уфа: УГАТУ, 2012. С. 173-176.

12. Использование поддонов при применение алгоритма ABLP / И. С. Кощеев // Интеллектуальные технологии обработки информации и управления: Международная молодежная конференция (Уфа, 17—20 июля 2012). Уфа: УГАТУ, 2012. С. 173-176.

13. Трехмерная упаковка цилиндров и параллелепипедов в полу бесконечный контейнер с учетом расположения центра масс / А. Ф. Валеева, И. С. Кощеев // Проблемы оптимизации и экономические приложения: V Всероссийской конференции (Омск, 2—6 июля 2012). Омск: ОмГУ, 2012. С. 14-16.

14. Задача о доставке однородного продукта различным потребителям / А. Ф. Валеева, И. С. Кощеев, Ю. А. Гончарова // Дискретная оптимизация и исследование операций: Международная конференция (Новосибирск, 24-28 июня 2013). Новосибирск: Изд-во Института математики, 2013. С. 128.

15. Задача оптимизации доставки груза / А. Ф. Валеева, И. М. Латыпов, И. С. Кощеев, Е. Ю. Рассадникова // Информатика и информационные технологии СБГГ 2010: 12-я междунар. конф. (Уфа-Москва-Санкт-Петербург, 13-19 сентября 2010). Т. 3. С. 87-89. (Опубл. на английском языке).

16. Эволюционный алгоритм (1+1)ЕА для задачи упаковки цилиндров и па-раллелелепипедов в контейнеры / И. С. Кощеев // Информатика и информационные технологии СБЕГ 2010: 12-я междунар. конф. (Уфа-Москва-С. Петербург, 13-19 сентября 2010). Т. 3. С. 43-46. (Опубл. на английском языке).

17. Обзор существующих методов решения задачи трехмерного размещения цилиндров и параллелепипедов в полубесконечный контейнер / И. С. Кощеев // Информатика и информационные технологии СБЕГ 2011: 13-я мезадунар. конф. (Гармиш-Партенкирхен, 13-19 сентября 2011). Уфа: УГАТУ, 2011. С. 39-41. (Опубл. на английском языке).

18. Поиск нижних границ для задачи трехмерной упаковки / А. Ф. Валеева, в. ЗсЪеШшиег, И. М. Латыпов, И.С. Кощеев // Информатика и информационные технологии С51Т'2012: тр. 14-й междунар. конф. (Уфа - Гамбург - Норвежские Фьорды, 20-26 сентября 2012). Уфа: УГАТУ, 2012. Т. 1. С. 20-26. (Опубл. на английском языке).

Диссертант

И. С. Кощеев

КОЩЕЕВ Иван Сергеевич

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

Специальность: 05.13.01 — Системный анализ, управление и обработка информащш (в промышленности)

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

Подписано в печать 16.04.2015. Формат 60x84 1/16 Бумага офсетная. Печать плоская. Гарнитура Times New Roman. Усл. печ. л. 1,0. Уч.-изд. л. 0,9. Тираж 100 экз. Заказ № 258.

ФГБОУ ВПО «Уфимский государственный авиационный технический университет» Центр оперативной полиграфии 450000, Уфа-центр, ул. К. Маркса, 12