Содержание к диссертации
Введение
Глава 1 Проблема доставки груза потребителям с учетом его размещения внутри транспортных средств при наличии технологических ограничений 9
1.1 Актуальность исследуемой проблемы 9
1.2 Анализ существующих методов составления рациональных маршрутов доставки груза 13
1.3 Классификация и анализ методов решения задачи маршрутизации 19
1.4 Классификация и анализ методов решения задачи упаковки 30
1.5 Цель и задачи исследования 38
Выводы по первой главе 39
Глава 2 Постановка задачи доставки груза потребителям с учетом его размещения внутри транспортных средств при наличии технологических ограничений и методы ее решения 41
2.1 Математические модели задачи доставки груза с учетом его размещения внутри ТС 41
2.2 Декодер для решения задачи оптимизации размещения груза внутри ТС ... 51
2.3 Анализ работы процедуры размещения 58
Выводы по второй главе 65
Глава 3. Разработка метода решения задачи доставки груза потребителям с учетом его размещения внутри ТС при наличии технологических ограничений 67
3.1 Разработка алгоритма для решения транспортной задачи 67
3.2 Применение эволюционных стратегий для решения задачи размещения груза внутри ТС 70
3.3 Разработка роевой гиперэвристики для решения задачи оптимизации размещения груза внутри ТС
3.4. Разработка метода решения задачи доставки груза потребителям с учетом технологических ограничений 85
3.5. Анализ работы алгоритма эволюционных стратегий 89
Выводы по третьей главе з
Глава 4. Оценка эффективности алгоритмов и методов оптимизации доставки груза потребителям при наличии технологических ограничений на базе численных экспериментов 95
4.1 Программное обеспечение для задачи оптимизации доставки груза потребителям при наличии технологических ограничений 95
4.2 Анализ результатов численного эксперимента на задаче размещения кругов. 99
4.3 Анализ результатов численного эксперимента на задаче размещения кругов и прямоугольников 103
4.4 Анализ результатов численного эксперимента на задаче размещения прямоугольных параллелепипедов 106
4.5 Анализ результатов численного эксперимента на задаче класса 3L-CVRP109
4.6 Анализ эффективности работы программного обеспечения для решения прикладных задач ПО
Вывод по четвертой главе 114
Заключение 116
Список литературы
- Классификация и анализ методов решения задачи маршрутизации
- Декодер для решения задачи оптимизации размещения груза внутри ТС
- Разработка роевой гиперэвристики для решения задачи оптимизации размещения груза внутри ТС
- Анализ результатов численного эксперимента на задаче размещения кругов и прямоугольников
Классификация и анализ методов решения задачи маршрутизации
В современной рыночной экономике исчезают все границы для товарооборота между странами, что порождает жесткую конкурентную борьбу практически на всех рынках. Объем мирового экспорта за последние тридцать лет увеличился в десять раз [1]. В условиях рыночной конкуренции предприятиям необходимо снижать свои затраты, для того чтобы обеспечить выгодное предложение клиентам. Значительную часть расходов составляют расходы на логистику. В среднем на предприятиях расходы на логистику находятся в интервале 5-35% в зависимости от таких факторов, как: объем выпускаемой продукции, географическое расположение, используемый ресурс, тип бизнеса и т.д. Это статья расходов уступает лишь затратам на материалы и сырье [2]. Расходы на транспортную логистику могут составляют до 50% расходов на логистику, в целом [3].
Если рассматривать экономику макроуровня, то расходы на логистику также составляют значительную часть. Например, в США в 2003 году объем расходов на логистику составлял 8,5% валового внутреннего продукта [4]. В 2013 году расходы на транспортную логистику в России составили 6,3% валового внутреннего продукта РФ. Примерно половина расходов на логистику составляют расходы на транспортную логистику. В свою очередь 76.5% перевозок совершаются автотранспортном [5]. Отдельно стоит заметить, что в 2014 году экономическая ситуация в России стала хуже чем в прошлом году: объемы потребления сокращаются, что приводит к пропорциональному (а часто и большему) сокращению рынка услуг транспортной и складской логистики [2], а значит к ужесточению конкуренции.
В этих условиях значение себестоимости продукции для предприятия резко возрастают [4] [3]. Себестоимость продукции (работ, услуг) представляет собой стоимостную оценку используемых в процессе производства продукции (работ, услуг) природных ресурсов, сырья, материалов, топлива, энергии, основных фондов, трудовых ресурсов и других затрат на ее производство и реализацию [4].
Принято различать среднеотраслевую и индивидуальную себестоимость. Среднеотраслевая себестоимость определяется как средневзвешенная величина и характеризует средние затраты на единицу продукции по отрасли, поэтому она находится ближе к общественно необходимым затратам труда. Индивидуальная себестоимость определяется как себестоимость конкретно взятого предприятия. Следовательно, в условиях конкурентной борьбы предприятие должно стараться держать себестоимость на уровне среднеотраслевой, а лучше ниже ее. Значительную часть себестоимости могут составлять расходы на логистику, в целом, и на транспортную логистику, в частности
Одной из основных задач транспортной логистики является выбор вида и типа ТС, а также определение рациональных маршрутов доставки. Доставка груза может осуществляться различными транспортными средствами. Выбор конкретного вида ТС зависит от шести основных факторов [2]:
При этом традиционно различают следующие шесть видов транспортных средств, каждый из которых обладает своими достоинствами и недостатками. Наиболее популярным способом доставки груза является автомобильный транспорт. Обусловлено это несколькими факторами: автомобильный транспорт позволяет обеспечить оперативность, динамичность; на рынке существует достаточно большое количество перевозчиков, что обеспечивает конкурентную борьбу между ними. Однако у данного метода перевозки есть и недостатки: так с возрастанием расстояния себестоимость начинает возрастать по сравнению с конкурирующими видами; вторым существенным недостатком является зависимость от дорожных условий и сравнительно небольшая грузоподъемность. Вторым часто используемым видом транспорта является железнодорожный. Он способен обеспечить перевозку практически в любые погодные условия, при достаточно невысокой цене. К ключевому недостатку железнодорожного транспорта стоит отнести его ограниченность, причем ограниченность в двух смыслах: ограниченное число перевозчиков и ограниченное число железнодорожных станций, откуда может потребоваться дополнительный развоз. Воздушный транспорт позволяет обеспечить быструю доставку в отдаленные регионы, но данный вид транспорта обладает высокой стоимостью и ограниченностью (ограниченное число аэропортов, дополнительный развоз от аэропорта). Одним из самых дешевых видов транспорта, способным обеспечить высокую грузоподъёмность на дальние расстояния является морской транспорт. Главными проблемами при использовании морского транспорта являются долгое время доставки и сильная зависимость от географических условий и степени развития инфраструктуры. В некоторых классификациях выделяют также речной транспорт, который обладает теми же достоинствами и недостатками, что и морской. Отдельно от остальных стоит трубопроводный вид доставки, который обеспечивает высокую скорость доставки при невысокой стоимости, однако подходящий только под некоторые виды грузов и ограниченность передачи при малых данных (невозможно передавать малые объемы).
Каждая фирма выбирает тот или иной вид транспортных средств, исходя из 6 факторов, перечисленных выше. В рамках данной работы рассматривается автомобильный транспорт. При его рассмотрении для решения задачи транспортной логистики, то важная проблема, требующая подробного рассмотрения. Это проблема экономического выбора между двумя альтернативами: содержанием собственного парка автотранспорта или аренды стороннего (аутсорсинг).
Декодер для решения задачи оптимизации размещения груза внутри ТС
Общую идею вычисления решения задач упаковки (задач раскроя и упаковки) при использовании метаэвристических алгоритмов можно выразить следующим образом. Алгоритм состоит из двух частей: первая - это алгоритм, работающий с кодировкой и осуществляющий перебор возможных кодировок решения; вторая - это алгоритм-декодер, осуществляющий преобразование кодировки непосредственно в промежуточное решение (план размещения). Под кодировкой подразумевается приоритетный список, т.е. некоторая перестановка номеров предметов. Соответственно основными функциями алгоритма-деко дера является вычисление целевой функции и восстановление плана размещения из кодировки решения. Для представления решения предлагается прямая схема кодирования, при которой решение представляется в виду последовательностей координат (xpuypuzpi), при этом для прямоугольных параллелепипедов этими координатами задается левый нижний ближний угол предмета, а для цилиндров -центра нижнего основная предмета. Для кодирования решения предлагается приоритетный список, состоящий из номеров предметов [85]. Наиболее известным и часто упоминаемых в литературе декодером является «нижний левый» («bottom-left»).Улучшенный вариант этого декодера был предложен в 1999 году в работе Liu D., Teng Н. [86]. Разные вариации данного декодера использовались в сочетании с разнообразными эвристическими алгоритма [87] [88].Также хорошие результаты показывали декодер Q-последовательность, предложенный в 2000 году работе К. Sahanushi, Y. Kajitani [89], и схема парных последовательностей кодирования, предложенная 2001 году Imahori S., Yaguira М., Ibaraki Т. [90], а также Lot схема для кодирования упаковок, которые представляются упорядоченным деревом (Takahasi).
В рамках данной работы предлагается декодер ABLP , который является расширения декодера ABLP(Adapted Best Local Position) [66] и TSLP(Best Local Position) [66] успешно применяемых для решения задач упаковки кругов, а также кругов и прямоугольников. ABPL, по аналогии с BLP находится самую левую верхнюю позицию для размещения круга заданного размера, но существенное отличие состоит в том, что он проще в реализации и быстрее по времени выполнения.
Рассмотрим подробнее работу процедуры ABLP , позволяющей найти доступные позиции для размещения предметов. Первый предмет, как уже отмечалось, помещается в дальний нижний левый угол контейнера. Позиции относительного каждого уже размещенного предмета определяются следующим образом:
Если следующий предмет - цилиндр, то позиции его расположения относительно параллелепипеда itpt определяются следующим образом: параллелепипед очерчивается плоскостями, проходящими через его стороны. Таким образом, в плоскости Z=zpi образуются позиции 1-4 (Рисунок 2.4) для размещения цилиндра, а в плоскости Z=zpi+hpi - еще одна позиция 5. Координаты для этих позиций определяются следующим образом:
Если первым в контейнер помещается параллелепипед, а следующим -также параллелепипед, то для размещения второго параллелепипеда относительно первого создаются позиции 1-4 (Рисунок 2.6), а также позиция 5. (Wi. УРІ)
Приведем пример работы процедуры рационального размещения прямоугольных параллелепипедов и цилиндров ABLP на примере полубесконечной трехмерной области (для простоты рассматривается случай, когда предметы не образуют ярусов, поэтому на рисунках отображаются двумерные проекции).
Пусть имеется множество предметов Item = {Item\, Iteni2, Item , Item } ,где Item\Jtem2Jtem - предметы цилиндрической формы, каждый из которых задается парой (гск,кск), Item - предметы параллелепипедной (прямоугольной) формы, каждый из которых задан тройкой (1рк, wpk, hpk ).
Требуется разместить заданные предметы в полубесконечный контейнер при соблюдении условий допустимости математической модели одновременного размещения прямоугольных параллелепипедов и цилиндров, формулы (2.8) -(2.14).
Пример работы метода ABLP3D: 1. В начале работы метода ABLP в полубесконечный контейнер, в которую следует разместить предметы, нет ни одного размещенного цилиндра или прямоугольного параллелепипеда. Пусть первым предметом для размещения был выбран цилиндр Item і. Ввиду того, что контейнер пуст первый цилиндрЛет? размещается в нижний ближний левый угол (Рисунок 2.9) с координатами (xci=rchyci=rch ZC =0). размещенный цилиндр Item і с радиусом rcj очерчивается плоскостями перпендикулярными XOY и ZOY. Таким образом, формируется 5 возможных позиций для размещения; На Рисунок 2.10 продемонстрирован найденный список позиций П={\, 2, 3, 4, 5, 6, 7, 8, 9} возможных позиций размещения цилиндра Item2 относительно уже размещенного цилиндра Itemj и контейнера. Позиции 1 и 2 не удовлетворяют условию допустимости о невыходе цилиндров за границы области размещения формула (2.13). Позиция 6 не удовлетворяет условию допустимости о не пересечении цилиндров друг с другом - формула (2.12). По этой причине данные позиции не попадают в список допустимых позиций 77 . Из оставшихся позиций {3, 4, 5, 7, 8, 9} все формируют допустимые решения, по критерию минимума координат (в порядке убывания приоритета z, х, у) выбирается позиция 3.Пусть (хс2, ус2, zc2 ) - координаты центра нижнего основания цилиндра Item2 (Рисунок 2.11), тогда искомые координаты(лг2, 2, )цилиндра Item2 вычисляются из системы уравнений (2.35).
Разработка роевой гиперэвристики для решения задачи оптимизации размещения груза внутри ТС
Прототип программного обеспечения, реализующий предложенные алгоритмы и методы, предназначен для решения задачи доставки груза потребителям с учетом расположения груза внутри транспортных средств. Прототип представляет собой клиент-серверное приложение. Серверная часть приложения может быть размещена на любом сервере приложений, поддерживающем Java (IBM WebSphere Application Server (WAS), Oracle GlassFish Server, Getty и т.д.), поддержка JavaEE не является обязательной. Серверная часть поставляется в виде war-архива и динамически подключаемой библиотеки (для новых систем библиотеку необходимо будет перекомпилировать). Промышленные примеры выполнялись на следующих двух конфигурациях: AIX 7.1 + WAS 8.5.5.2 и Windows Server 2008r2 + GlassFish 3.1.2.
Описание программного решения. На рисунок 4.1. представлена схема работы прототипа программного обеспечения. Как видно на рисунке прототип решения представляет собой клиент-серверное приложение. Реализацию программы можно разбить на две части: алгоритмическая часть реализована на языке C++ в виде динамически подключаемой библиотеки (DLL), и прикладная часть, реализованная на языке программирования JAVA. Клиент-серверное взаимодействие организовано с использованием Google Web Toolkit (GWT). Часть логики, отвечающая за отображение найденных маршрутов с использованием Google Maps Web API, реализована с использованием JavaScript. Рисунок 4.1- Описание архитектуры предлагаемого решения
На рисунок 4.2. представлена статическая модель данных решаемой задачи. В ней описаны основные сущности, существующие в задаче, а также характеризующие их параметры и виды связей между ними. Как видно из рисунка были выделены следующие сущности: заказчик, заказ, грузовик, тип грузовика, поддон, тип поддона, отдельные типы заведены под груз.
Параметры алгоритма. Параметры, используемые для построения алгоритма, задаются с помощью стандартного файла Java-конфигурации, который представляет собой набор вида «ключ=значение» разделенный символом перехода на новую строку. Рисунок 4.2 - Статическая модель данных Например, для задания параметров работы алгоритма ABLP в файле параметров должны быть указаны следующие параметры:
Автоматизированное построение решений. Для проведения тестирования в программе предусмотрена возможность построения решения сразу по набору тестовых данных с предварительным указанием параметров алгоритмов, которые необходимо для них применять. При этом для каждого тестового набора можно указать несколько тестовых наборов с помощью механизма описанного в разделе с описанием параметров алгоритма. Данный механизм продемонстрирован на рисунок 4.2.
Построение статистики. Для удобства тестирования в программе предусмотрена функция, позволяющая подвести статистику по заданному набору результирующих файлов. Результатом выполнения данной функции является xml файл. Так как клиент является тонким клиент, передача на сервер осуществляется посредством передачи ссылки на расшаренную папку, куда необходимо предварительно разместить заранее полученные результирующие данные. Использование программного лога.
Уровень легирования выставляется стандартным образом и может быть выставлен в один из следующих уровней: trace, debug, info, warn, error. По умолчанию лог пишется в папку с SystemOut сервера приложений, однако данное поведение может быть изменено соответствующими настройками. Для чтения логов рекомендуется использовать такие стандартные средства как NodePad+ (Ъпр://notepad-plus-plus.org/), Sublime(http://www.sublimetext.com/). 4.2 Анализ результатов численного эксперимента на задаче размещения кругов Эксперимент проводился на известных тестовых наборах для решения задачи размещения кругов в полубесконечную полосу. Для каждого тестового набора известны длина и ширина контейнера, а также радиусы кругов для упаковки. Также представлены решения задачи упаковки кругов, полученные генетическим алгоритмом CAGA[73], методом ветвей и границ S.Y. [105], жадной эвристической процедурой В 1.5 [106], алгоритмом вероятностного поиска с запретами TABU SEARCH (TS) [107], алгоритмом муравьиной колонии [108], решением предложенным А.С. Рудневым на основе коммерческого проекта GAMS(http://www.gams.com/)(c использованием решающего ядра BARON), а также нижними границами(Х5) по объему. LB = W , где W - ширина контейнера Время работы алгоритма CAGA составляло 30 минут на компьютере с процессором Pentium III 733MHz. Время работы метода ветвей и границ не указано, за исключением примера SY6, для которого потребовался один час на IBM PC/AT 486. Среднее время работы алгоритма В 1.5 составляло примерно 40 минут для примеров SY1-SY4 и 18 часов для примеров SY5 и SY6 на машине с процессором Athlon ХР2000+. Время работы алгоритма Р-АСО составляло 30 мин.
Анализ результатов численного эксперимента на задаче размещения кругов и прямоугольников
Время работы алгоритма CAGA составляло 30 минут на компьютере с процессором Pentium III 733MHz. Время работы метода ветвей и границ не указано, за исключением примера SY6, для которого потребовался один час на IBM PC/AT 486. Среднее время работы алгоритма В 1.5 составляло примерно 40 минут для примеров SY1-SY4 и 18 часов для примеров SY5 и SY6 на машине с процессором Athlon ХР2000+. Время работы алгоритма Р-АСО составляло 30 мин. Для пакета GAMS было выделено 20 часов на решение каждого примера. За это время было получено решения только для тестовых наборов SY1-SY4. В таблице 4.1. представлена информация о примерах, где W - ширина полосы, L длина полосы, пс - количество кругов в тестовом наборе. В таблице 4.2 представлены результаты численных экспериментов, те же данные представлены в графическом виде на рисунке 4.2.
Сравнение алгоритмов при размещении кругов На этих же тестовых наборах проводилось исследование влияния параметров алгоритма на качество получаемого решения. Рассматривались следующие параметры: значение ц, значение А., время выделенное на работу алгоритма. При каждом наборе параметров запуск осуществлялся 10 раз. В таблице ниже (Таблица 4.3) значения с стобце Min - лучшее полученное решение, Avg - среденее полученное решение, Мах - худшее из полученных решений.
Выводы no эксперименту: Как видно из результатов первого численного эксперимента алгоритм, основанный на эволюционных стратегиях, на 5 из 103 тестовых наборах лучше, чем В 1.5 и S.Y. Решения, получаемые алгоритмами Р-АСО, Tabu Search и ЕА в целом показывали соизмеримые результаты. Для тестового набора SY3 было получено новое лучшее решение. Решения, полученные с помощью алгоритма ЕА, не отличаются более чем на 4% от лучших известных. По итогам проведения численного эксперимента можно сделать следующие выводы: по влиянию параметров алгоритма на качество получаемого решения: параметры А. и ц на заданных тестовых наборах не имели решающего значения; с увеличением времени вычисления результаты имели тенденцию к улучшению, но при этом результаты, полученные за 30 сек., не отличались более чем на 3% от результатов, полученных за 900 сек.
А.С.Рудневым в статье [107]. Для данных наборов известна оценка верхней границы оптимального решения, т.к. генерация тестовых наборов проходила последующей схеме: генерировались безотходное размещение пг прямоугольников и пс квадратов для заданной прямоугольной полосы размером W UB. Затем каждый квадрат заменялся кругом, соответствующего диаметра (равного стороне квадрата). А.С. Рудневым предложено 24 тестовых наборов с количеством предметов от 8 до 196.
В процессе эксперимента алгоритм ЕА запускался 10 раз для каждого примера. Был рассмотрен неориентированный случай задачи, т.е. повороты прямоугольников на 90 градусов были разрешены.
Выводы no эксперименту: В поставленных экспериментах для 3 тестовых наборах были получены рекордные значения, еще для 5 тестовых наборах алгоритм достиг наилучшего известного на данный момент значения целевой функции. На всей совокупности тестовых наборов алгоритм показывал результаты, отличающиеся от лучших известных не более чем на 1-9. По итогам проведения численного эксперимента можно сделать следующие выводы: время работы алгоритма не имело решающего влияния на получаемые результаты, в поведение алгоритма не наблюдалось никакого тренда в зависимости от времени выполнения - это можно объяснить тем, что алгоритм достаточно быстро находил локальный оптимум и в дальнейшем улучшения решения уже не происходило.
Анализ результатов численного эксперимента на задаче размещения прямоугольных параллелепипедов Эксперимент 1. Оценка зависимости времени итерации алгоритма от количества размещаемых предметов для решения задачи размещения в полубесконечный контейнер для алгоритма SH-BP. В таблице 4.6. представлены результаты данного опыта при этом приведенные данные по результатам 10 запускам на каждом тестовом наборе. Эксперимент проводился на известных тестовых набор, представленных в OR-Library
Выводы по эксперименту: Как видно из таблицы 4.3. время выполнения одной итерации гиперэвристического алгоритма, основанного на алгоритме пчел, возрастает относительно плавно вплоть до 350 предметов, после чего время итерации начинает резко возрастать.
Эксперимент 2. В ходе второго эксперимента проводилось сравнение предлагаемой гиперэвристики SH-BP с низкоуровневыми алгоритмами NextFit, FirstFit, BestFit. Как и в предыдущем опыте, сравнение проводилось на известных тестовых наборах из международной библиотеки тестов OR-Library для задач исследования операций (Ъпр: //people. brunel. ас. uk/ mastj і b/j eb/info. html). В таблице 4.7. представлены результаты данных алгоритмов, в ячейках таблицы представлено значение целевой функции (занятая высота контейнера).
Выводы по эксперименту: Из представленной таблице видно, что гиперэвристический алгоритм, основанный на алгоритме пчел, дает результат лучше, чем используемые в нем однопроходные эвристики NextFit, FirstFit, BestFit. На заданных тестовых наборах гиперэвристический алгоритм, основанный на алгоритме пчел, показал результат был на 1-35% лучше, чем у однопроходных эвристик.
Эксперимент 3. Эксперимент проводился на известных тестовых наборах из библиотеки OR-Library (Ъпр: //реор! е. brunel. ас. uk/ mastj і b/j eb/info. html). Сравнивались следующие алгоритмы: PackingTreel-3 [109], Hybrid Methaheuristic (GA+ACO) [110], Hybrid Methaheuristic(GA+ILP) [111], SH-BP. Каждый набор тестов состоит из 100 примеров, количество предметов изменяется от теста к тесту. Результаты вполнения алгоритмов представлены в Таблице 4.8.