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

• Автор: Пожидаев, Михаил Сергеевич
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Томск
• Количество страниц: 136 с. : ил.

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

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

1.1 Терминология

1.2 Постановка ЗМТ

1.3 Классификация алгоритмов для решения ЗМТ

1.4 Конструктивные классические алгоритмы.

1.4.1 Алгоритм КларкаРайта.

1.4.2 Расширения алгоритма КларкаРайта.

1.4.3 Последовательный алгоритм вставки МоляДжеймсона .

1.4.4 Последовательный алгоритм вставки КристофидесаМингоззиТосса

1.5 Двухфазные классические алгоритмы.
1.5.1 Алгоритм заметания
1.5.2 Алгоритм ФишераДжекумера.
1.5.3 Алгоритм БрамелаСимчиЛеви
1.5.4 Алгоритм лепестков
1.5.5 Методы с решением ЗК перед кластеризацией.
1.6 Классические улучшающие алгоритмы
1.6.1 Оптимизация отдельного маршрута.
1.6.2 Алгоритмы для улучшения нескольких маршрутов .
1.7 Метаэвристики.
1.8 Алгоритм Османа поиска с исключениями.
1.8.1 Понятие окрестности решения
1.8.2 Стратегия запрещения
1.8.3 Стратегия освобождения удаления из списка исключений
1.8.4 Стратегия выбора
1.8.5 Специальная структура данных для стратегии наилучший подходящий.
1.8.6 Функция для определения длины списка исключений . .
1.8.7 Критерий остановки
1.8.8 Общий вид алгоритма.
1.9 Другие варианты поиска с исключениями.
1.9.1 Алгоритм ГенроГерцаЛапорте
1.9.2 Алгоритм Тейлорда.
1.9.3 Алгоритм КсоКелли.
1.9.4 Алгоритм РигоРокарола
1. Моделируемый отжиг . . . .
11 Ранние алгоритмы моделируемого отжига для решения ЗМТ.
12 Алгоритм Османа
1. Детерминированный отжиг.
1. Генетический алгоритм.
11 Основной вид генетического алгоритма.
12 Применение генетического алгоритма для задач упорядочивания
13 Применение алгоритма для решения ЗМТ.
1. Алгоритм на основе муравьиных колоний.
1. Нейронные сети
1. Выводы
2 Сбалансированные алгоритмы решения ЗМТ
2.1 Сбалансированная ЗМТ
2.2 Вычисление количества вершин для каждого транспортного средства в СЗМТ
2.3 Общий вид процедуры дихотомического деления вершин
на группы.
2.4 Процедура дихотомической кластеризации для СЗМТ
2.5 Другие варианты дихотомического алгоритма для СЗМТ
2.6 Обменная оптимизация при дихотомическом делении
2.7 Алгоритм разрезания общего маршрута для СЗМТ.
2.8 Алгоритм заметания для СЗМТ
2.9 Вычислительный эксперимент для СЗМТ
2. Сбалансированный алгоритм кластеризации для ЗМТУГ
2. Рекурсивная процедура дихотомического сбалансирован ного разделения вершин
2. Вычислительный эксперимент для ЗМТУГ
2. Дополнительные варианты сбалансированного алгоритма для ЗМТУГ
21 Вариант сбалансированного алгоритма с бэктрекингом .
22 Ограничение количество вершин в маршрутах.
2. Вариант сбалансированного алгоритма для нескольких депо . .
2. Использование геометрической информации для процедуры деления вершин
2. Выводы.
3 Реализация алгоритмов решения ЗМТ
3.1 Основные понятия.
3.2 Обработка несимметричных матриц
3.3 Пользовательский интерфейс.
3.4 Интерфейс библиотеки для решения ЗМТ.
3.4.1 Описание функции 8о1усВСУР
3.4.2 Описание функции 8о1уеУЛР.
3.5 Внутренняя структура библиотеки алгоритмов решения ЗМТ .
3.6 Выводы.
Заключение
Список литературы


