Развитие метода ветвей и границ в задаче поиска оптимального кольцевого маршрута - Овезгельдыев, А.О.; Морозов, А.В. (Кибернетика и системный анализ, 2013)
Побудовано математичну модель прикладної задачі оптимізації замкнених маршрутів — кільцевої задачі про сільського листоношу. Запропоновано двоетапний метод типу гілок та меж, який знаходить розв’язок або встановлює факт нерозв’язності задачі. Перший етап методу включає перевірку достатніх умов нерозв’язності і процедуру вершинно-реберного перетворення. Це дає можливість скоротити час пошуку розв’язку на другому етапі методу за допомогою запропонованої модифікації методу Літтла. У ній вперше застосовано спосіб розбиття множини розв’язків на підмножини, що не перетинаються, за допомогою трьох правил розгалуження і обчисленням відповідних нижніх оцінок вартості оптимального розв’язку. Запропонований метод коректно виконує пошук оптимального розв’язку гамільтонової задачі про сільського листоношу, загальної і гамільтонової задачі комівояжера.