Пошук академічних текстів

Реєстраційний номер

0409U002510, Кандидатська дисертація

На здобуття

к.т.н., 01.05.02, Математичне моделювання та обчислювальні методи

Дата захисту

14-04-2009

Статус

Запланована

Назва роботи

Моделювання і розробка методів оптимізації циклічних процесів на транспортних мережах

Здобувач

Гаращенко Ірина Володимирівна,

Керівник Панішев Анатолій Васильович
Опонент Ємець Олег Олексійович
Опонент Гребеннік Ігор Валерійович

Опис

У дисертації показано, що базовим задачам проблеми комівояжера, симетричній і гамільтоновій, притаманні алгоритмічні особливості, які потребують подальшого вивчення: властивість симетрії суттєво впливає на час і точність наближеного розв'язку симетричної задачі комівояжера (СЗК), а гамільтонова задача комівояжера (ГЗК) не завжди розв'язна. Висока точність розв'язку СЗК забезпечується шляхом побудови алгоритму, що складається з двох стадій. Трудомісткість наближеного розв'язку СЗК залежить від алгоритмічних властивостей релаксації і способу перетворення. Запропоновано двоетапний алгоритм пошуку розв'язку ГЗК, який спочатку перевіряє, виходячи із структурних характеристик транспортної мережі, умови її негамільтоновості. Якщо жодна з них не виконується, то алгоритмом типу гілок та меж здійснюється відтинання негамільтонових циклів. Для обчислення нижніх оцінок вартості шуканого маршруту запропоновано модифікований метод розв'язання задачі про призначення, який встановлює нерозв'язність ГЗК у вершинах дерева розгалужень. Проведено обчислювальний експеримент і аналіз отриманих даних.

Додано в НРАТ

2020-04-04