№ 1(36) 2012 (январь–март) Безопасность движения и автомобильные перевозки УДК 656.135.073 С. А. ЖЕСТКОВА ИСПОЛЬЗОВАНИЕ МЕТОДА «ВЕТВЕЙ И ГРАНИЦ» ПРИ РЕШЕНИИ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТА В статье рассматривается решение задачи маршрутизации транспорта «методом ветвей и границ». <...> Предложен усовершенствованный алгоритм, позволяющий получить точное решение задачи. <...> ВВЕДЕНИЕ Для снижения стоимости транспортировки грузов требуется разработка эффективных алгоритмов для определения кратчайших маршрутов передвижения транспорта. <...> Общая математическая формулировка этой задачи известна как задача маршрутизации транспорта. <...> В настоящее время для решения задач маршрутизации транспорта используются метаэврестические методы, которые содержат дискретные и непрерывные параметры регулирующие их работу. <...> Они требуют выполнения операций по перебору вариантов их значений для нахождения окончательной эвристики. <...> Подбор параметров необходимо выполнять каждый раз для нового типа задач. <...> Кроме того метаэвристические алгоритмы, например генетический и муравьиных колоний, образуют массив данных значительного размера и содержат большое количество управляющих параметров. <...> По этому несмотря на привлекательность этих методов достоверность вычислений по ним приходится проверять используя более точные методы решения подобных задач. <...> ДОКАЗАТЕЛЬСТВО НЕТОЧНОСТИ МЕТОДА «ВЕТВЕЙ И ГРАНИЦ» ПРИ РЕШЕНИИ ЗАДАЧ МАРШРУТИЗАЦИИ ТРАНСПОРТА 2 4 2 1 1 3 5 3 5 5 3 Рисунок 1 – Граф транспортной сети Рассмотрим возможность решения задачи маршрутизации транспорта методом «ветвей и границ» при исходных данных, представленных на графе транспортной сети (рис. <...> В результате получаем приведенную матрицу с минимальной границей множества 17 (табл. <...> Здесь две ячейки имеют одинаковую оценку 2: 7-5 и 5-7. <...> Рассмотрим в ней вычеркивание ветви 5-7, имеющею наивысшею оценку 2. <...> 6 наибольшую оценку бесконечности имеют две ячейки 4-6 и 6-5. <...> При вычеркивании ветви <...>