Введение 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
Приложение
В жизни современных предприятий самого разного рода существенное место занимают транспортные потоки: для каждой компании актуален вопрос о своевременной доставке товара потребителям в кратчайшие сроки. Для осуществления этого руководство компании, по сути, занимается решением так называемой задачи коммивояжера.
Представим себе ситуацию, в том или ином виде возникающую на любом предприятии, которое специализируется на доставке товаров и грузов. Допустим, курьеру компании необходимо развезти продукцию в определенное число мест и вернуться в офис. Задача формулируется следующим образом: определить в каком порядке курьер должен посещать клиентов, чтобы дорога заняла наименьшее время (все пункты посещаются один раз).
Задача коммивояжера в такой постановке является NP-трудной. Это означает, что не существует алгоритма, который находил бы точное решение задачи коммивояжера за полиномиальное время. Единственным же алгоритмом, который в принципе может гарантировать нахождение точного решения, является метод полного перебора. Однако работа программы, реализующей этот алгоритм, занимает адекватное время только при очень малой размерности входных данных (при числе пунктов < 20).
В связи с отсутствием эффективных точных методов решения задачи коммивояжера, становится необходимым использование методов эвристических. Эвристическими называют методы, которые будучи основанными на некой эвристике (правиле), не всегда следующей из строгих математических принципов, в подавляющем большинстве случаев дают решение, близкое к точному.
Таким образом, ставится следующая цель: исследовать различные эвристические методы решения задачи коммивояжера и оценить качество полученного решения для задач с различным числом посещаемых пунктов.
Для реализации поставленной в работе цели ставятся следующие задачи:
• изучить единственный точный метод решения задачи коммивояжера - метод полного перебора,
• исследовать некоторые эвристические алгоритмы,
• программно реализовать их,
• проанализировать время и результаты работы программных реализаций алгоритмов,
• улучшить алгоритмы, если это возможно,
• разработать способ учета изменяющейся дорожной обстановки в методах,
• разработать способ генерации входных данных для задачи коммивояжера с учетом специфики постановки задачи,
• организовать возможность параллельной работы методов на разных экземплярах задач,
• сравнить время и результаты работы программных реализаций усовершенствованных алгоритмов с исходными.
Поставленные в данной работе цели и задачи были успешно выполнены:
• изучена литература, посвященная задаче, отмечены основные направления современных исследований в данной области;
• изучен метод полного перебора; показано, что он не может успешно применяться на практике ввиду быстрого роста времени работы его программной реализации при увеличении количества посещаемых пунктов;
• подробно описаны метод ближайшего соседа и метод ветвей и границ, проиллюстрированы шаги работы алгоритмов, приведены их логические схемы, оба метода успешно реализованы на языке C++;
• на основе широкой выборки сгенерированных матриц построены сравнительные таблицы и графики, на основании которых были сделаны выводы о полезности применения алгоритмов на практике;
• произведено усовершенствование метода ближайшего соседа путем введения в рассмотрение фиктивных стартовых пунктов; на основании применения усовершенствованного метода к различным экземплярам задачи, сделан вывод о том, что эффективность метода повысилась;
• разработана модель учета изменения дорожной ситуации, проведена демонстрация работы модели на примере;
• разработан удобный способ генерации входных данных, обоснована его
адекватность специфике рассматриваемой постановки задачи;
разработан скрипт, позволяющий генерировать входные данные и осуществлять программное решение задачи одновременно для нескольких экземпляров задачи.
Результаты проделанной работы докладывались и публиковались на конференциях с международным участием, проводимых Санкт-Петербургским государственным университетом и Санкт-Петербургским политехническим университетом Петра Великого, а так же на международной научно-исследовательской конференции «INFO-эксперт»- 2016. Статья «Один из способов моделирования дорожной ситуации для решения задачи коммивояжера в условиях города» была отмечена дипломом победителя II-ой степени в номинации «Computer science - IT- эксперт» на международной научно-исследовательской конференции «ЮТО-эксперт»-2016.
Помощь студентам и аспирантам в выполнении работ от наших партнеров
