Введение
1 Обзор существующих алгоритмов решения ЗМТ 11
1.1 Классификация ЗМТ 11
1.2 Методы оптимизации 13
1.2.1 Метод ветвей и границ 13
1.2.2 Методы линейной оптимизации 14
1.2.3 Генетические алгоритмы 16
1.2.4 Метод имитации отжига 17
1.2.5 Поиск с запретами 19
1.3 Классификация Фишера 19
1.4 Классификация Кордо 21
1.4.1 Построение начального приближения 22
1.4.2 Локальная оптимизация приближения 23
1.4.3 Глобальная оптимизация 25
1.4.4 Машинное обучение 27
1.5 Выводы 30
2 Многофазный алгоритм 32
2.1 Постановка задачи 32
2.2 Общая схема работы алгоритма 34
2.3 Построение редуцированного графа 35
2.3.1 Одномерный случай 36
2.3.2 Двумерный случай 36
2.3.3 Многомерный случай 39
2.4 Метод фиктивных клиентов 52
2.5 Построение начального приближения 54
2.6 Обмен сегментов маршрутов 55
2.6.1 Ускорение операции обмена сегментов 55
2.6.2 Поиск оптимального обмена сегментов 59
2.7 Разгрузка агентов 62
2.8 Постобработка 63
2.9 Выводы 64
3 Аспекты реализации 66
3.1 Система PlanVidia 66
3.2 Архитектура PlanVidia 68
3.2.1 Эксплуатация системы 68
3.2.2 Основные части системы 69
3.2.3 Назначение системы 70
3.2.4 Функциональность системы 71
3.2.5 Внутренняя структура системы 71
3.2.6 Расчетный модуль 73
3.2.7 Потоки данных 74
3.3 Формирование исходных данных 76
3.3.1 Построение графа дорог 76
3.3.2 Геокодирование 78
4 Практические результаты 80
4.1 Процедура тестирования 80
4.1.1 Открытое тестирование 80
4.1.2 Внешнее тестирование 81
4.2 Примеры проектов 81
4.2.1 Антверпен 81
4.2.2 Бельгия 84
4.3 Визуальное тестирование 85
4.3.1 Обслуживание изолированных клиентов 85
4.3.2 Распределение кластеров между агентами 85
4.3.3 Привязка клиентов к ребрам графа 87
4.4 Результаты экспериментов 88
4.4.1 Алгоритм начального построения 88
4.4.2 Зависимость результатов от размеров групп . 88
4.4.3 Тестовые наборы Геринга и Хомбергера 89
4.4.4 Задачи большой размерности 90
4.4.5 Вариация параметров оптимизации 91
4.4.6 Эффективность оптимизации 92
4.4.7 Сравнение расчетных данных с экспериментальными 93
4.4.8 Проекты компании CapVidia 95
4.4.9 Параллельные вычисления 96
4.5 Выводы 97
Литература 101
