К. С. Подшивалова, Э. Р. Домке, С. Ф. Подшивалов, С. А. Жесткова
ИСПОЛЬЗОВАНИЕ ФИКТИВНЫХ УЗЛОВ
ДЛЯ ОПРЕДЕЛЕНИЯ ОПТИМАЛЬНОЙ КОМБИНАЦИИ
МАРШРУТОВ С СОВМЕСТНЫМ ЦЕНТРОМ
Аннотация. <...> Предложено совершенствование метода ветвей и границ, позволяющее посещать вершины графа несколько раз. <...> Представлено решение задачи маршрутизации для комбинации маршрутов с симметричной матрицей весов, выходящих из одного центра. <...> Введение
Задача поиска оптимальных маршрутов на взвешенном графе имеет самый общий характер. <...> На практике выбор оптимального маршрута при решении задачи коммивояжера подразумевает однократное появление каждого события. <...> Наиболее сложные и интересные задачи стоят перед исследователями
в областях, где события могут накладываться друг на друга, повторяться и
связаны с поиском оптимальной комбинации одновременно нескольких
маршрутов на графе. <...> Постановка задачи
В классической задаче коммивояжера необходимо посетить все вершины графа один раз так, чтобы вес маршрута был наименьший. <...> В незамкнутой задаче коммивояжера, когда не требуется возвращаться к исходной вершине, находится гамильтонов путь. <...> Поволжский регион
Следует отметить, что гамильтонов контур не всегда является кратчайшим маршрутом. <...> Граф оптимального маршрута
Требуется найти оптимальный маршрут из пункта 1 через все узлы
графа и вернуться в исходную вершину 1. <...> Как следует из анализа вариантов
передвижения, он проходит через вершины 1–2–3–2–4–1, длиной 11 единиц
(рис. <...> Заданы контрольные вершины, через которые пройдут замкнутые маршруты. <...> Для разделения графа на маршруты вводим дополнительно фиктивные
узлы в исходную матрицу весов. <...> Фиктивным будем называть узел, дублирующий действительную вершину исходного графа. <...> Фиктивной дугой называется дополнительная хорда между вершинами, которой не было в исходном
графе. <...> Фиктивной ветвью называется дуга с фиктивным узлом. <...> Фиктивный узел делит оптимальный замкнутый маршрут
с симметричной <...>