Главная » Справочник » Основы организации и управления транспортными системами » Постановка задачи коммивояжера и идея метода ветвей и границ

Постановка задачи коммивояжера и идея метода ветвей и границ

Имеется несколько городов, населенных пунктов (вершин транспортной сети), которые коммивояжеру∗ надо обойти по кратчайшему маршруту, причем зайти в каждый город надо не более одного раза. Коммивояжеру известны пути, соединяющие населенные пункты и их длина, то есть, задана транспортная сеть и известны оценки ее дуг.

Интересно

При большой размерности задачи – при большом количестве вершин и дуг транспортной сети найти кратчайший маршрут обхода за приемлемое время с использованием современных математических методов и вычислительной техники не представляется возможным, то есть задача коммивояжера большой размерности не имеет решения. Тем не менее, для решения задачи коммивояжера на транспортной сети, состоящей из нескольких десятков вершин, успешно применяются комбинаторные методы оптимизации, в частности, метод «ветвей и границ».

Метод «ветвей и границ» является комбинаторным методом оптимизации, основанным на идее перебора возможных вариантов решения различных оптимизационных задач. Метод «ветвей и границ» применяется в тех случаях, когда множество вариантов решения задачи образует своеобразное дерево вариантов. Например, в задаче коммивояжера включение одной дуги в маршрут обхода вместо другой приводит к формированию нового множества вариантов или новой ветви вариантов.

Множество таких ветвей образуют дерево решений. Кроме того, для применения метода «ветвей и границ» необходимо, чтобы имелась возможность расчета критерия оптимальности на каждом шаге построения дерева решений. Например, в задаче коммивояжера каждый вариант маршрута обхода характеризуется оценкой или длиной.

В процессе использования метода «ветвей и границ» находится первый произвольный вариант решения задачи. Определяется значение критерия оптимальности для найденного варианта, которое называется нижней границей дерева решений. В процессе последовательного формирования других вариантов решения задачи, то есть в процессе ветвления дерева решений, рассчитывается текущая граница – текущая оценка нового варианта решения.

Рассмотрение нового варианта прекращается как только текущая оценка не будет больше или равна нижней границе дерева решений. В этом случае «ветвь обрезается» и все последующие варианты (ветви), исходящие из данной ветви не рассматриваются. За счет этого достигается сокращение общего количества перебираемых вариантов и ускорение процесса поиска оптимального решение

Очевидно, что чем ближе оценка начального варианта к оптимальной, тем меньше вариантов приходится перебирать в процессе решения задачи методом «ветвей и границ». Если окажется, что новый окончательный вариант имеет меньшую оценку, то это значение считается новой нижней границей дерева решений и используется для определения момента прекращения расчетов по новым вариантам решения задачи.

Предыдущая статья Понятие транспортной системы Следующая статья Постановка задачи определения оптимального варианта плана формирования поездов

Статьи по теме