гамільтонів цикл, гамильтонов цикл ; задачі маршрутизації,задачи маршрутизации ; задача комівояжера, задача коммивояжера ; кільцеві маршрути, кольцевые маршруты ; математичні моделі, математические модели, mathematical models ; метод Літтла, метод Литтла ; транспортні мережі, транспортные сети

Целью работы является построение математических моделей для решения новых задач оптимизации кольцевых маршрутов на транспортной сети, что повышает эффективность транспортных перевозок пассажиров и грузов. Впервые разработаны математические модели для решения ГЗСП (гамильто- новой задачи о сельском почтальоне) и КЗСП (кольцевой задачи о сельском почтальоне).Получил дальнейшее развитие двухэтапный точный переборный метод типа ветвей и границ, который находит оптимальное решение ГЗСП или КЗСП, либо устанавливает факт неразрешимости задачи; первый этап метода включает проверку достаточных условий неразрешимости задачи и процедуру вершинно-реберного преобразования, устанавливающую один из трех возмож- ных результатов: построено оптимальное решение; задача не имеет решения; поиск оптимального решения необходимо продолжить на преобразованном графе со степенями вершин, большими 2, и с множеством фиксированных ребер, образующих паросочетание, что дает возможность сократить время поиска точ- ного р

• УДК // Загальні питання комбінаторних алгоритмів. Поліномінальні та NP- повні задачі