Адаптивные модели и алгоритмы маршрутизации

• Автор: Перцовский, Александр Константинович
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Санкт-Петербург
• Количество страниц: 127 с. : ил.

Оглавление
Введение
Глава 1. Задача маршрутизации с ограничениями
1.1 Описание предметной области
1.2 Возникновение транспортной задачи и этапы ее становления
1.3 Классическая транспортная задача
1.4 Цели диссертационной работы
1.4.1 Формализация предметной области
1.4.2 Анализ требований к решению
Глава 2. Математические модели доставки грузов с различными ограничениями
2.1. Задачи управления доставками
2.1.1 Обзор существующих моделей
2.1.2 Задача коммивояжера
2.2 Цели и задачи моделирования
2.3 Формализация предметной области. Параметры модели
2.4.Математическая модель доставок грузов(1)
2.5.Математическая модель доставок грузов(П)
Глава 3. Методы решения и оптимизации моделей I и II
3.1 Общая методология оптимизации в моделях I, II
3.2 Методы кластеризации при декомпозиции в процессе решения задачи маршрутизации транспорта
3.2.1 Критерии кластеризации
3.3. Построение начального разбиения
3.3.1 Метод дальней точки
3.3.2 Метод, основанный на алгоритме Свира
3.4 Алгоритм кластеризации с известным числом кластерных географических районов
3.4.1. Определение точки, рассматриваемой на текущей итерации построения кластерных географических районов. Метод свободной точки
3.4.2 Алгоритм улучшения разбиения на кластерные географические районы

3.5. Метод решения задачи коммивояжера
3.6. Итерационный метод решения моделей I и II
Глава 4. Программная реализация алгоритмов решения моделей I и II
4.1 Архитектура программного комплекса
4.2 Использованные технологии
4.3 Информационно-логическая модель. Реализация схемы данных
4.4 Реализация службы кэширования графа транспортной доступности
4.5 Реализация модуля построения рейса
4.6 Реализация модуля построения кластерных географических районов
4.7 Описание интерфейса пользователя
Заключение
Список литературы

Введение
1. Актуальность темы исследования
Развитие информационных технологий и повсеместная доступность ЭВМ позволяют повысить эффективность принятия управленческих решений, связанных с большой вычислительной работой. В частности, для ряда отдельно взятых организаций важным является вопрос об оптимальном управлении транспортными потоками. Постоянный рост рынка транспортных услуг обостряет конкуренцию между игроками. В такой обстановке существенным преимуществом является оптимальное планирование обслуживания доставок. Решение дайной задачи возможно при помощи математических методов, имитационных и эвристических алгоритмов с использованием современных вычислительных мощностей.
Исследованию и решению задач маршрутизации транспорта посвящено большое количество работ в зарубежной литературе. В виду специфики развития отечественной науки и экономики на протяжении XX века в русскоязычной литературе вопросы управления доставками и маршрутизации транспортных средств стали рассматриваться относительно недавно. Рост интереса к проблеме начался с 90х годов после перехода страны на рыночную основу экономики.
Изучением вышеописанных вопросов занимается транспортная логистика. Большинство задач, рассматриваемых в рамках данной дисциплины, являются ХР-полными (к ИР-полным задачам относят задачи, которые невозможно разрешить за полиномиальное время). Задачи такой сложности в общем случае не разрешимы точными методами, поэтому для получения решения применяются различные эвристические и генетические методы. В возникающих практических задачах указанные методы являются ресурсозатратными, и, следовательно, необходимо модифицировать их с учетом возникающих ограничений и специфики каждого класса задач. Необходимость этого обусловлена тем, что быстродействие имеющихся у

• грузовместимость - ограничение на максимальный объем, который вмещает транспортное средство;
• грузоподъемность - ограничение на максимальный вес, который вмещает транспортное средство.
Теперь необходимо сформулировать понятия рейса - сущности, которую нужно построить для решения задачи
Рейсом будем называть упорядоченную последовательность географических точек, при этом для каждой точки, входящей в рейс задано время ее посещения, а также список доставок, обслуженных при визите в данную точку. Рейсу также приписывается определенное транспортное средство и водитель, которые осуществят его обслуживание.
Таким образом, рейс можно охарактеризовать следующими
параметрами:
• • (рЛ ~ упорядоченная последовательность географических точек;
• {£;} - упорядоченная последовательность моментов посещения
соответствующих пунктов в рейсе;
• £> = - доставки, обслуженные в ходе выполнения рейса, где i -
индекс пункта доставки;
• Т¥ - суммарный вес доставок, осуществленных в рейсе;
• {ищ;} - загруженность транспортного средства по весу при посещении [-го пункта рейса;
• ТУ - суммарный объем доставок, осуществленных при выполнении рейса;
• - загруженность транспортного средства по объему при посещении
ьго пункта рейса;
• Время выполнения рейса - временной интервал от выезда машины из начальной точки до прибытья в конечную точку.