Исследование эвристических методов решения задачи коммивояжера

В работе исследованы различные эвристические методы решения задачи коммивояжера и произведена оценка качество полученного решения для асимметричных задач с различным числом посещаемых пунктов. В рамках работы были изучены точный и эвристические методы решения. Исследованы и программно реализованы метод ветвей и границ и метод ближайшего соседа. Метод ближайшего соседа усовершенствован путём введения в рассмотрение фиктивных стартовых пунктов. Произведена программная реализация усовершенствованного метода ближайшего соседа. Предложен способ моделирования изменяющейся дорожной ситуации. Предложен способ генерации матриц временных затрат для задачи коммивояжёра в условиях городского цикла. По результатам работы программных реализаций исходного и усовершенствованного методов сделан вывод об успешной модификации алгоритма. По результатам работы программных реализаций алгоритмов, были сделаны выводы о том, что программная реализация метода ветвей и границ наиболее применима на практике.

Общественные науки в целом
Дипломы

Вуз: Санкт-Петербургский государственный университет (СПбГУ)

ID: 587d365c5f1be77c40d58da6
UUID: f8791901-5084-48fc-b196-a39f96a4b9ee
Язык: Русский
Опубликовано: больше 4 лет назад
Просмотры: 615

Поборчий Игорь Всеволодович

Источник: Санкт-Петербургский государственный университет


0

Комментировать 0

Рецензировать 0

Скачать - 874797 bytes


Поделиться работой
Current View

Рецензии:

  Авторизуйтесь, чтобы добавить рецензию

- у работы пока нет рецензий -

Для лиц старше 18 лет