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

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