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

• Автор: Чернышев, Сергей Владленович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 116 с. : ил.

Оглавление
Введение

1 Обзор существующих алгоритмов решения ЗМТ

1.1 Классификация ЗМТ .

1.2 Методы оптимизации

1.2.1 Метод ветвей и границ

1.2.2 Методы линейной оптимизации

1.2.3 Генетические алгоритмы.

1.2.4 Метод имитации отжига

1.2.5 Поиск с запретами

1.3 Классификация Фишера.

1.4 Классификация Кордо.
1.4.1 Построение начального приближения.
1.4.2 Локальная оптимизация приближения.
1.4.3 Глобальная оптимизация .
1.4.4 Машинное обучение
1.5 Выводы
2 Многофазный алгоритм
2.1 Постановка задачи.
2.2 Общая схема работы алгоритма
2.3 Построение редуцированного графа
2.3.1 Одномерный случай
2.3.2 Двумерный случай.
2.3.3 Многомерный случай
2.4 Метод фиктивных клиентов
2.5 Построение начального приближения.
2.6 Обмен сегментов маршрутов.
2.6.1 Ускорение операции обмена сегментов
2.6.2 Поиск оптимального обмена сегментов
2.7 Разгрузка агентов.
2.8 Постобработка.
2.9 Выводы.
3 Аспекты реализации
3.1 Система Р1апУкПа.
3.2 Архитектура ПапУкПав.
3.2.1 Эксплуатация системы.
3.2.2 Основные части системы
3.2.3 Назначение системы.
3.2.4 Функциональность системы.
3.2.5 Внутренняя структура системы
3.2.6 Расчетный модуль.
3.2.7 Потоки данных
3.3 Формирование исходных данных.
3.3.1 Построение графа дорог.
3.3.2 Геокодирование
4 Практические результаты
4.1 Процедура тестирования
4.1.1 Открытое тестирование.
4.1.2 Внешнее тестирование
4.2 Примеры проектов
4.2.1 Антверпен
4.2.2 Бельгия.
4.3 Визуальное тестирование
4.3.1 Обслуживание изолированных клиентов.
4.3.2 Распределение кластеров между агентами
4.3.3 Привязка клиентов к ребрам графа
4.4 Результаты экспериментов
4.4.1 Алгоритм начального построения .
4.4.2 Зависимость результатов от размеров групп .
4.4.3 Тестовые наборы Геринга и Хомбергера
4.4.4 Задачи большой размерности
4.4.5 Вариация параметров оптимизации
4.4.6 Эффективность оптимизации.
4.4.7 Сравнение расчетных данных с экспериментальными .
4.4.8 Проекты компании СарПсНа.
4.4.9 Параллельные вычисления.
4.5 Выводы
Литература


При этом нужно минимизировать суммарные накладные расходы (время работы, время простоя, суммарные транспортные расходы, количество задействованных агентов и т. Рассматриваемый класс задач представляет интерес с научной точки зрения. В данном направлении на протяжении последних сорока лет ведутся интенсивные исследования [7,,,-,,,,,, ,-,-,,-, ,,,-,-,,,,0,3-7, 9,1]. Огромное количество входных параметров, с одной стороны, делают задачу настолько сложной, что многие существующие алгоритмы либо не применимы, либо плохо адаптируемы к практике. С другой стороны, эта же особенность предоставляет простор для новых исследований. Первые приближенные алгоритмы были получены в -х годах (Clarke G. Wright J. W. []). В -е годы были заложены основные подходы к приближенному решению задач маршрутизации транспорта (Cook Т. Russel R. A., Christofides N. Mingozzi A. Toth P. С середины -х годов исследования сосредоточились на построении метаэвристик, в основе которых лежат такие методы как поиск с исключениями, метод отжига, генетические алгоритмы, метод муравьиных колоний, нейросети и другие (Gendreau М. Osman I. H., Matsuyama Y. В последние десять лет исследования склонились в основном в сторону обработки сложных видов ограничений (Frazzoli Е. Bullo F. Главной целью большинства исследователей является повышение качества результатов счета. В то же время высокий темп роста 1Т-индустрии и интернет-технологий приводит к необходимости создания программных продуктов, ориентированных на широкий круг пользователей. Для задач массового обслуживания количество клиентов может достигать нескольких тысяч, но при этом время работы не должно превышать заданного временного порога. Таким образом, поиск алгоритмов, способных находить решения приемлемого качества за заданное время, становится все более актуальной задачей. Целью работы является разработка моделей и алгоритмов для практического решения задач маршрутизации транспорта на графах больших размерностей, содержащих до ООО клиентов. Разработка моделей и на их основе приближенных алгоритмов для решения многокритериальной задачи о поиске кратчайших путей. Разработка новых и ускорение существующих алгоритмов для решения задачи маршрутизации транспорта с временными окнами и дополнительными ограничениями. Методы исследования. В диссертации применяются методы дискретной оптимизации, математического моделирования, динамического программирования и теории сложности алгоритмов. Научная новизна. Предложен и исследован приближенный алгоритм дня построения Парето-минимальных путей в двумерном случае. Предложен метод фиктивных клиентов для снижения размерности задачи. Создан и исследован алгоритм построения начального приближения, основанный на решении задачи о назначениях. Построена новая структура данных для выполнения операции обмена сегментов маршрутов и доказано, что применение этой структуры позволяет сократить время выполнения таких операций с 0(п) до 0(log2n), где п — общее количество клиентов в маршрутах. С помощью введенного в диссертации понятия «разрез» сформулировано часто выполняющееся на практике условие фильтрации и доказано, что выполнение данного условия позволяет сократить количество разрезов с 0(п2) до 0(п). Разработан многофазный эвристический алгоритм для приближенного решения задачи маршрутизации транспорта с временными окнами, позволяющий учитывать такие дополнительные ограничения, как множественность депо, приоритеты клиентов, зоны обслуживания, множественность характеристик товаров. Практическая ценность. Алгоритмы, опубликованные в данной работе, реализованы на языке С+4- и протестированы в операционных системах Vindows, Ьіпих. Для практического использования создана динамическая библиотека, которая в настоящее время внедрена в программном комплексе РІапУісІіа. Апробация результатов работы. Шестая международная конференция памяти академика А. Публикации. ВАК и 1 статья в международном рецензируемом журнале []. Личный вклад соискателя. Все исследования, результаты которых изложены в диссертационной работе, проведены лично соискателем в процессе научной деятельности.