Разработка и исследование алгоритмов, проведение вычислительною эксперимента, реализация и отладка программного обеспечения осуществлялись автором самостоятельно. Гл. ЗМТ и наиболее известных приближённых алгоритмов её решения. Кроме общего вида задачи, приводятся описания ЗМТ с учётом грузоподъёмности транспортных средств, ЗМТ с ограничением количества вершин в каждом маршруте, а также развитие ЗМТ для случая нескольких депо. Упоминаются некоторые дополнительные виды задачи, получившие распространение на практике, но не рассматриваемые детально в работе. В разд. ЗМТ с общей характеристикой каждой группы. Точные методы решения этой задачи не упоминаются в силу неприемлемо больших затрат вычислительных ресурсов для их применения. Описаны следующие алгоритмы: алгоритм Кларка-Райта с некоторыми расширениями, последовательный алгоритм вставки Моля-Джсймсона, последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса, алгоритм заметания, алгоритм Фишера-Джскумера, алгоритм Брамела-Симчи-Леви, алгоритм лепестков, а также приведены некоторые идеи подходов, выполняющих последовательное улучшение уже найденного решения. Перечисленные алгоритмы составляют группу так называемых классических эвристик. Известен ряд новых идей, традиционно относимых к другой группе метаэвристик. Мегаэвристики являются общими методами решения задач комбинаторной оптимизации, широко известными и за пределами области алгоритмов решения ЗМТ. Их применение для ЗМТ показывает неплохие результаты, но затруднено на практике из-за недостаточно конкретной формулировки. Рассматриваются поиск с исключениями, моделируемый и детерминированный отжиг, генетический алгоритм, алгоритм на основе муравьиных колоний и нейронные сети. В гл. Предлагается новая формулировка ЗМТ с наложенным условием сбалансирования, далее называемая сбалансированной ЗМТ. Она требует, чтобы количество вершин для каждой пары построенных маршрутов не отличалось бы более, чем на единицу. Для получения окончательного решения ЗМТ требуется решить ЗК внутри каждой группы. Кратко перечислены направления поиска, показавшие во время исследований ухудшение результатов, а также рассмотрено влияние условия сбалансирования на такие известные методы, как алгоритм заметания и разрезание общего маршрута. В каждом случае показано уменьшение времени работы алгоритмов. Приводятся результаты проведённого вычислительного эксперимента для алгоритмов решения сбалансированной ЗМТ. Развитие идеи сбалансированного дихотомического деления позволило создать новый алгоритм решения стандартной ЗМТ с учётом грузоподъёмности, показывающий хорошие результаты качества для больших наборов входных данных при сравнительно непродолжительном времени работы. Проведён вычислительный эксперимент, сравнивающий новый алгоритм с алгоритмом Османа поиска с исключениями. В вычислительном эксперименте была рассмотрена возможность запуска алгоритма Османа поверх решения, полученного алгоритмом сбалансированного дихотомического деления. Новый алгоритм показывает хорошие результаты для наборов данных с более, чем 0 вершинами. После вычислительного эксперимента описаны две разновидности сбалансированного дихотомического алгоритма: вариант с бэктрекингом, показывающий уменьшение стоимости решений в ущерб равномерности загрузки транспортных средств, и вариант, позволяющий задать явное ограничение максимального количества вершин в каждом маршруте. Дальнейшее развитие идеи сбалансированного деления позволило создать алгоритм, решающий ЗМТ для нескольких депо. Приводятся результаты вычислительного эксперимента с запуском алгоритма для задач с двумя и четырьмя депо. Гл. Перечислены основные этапы решения ЗМТ на практике: загрузка данных карты из внешнего файла, построение транспортного слоя, построения графа для получения подходящей математической модели транспортной сети и вычисления матрицы стоимости переездов, выбор желаемых пунктов обслуживания и депо, запуск алгоритмов и оценивание результатов. Подробно описаны особенности каждого этапа и связанные с ним понятия.