Введение 3
Глава 1. Обзор транспортных задач. Актуальность задачи коммивояжера 5
1.1. Транспортные задачи 5
1.2. Постановка задачи коммивояжера 7
Глава 2. Алгоритмы решения задачи коммивояжера 8
2.1. Метод полного перебора 8
2.2. Метод ближайшего соседа 11
2.3. Усовершенствованный метод ближайшего соседа 15
2.4. Метод ветвей и границ 18
Глава 3. Моделирование загруженности транспортной сети 25
3.1. Дорожные заторы (пробки) 25
Глава 4. Сравнительный анализ эвристических методов решения задачи коммивояжера 29
4.1. Разработка скрипта для параллельных генерации и вычислений алгоритмов 29
4.2. Способ генерации матриц времен для задачи коммивояжера в условиях городского цикла 31
4.3. Сравнительный анализ эвристических методов решения задачи коммивояжера 32
Выводы 37
Заключение 38
Список литературы 40
Приложение 43
В жизни современных предприятий самого разного рода существенное место занимают транспортные потоки: для каждой компании актуален вопрос о своевременной доставке товара потребителям в кратчайшие сроки. Для осуществления этого руководство компании, по сути, занимается решением так называемой задачи коммивояжера.
Представим себе ситуацию, в том или ином виде возникающую на любом предприятии, которое специализируется на доставке товаров и грузов. Допустим, курьеру компании необходимо развезти продукцию в определенное число мест и вернуться в офис. Задача формулируется следующим образом: определить в каком порядке курьер должен посещать клиентов, чтобы дорога заняла наименьшее время (все пункты посещаются один раз).
Задача коммивояжера в такой постановке является NP-трудной. Это означает, что не существует алгоритма, который находил бы точное решение задачи коммивояжера за полиномиальное время. Единственным же алгоритмом, который в принципе может гарантировать нахождение точного решения, является метод полного перебора. Однако работа программы, реализующей этот алгоритм, занимает адекватное время только при очень малой размерности входных данных (при числе пунктов < 20).
В связи с отсутствием эффективных точных методов решения задачи коммивояжера, становится необходимым использование методов эвристических. Эвристическими называют методы, которые будучи основанными на некой эвристике (правиле), не всегда следующей из строгих математических принципов, в подавляющем большинстве случаев дают решение, близкое к точному.
Таким образом, ставится следующая цель: исследовать различные эвристические методы решения задачи коммивояжера и оценить качество полученного решения для задач с различным числом посещаемых пунктов.
Для реализации поставленной в работе цели ставятся следующие задачи:
• изучить единственный точный метод решения задачи коммивояжера - метод полного перебора,
• исследовать некоторые эвристические алгоритмы,
• программно реализовать их,
• проанализировать время и результаты работы программных реализаций алгоритмов,
• улучшить алгоритмы, если это возможно,
• разработать способ учета изменяющейся дорожной обстановки в методах,
• разработать способ генерации входных данных для задачи коммивояжера с учетом специфики постановки задачи,
• организовать возможность параллельной работы методов на разных экземплярах задач,
• сравнить время и результаты работы программных реализаций усовершенствованных алгоритмов с исходными.
Поставленные в данной работе цели и задачи были успешно выполнены:
• изучена литература, посвященная задаче, отмечены основные направления современных исследований в данной области;
• изучен метод полного перебора; показано, что он не может успешно применяться на практике ввиду быстрого роста времени работы его программной реализации при увеличении количества посещаемых пунктов;
• подробно описаны метод ближайшего соседа и метод ветвей и границ, проиллюстрированы шаги работы алгоритмов, приведены их логические схемы, оба метода успешно реализованы на языке C++;
• на основе широкой выборки сгенерированных матриц построены сравнительные таблицы и графики, на основании которых были сделаны выводы о полезности применения алгоритмов на практике;
• произведено усовершенствование метода ближайшего соседа путем введения в рассмотрение фиктивных стартовых пунктов; на основании применения усовершенствованного метода к различным экземплярам задачи, сделан вывод о том, что эффективность метода повысилась;
• разработана модель учета изменения дорожной ситуации, проведена демонстрация работы модели на примере;
• разработан удобный способ генерации входных данных, обоснована его адекватность специфике рассматриваемой постановки задачи;
• разработан скрипт, позволяющий генерировать входные данные и осуществлять программное решение задачи одновременно для нескольких экземпляров задачи.
Результаты проделанной работы докладывались и публиковались на конференциях с международным участием, проводимых Санкт-Петербургским государственным университетом и Санкт-Петербургским политехническим университетом Петра Великого, а так же на международной научно-исследовательской конференции «INFO-эксперт»- 2016. Статья «Один из способов моделирования дорожной ситуации для решения задачи коммивояжера в условиях города» была отмечена дипломом победителя II-ой степени в номинации «Computer science - IT- эксперт» на международной научно-исследовательской конференции «ЮТО-эксперт»-2016.
