Введение
1 Обзор алгоритмов решения ЗМТ 13
1.1 Терминология 13
1.2 Постановка ЗМТ 14
1.3 Классификация алгоритмов для решения ЗМТ 17
1.4 Конструктивные классические алгоритмы 19
1.4.1 Алгоритм Кларка-Райта 19
1.4.2 Расширения алгоритма Кларка-Райта 20
1.4.3 Последовательный алгоритм вставки Моля-Джеймсона . 22
1.4.4 Последовательный алгоритм вставки Кристофидеса-Мингоззи-Тосса 23
1.5 Двухфазные классические алгоритмы 24
1.5.1 Алгоритм заметания 25
1.5.2 Алгоритм Фишера-Джекумера 26
1.5.3 Алгоритм Брамела-Симчи-Леви 26
1.5.4 Алгоритм лепестков 27
1.5.5 Методы с решением ЗК перед кластеризацией 30
1.6 Классические улучшающие алгоритмы 31
1.6.1 Оптимизация отдельного маршрута 31
1.6.2 Алгоритмы для улучшения нескольких маршрутов . 32
1.7 Метаэвристики 33
1.8 Алгоритм Османа поиска с исключениями 34
1.8.1 Понятие окрестности решения 35
1.8.2 Стратегия запрещения 35
1.8.3 Стратегия освобождения удаления из списка исключений 36
1.8.4 Стратегия выбора 36
1.8.5 Специальная структура данных для стратегии "наилучший подходящий" 37
1.8.6 Функция для определения длины списка исключений . 38
1.8.7 Критерий остановки 38
1.8.8 Общий вид алгоритма 39
1.9 Другие варианты поиска с исключениями 39
1.9.1 Алгоритм Генро-Герца-Л апорте 40
1.9.2 Алгоритм Тейлорда 41
1.9.3 Алгоритм Ксю-Келли 42
1.9.4 Алгоритм Риго-Рокарола 42
1.10 Моделируемый отжиг 43
1.10.1 Ранние алгоритмы моделируемого отжига для решения ЗМТ 44
1.10.2 Алгоритм Османа 44
1.11 Детерминированный отжиг 46
1.12 Генетический алгоритм 46
1.12.1 Основной вид генетического алгоритма 47
1.12.2 Применение генетического алгоритма для задач упорядочивания 48
1.12.3 Применение алгоритма для решения ЗМТ 48
1.13 Алгоритм на основе муравьиных колоний 50
1.14 Нейронные сети 52
1.15 Выводы 55
2 Сбалансированные алгоритмы решения ЗМТ 57
2.1 Сбалансированная ЗМТ 59
2.2 Вычисление количества вершин для каждого транспортного средства в СЗМТ 60
2.3 Общий вид процедуры дихотомического деления вершин на группы 62
2.4 Процедура дихотомической кластеризации для СЗМТ 63
2.5 Другие варианты дихотомического алгоритма для СЗМТ . 67
2.6 Обменная оптимизация при дихотомическом делении 67
2.7 Алгоритм разрезания общего маршрута для СЗМТ 68
2.8 Алгоритм заметания для СЗМТ 70
2.9 Вычислительный эксперимент для СЗМТ 72
2.10 Сбалансированный алгоритм кластеризации для ЗМТУГ . 77
2.11 Рекурсивная процедура дихотомического сбалансированного разделения вершин 79
2.12 Вычислительный эксперимент для ЗМТУГ 84
2.13 Дополнительные варианты сбалансированного алгоритма для ЗМТУГ 88
2.13.1 Вариант сбалансированного алгоритма с бэктрекингом 91
2.13.2 Ограничение количество вершин в маршрутах 93
2.14 Вариант сбалансированного алгоритма для нескольких депо 95
2.15 Использование геометрической информации для процедуры деления вершин 97
2.16 Выводы 101
3 Реализация алгоритмов решения ЗМТ 102
3.1 Основные понятия 102
3.2 Обработка несимметричных матриц 105
3.3 Пользовательский интерфейс 106
3.4 Интерфейс библиотеки для решения ЗМТ 108
3.4.1 Описание функции SolveBCVRP 113
3.4.2 Описание функции SolveVRP 115
3.5 Внутренняя структура библиотеки алгоритмов решения ЗМТ 116
3.6 Выводы 121
Заключение 124
Список литературы 126
Приложение 136
