Search academic texts

Registration Number

0409U002510, Candidate dissertation

Status

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

Date

14-04-2009

popup.evolution

o

Title

Modeling and development of methods of cyclic processes optimization on transport networks

Author

Garashchenko Iryna Volodymyrivna,

popup.head Panishev Anatoly Vasyliovych
popup.opponent Ємець Олег Олексійович
popup.opponent Гребеннік Ігор Валерійович

Description

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

popup.nrat_date

2020-04-04