Разработка и исследование роевых алгоритмов для решения транспортно-логистических задач

• Автор: Кажаров, Аскер Артурович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Таганрог
• Количество страниц: 173 с. : ил.

СОДЕРЖАНИЕ
СОДЕРЖАНИЕ
ВВЕДЕНИЕ

1. АНАЛИЗ И СОСТОЯНИЕ ПРОБЛЕМ РЕШЕНИЯ ТРАНСПОРТНЫХ

ЗАДАЧ

1Л Анализ алгоритмов и методов решения задачи коммивояжера

1.2 Анализ и состояние задачи маршрутизации автотранспорта

1.2 Л Построение математической модели задачи маршрутизации автотрав спорта

1.2.2 Построение критерия оптимизации задачи маршрутизации автотрав спорта

1.3 Анализ и состояние задачи разбиения товаров для упаковки в транспортные средства
1.4 Анализ алгоритмов и методов решения задач коммивояжера и маршрутизации автотранспорта
1.4.1 Анализ последовательных алгоритмов
1.4.2 Ашшиз итерационных алгоритмов
1.4.3 Обзор вероятностных алгоритмов
1.4.4 Ашшиз временной сложности алгоритмов решения задач коммивсяжера и маршрутизации автотранспорта
1.5 Выводы
2 РАЗРАБОТКА БИОИНСПИРИРОВАННЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА И МАРШРУТИЗАЦИИ АВТОТРАНСПОРТА
2.1 Разработка генетического алгоритма для решения задачи маршрутизации автотранспорта
2.1.1 Описание структурной схемы генетического алгоритма
2.1.2 Разработка кодировки хромосомы
2.1.3 Разработка генетических операторов

2.2 Разработка простого муравьиного алгоритма для решения задачи коммивояжера
2.3 Построение модификаций муравьиного алгоритма
2.3.1 Построение модификации «элитных» муравьев
2.3.2 Построение стратегий начального расположения колонии муравьев
2.3.3 Создание шаблонов
2.3.4 Построение модификации выпрямления
2.3.5 Построение модификации «пространственного феромона»
2.3.6 Разработка модифицированного муравьиного алгоритма для решения задачи маршрутизации автотранспорта
2.4 Оценке сложности муравьиного алгоритма
2.5 Разработка пчелиного алгоритма для решения задачи коммивояжера..
2.6 Разработка метода роя частиц для решения транспортных задач
2.7 Выводы
3 ПОСТРОЕНИЕ ИНТЕГРИРОВАННОГО АЛГОРИТМА МАРШРУТИЗАЦИИ АВТОТРАНСПОРТА
3.1 Анализ построения интегрированных алгоритмов маршрутизации автотранспорта
3.2 Разработка архитектуры гибридного алгоритма
3.3 Анализ и оценка временной сложности гибридного алгоритма
3.4 Выводы
4 ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
4.1 Исследования модифицированного муравьиного алгоритма для задачи коммивояжера
4.2 Исследования муравьиного алгоритма для задачи маршрутизации автотранспорта
4.3 Исследования пчелиного алгоритма для задачи разбиения товаров с учетом совместимости
4.4 Приложения
4.5 Выводы
ЗАКЛЮЧЕНИЕ
СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ
ПРИЛОЖЕНИЯ А
ПРИЛОЖЕНИЯ Б

быть данные из электронной системы, чеки и т.д. Далее на карте отмечаются все точки разгрузки/доставки товаров. Критерий оптимизации может меняться в зависимости от граничных условий. В зависимости от вида деятельности у предприятия бывают периоды активного сбыта товара и наоборот. К примеру, холодные напитки летом имеют намного больший спрос, чем зтмой. Тем самым в определенный период автопарк предприятия более загружен, и возникает риск нехватки транспорта. В этом случае предприятие вынуждено пользоваться услугами грузоперевозочных компаний, что само собой дороже использования собственного автопарка. Таким образом, главным критерием оптимизации в летний период становится размер используемого автопарка, а диспетчеру необходимо делать упор на решение задачи упаковки. С другой стороны, в период, когда заказы менее интенсивны, а риск нехватки транспорта для доставки товаров минимален, возникает проблема оптимизации маршрута, так как топливные расходы становятся основными. В этом случае основным критерием оптимизации становится длина маршрута[35].
Другим граничным условием является быстродействие алгоритма. Условия задачи могут меняться динамически, причины для этого разные -изменение адреса доставки, отказ заказчика от товара, изменение временного окна, человеческий фактор при сборе информации и т.д. Вследствие этого необходимо пересчитать маршрут, что невыгодно для трудоемких алгоритмов. В данной ситуации время пересчета маршрута становится временем пэостоя для водителя. «Приемлемым» эмпирически считается время пересчета до 10 минут. Отметим, что на начальном этапе время расчета может составлять порядка 30 минут, так как все транспорты изначально находятся в автопарке на начальных позициях.
Исходя из реальной модели задачи на примере работы транспортного отдела, можно сделать логичный вывод, что задача является многокритериальной, а цена критериев в течение периода не являются