Разработка алгоритмов многоальтернативной маршрутизации грузоперевозок в системах транспортной логистики на основе эволюционных методов

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

СОДЕРЖАНИЕ
Введение
Глаза 1. Анализ задач информационных систем транспортной логистики, функционирующих в пределах города, и методов их решения
1.1 Область применения, задачи и функции информационных систем транспортной логистики.

1.2 Пос тановка задачи маршрутизации транспорта.

1.3 Методы решения задачи маршрутизации транспорта

1.4 Алгоритмы нахождения оптимального пути между вершинами дорожного графа

1.5 Использование геоинформационных компонент в составе информационных систем транспортной логистики.

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

Глава 2. Разработка алгоритма решения задачи поиска оптимального пути между вершинами дорожного графа с нерегулярным весом ребер.

2.1. Алгоритма А для решения задачи поиска путей на графе

2.2 Модификация алгоритма А и оценка результатов работы
Глава 3. Разработка алгоритма нахождения глобального плана доставки задачи маршрутизации транспорта
3.1 Постановка задачи оптимизации глобального плана доставки
3.2 Разработка модифицированного меметического алгоритма для решения задачи маршрутизации транспорта
3.3 Алгоритма муравьиной колонии в качестве алгоритма локального поиска.
Глава 4 Разработка проблемноориентированного программного обеспечения многоальтернативной маршрутизации грузоперевозок.
4.1. Модульная структура системы маршрутизации
4.2 Интерфейс программирования приложений.
4.3 База данных приложения и объектнореляционное отображение.
4.4. Разработка геоинформационной компоненты в составе системы маршрутизации.
4.5. Модуль решения задач маршрутизации проблемно
ориентированного программного обеспечения.
4.6 Визуальный интерфейс программного средства.
Заключение
Список литературы


В работах, опубликованных в соавторстве и приведенных а автореферате, лично соискателю принадлежат следующие результаты: [1] - алгоритм решения задачи поиска кратчайшего пути на карте между двух точек, [2] - разработка геоииформационной компоненты в составе подсистемы маршрутизации, [5] -анализ использования ГИС в составе АИС транспортной логистики, [6] - методы решения задач маршрутизации транспортной логистики, [3, 4, 7] - алгоритм решения задачи маршрутизации для парка автотранспортных средств, Щ - разработка специального программного обеспечения, [9] - муравьиный алгоритм как алгоритм локального поиска при решении задач маршрутизации. Материалы диссертации отражены также в 3 научно-технических отчетах НИОКР. Структура п объем работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 3 страницах, списка литературы из 4 наименований, содержит рисунка и 3 таблицы. В первой главе показана необходимость использования информационно-компьютерной поддержки для эффективного решения задачи маршрутизации транспорта. Такой поддержкой выступают информационные системы. Проведен анализ задач и требований, предъявляемых к современным информационным системам транспортной логистики. Ставится задача нахождения оптимального по заданному критерию (минимальному суммарному времени, минимальной суммарной стоимости, максимальному коэффициенту загрузки транспортных средств) плана маршрутов для парка автотранспортных средств с ограничениями грузоподъемности на ориентированном графе с нерегулярным весом ребер с учетом выполнения концепции доставки «точно в срок». Вследствие необходимости решения указанных задач был проведен системный анализ точных и приближенных методов решения задач маршрутизации транспортной логистики. Сделаны выводы о целесообразности использования меметических алгоритмов. Проанализированы алгоритмы нахождения оптимального пути между вершинами дорожного графа. Оптимальным алгоритмом является алгоритм А* и его модификации. Также показана необходимость реализации геоинформационной компоненты в составе подсистемы оптимизации планирования доставки. Для обеспечения надежности работы алгоритмов, необходимо, чтобы структура специального программного обеспечения отвечала принципам многоальтерпативных систем (Подвальный С. Л.), т. В конце главы сформулированы цели и задачи исследования. Вторая глава посвящена разработке алгоритма, решающего задачу нахождения оптимального пути между вершинами дорожного графа с нерегулярным весом ребер, определяемым динамикой пропускной способности дорожной сети распределенной по времени суток. При построении глобального плана доставки необходимо каждую итерацию строить маршруты для каждого транспортного средства, учитывая нерегулярную скорость движения по дорогам в течение дня. За счет того, что основной алгоритм постоянно обращается к алгоритму построения маршрутов, последний является «узким местом» процедуры оптимизации. Данный алгоритм построен па базе алгоритма А*, как наилучшем алгоритме для поиска оптимальных путей в различных пространствах, в частности на дорожном графе. А* является полным в том смысле, что он всегда находит решение, если таковое существует. Исследованы различные структуры данных, которые могут применяться в работе алгоритма А*. Приведена их сравнительная характеристика. В алгоритме использованы несинхронизированные хэш-габлицы, как наиболее подходящие структуры данных в плане скорости работы, для поставленной задачи. Алгоритм А* оптимизирован для поставленной задачи нахождения оптимального пути между двух точек на карте с ограничениями и нерегулярной средней скоростью в течение дня. Реализован метод оптимизации графа перед началом работы алгоритма, который заключается в замене нескольких последовательных ребер с одинаковыми значениями атрибутов (например, изогнутая дорога) одним ребром. Очередь сортировки узлов организована по принципу LIFO для организации поиска в глубину. Исследована реализация двунаправленного поиска, однако она показала отрицательные результаты за счет введения дополнительных структур данных. Реализован метод контроля оценки эвристического приближения, за счет чего выполняется более направленный поиск. Результаты работы алгоритма А* проанализированы для простого и сложного случая. Оценки результатов сведены в таблицу.