Оптимизация доставки груза потребителям с учетом его размещения внутри транспортных средств на основе эвристических методов

• Автор: Кощеев, Иван Сергеевич
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Уфа
• Количество страниц: 133 с. : ил.

Оглавление
Введение
Глава 1 Проблема доставки груза потребителям с учетом его размещения внутри транспортных средств при наличии технологических ограничений

1.1 Актуальность исследуемой проблемы

1.2 Анализ существующих методов составления рациональных маршрутов доставки груза

1.3 Классификация и анализ методов решения задачи маршрутизации

1.4 Классификация и анализ методов решения задачи упаковки

1.5 Цель и задачи исследования

Выводы по первой главе

Глава 2 Постановка задачи доставки груза потребителям с учетом его размещения внутри транспортных средств при наличии технологических ограничений и методы ее решения
2.1 Математические модели задачи доставки груза с учетом его размещения внутри ТС
2.2 Декодер для решения задачи оптимизации размещения груза внутри ТС
2.3 Анализ работы процедуры размещения
Выводы по второй главе
Глава 3. Разработка метода решения задачи доставки груза потребителям с учетом его размещения внутри ТС при наличии технологических ограничений
3.1 Разработка алгоритма для решения транспортной задачи
3.2 Применение эволюционных стратегий для решения задачи размещения груза внутри ТС
3.3 Разработка роевой гиперэвристики для решения задачи оптимизации размещения груза внутри ТС
3.4. Разработка метода решения задачи доставки груза потребителям с учетом технологических ограничений
3.5. Анализ работы алгоритма эволюционных стратегий
Выводы по третьей главе

Глава 4. Оценка эффективности алгоритмов и методов оптимизации доставки груза потребителям при наличии технологических ограничений на базе численных экспериментов
4.1 Программное обеспечение для задачи оптимизации доставки груза потребителям при наличии технологических ограничений
4.2 Анализ результатов численного эксперимента на задаче размещения кругов.
4.3 Анализ результатов численного эксперимента на задаче размещения кругов и прямоугольников
4.4 Анализ результатов численного эксперимента на задаче размещения прямоугольных параллелепипедов
4.5 Анализ результатов численного эксперимента на задаче класса ЗГ-СУЯР
4.6 Анализ эффективности работы программного обеспечения для решения прикладных задач
Вывод по четвертой главе
Заключение
Список литературы

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

используемых контейнеров [59]. В 2009 году Teoder G. Crainic, Guido Perboli и другие предложили двухуровневый поиск с запретами для той же задачи ВРР, при этом на втором уровне (размещения предметов в контейнеры) использовалось представление в виде графа интервалов [60].
Имитация отжига (Simulated Annealing, SA).
В 1994 году R.L. Rao и S.S. Iyengar предложили метод имитации отжига для задачи упаковки [61]. В 1997 году Brusco M.J, Thompson G.M и другие предложили имитацию отжига на основе морфинга для модифицированной задачи упаковки, в которой необходимо минимизировать среднеквадратичное отклонение от заданной точки по всем контейнерам [62]. В 2005 году А.Ф. Валеева и Т.Ю. Сиразетдинова предложили подификацию алгоритма для решения задачи двумерного гильотинного прямоугольного раскроя [63].
Генетические алгоритмы. Генетические алгоритмы могут различаться способом кодирования, определения простейших структур. Возможны различные способы кодирования и приемы идентификации простейших структур. Своего рода «классическим» является алгоритм для двухмерной задачи упаковки, представленный в работах D. Liu, H.Teng [64]; Н Cehring, A.Bortfeld [65]. Эффективность данного алгоритма сильно зависит от используемого декодера. Сравнение блочного декодера, парных списков, замещений и других декодеров показывает, что худший результат во всех случаях показывает усовершенствованный D. Liu, H.Teng декодер нижний-левый (IBL).
В 2007 г. Hifi М., M'Hallah R. предложили генетический алгоритм в сочетание с конструктивной процедурой для решения двухмерной задачи упаковки кругов в полосу [66].
Алгоритмы муравьиной колонии.
Алгоритм муравьиной колонии применялся для решения задач раскроя и упаковки. Например, в 2004 году J. Levine и F. Ducatelle предложили гибридный алгоритм, основанный на алгоритме муравьиной колонии и алгоритма локального поиска [67]. Применение алгоритмов муравьиной колонии для решения задач