Search academic texts

Information × Registration Number 0409U002510, Candidate dissertation Status к.т.н. 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 У дисертації показано, що базовим задачам проблеми комівояжера, симетричній і гамільтоновій, притаманні алгоритмічні особливості, які потребують подальшого вивчення: властивість симетрії суттєво впливає на час і точність наближеного розв'язку симетричної задачі комівояжера (СЗК), а гамільтонова задача комівояжера (ГЗК) не завжди розв'язна. Висока точність розв'язку СЗК забезпечується шляхом побудови алгоритму, що складається з двох стадій. Трудомісткість наближеного розв'язку СЗК залежить від алгоритмічних властивостей релаксації і способу перетворення. Запропоновано двоетапний алгоритм пошуку розв'язку ГЗК, який спочатку перевіряє, виходячи із структурних характеристик транспортної мережі, умови її негамільтоновості. Якщо жодна з них не виконується, то алгоритмом типу гілок та меж здійснюється відтинання негамільтонових циклів. Для обчислення нижніх оцінок вартості шуканого маршруту запропоновано модифікований метод розв'язання задачі про призначення, який встановлює нерозв'язність ГЗК у вершинах дерева розгалужень. Проведено обчислювальний експеримент і аналіз отриманих даних. Registration Date 2009-04-14 popup.nrat_date 2020-04-04 Close