Реєстраційний номер
0409U002510, Кандидатська дисертація
На здобуття
к.т.н.
Дата захисту
14-04-2009
Статус
Захищена
Назва роботи
Моделювання і розробка методів оптимізації циклічних процесів на транспортних мережах
Здобувач
Гаращенко Ірина Володимирівна,
Керівник Панішев Анатолій Васильович
Опонент Ємець Олег Олексійович
Опонент Гребеннік Ігор Валерійович
Установа, організація, у вченій раді якої відбудеться/відбувся захист
Харківський національний університет радіоелектроніки
Опис
У дисертації показано, що базовим задачам проблеми комівояжера, симетричній і гамільтоновій, притаманні алгоритмічні особливості, які потребують подальшого вивчення: властивість симетрії суттєво впливає на час і точність наближеного розв'язку симетричної задачі комівояжера (СЗК), а гамільтонова задача комівояжера (ГЗК) не завжди розв'язна. Висока точність розв'язку СЗК забезпечується шляхом побудови алгоритму, що складається з двох стадій. Трудомісткість наближеного розв'язку СЗК залежить від алгоритмічних властивостей релаксації і способу перетворення. Запропоновано двоетапний алгоритм пошуку розв'язку ГЗК, який спочатку перевіряє, виходячи із структурних характеристик транспортної мережі, умови її негамільтоновості. Якщо жодна з них не виконується, то алгоритмом типу гілок та меж здійснюється відтинання негамільтонових циклів. Для обчислення нижніх оцінок вартості шуканого маршруту запропоновано модифікований метод розв'язання задачі про призначення, який встановлює нерозв'язність ГЗК у вершинах дерева розгалужень. Проведено обчислювальний експеримент і аналіз отриманих даних.
Дата реєстрації
2009-06-03
Додано/оновлено в НРАТ
2020-04-04 / 2026-06-30
