ДИХОТОМИЧЕСКАЯ МАРШРУТИЗАЦИЯ ТРАНСПОРТНОГО ГРАФА 

Подшивалова Кристина Сергеевна, кандидат технических наук, доцент, кафедра организации и безопасности движения, Пензенский государственный университет архитектуры и строительства, E-mail: sharm-08@bk.ru
Подшивалов Сергей Федорович, кандидат технических наук, доцент, кафедра общепрофессиональных дисциплин,
филиал Военной академии материально-технического обеспечения имени генерала армии А. В. Хрулёва (г. Пенза), 
E-mail burobaola@mail.ru 

656.135.073 

Актуальность и цели. Рассматривается вопрос дихотомической маршрутизации в комбинированной системе доставки груза по кольцевым схемам с одной базы. Расчет таких сложных систем развозки или сбора груза производится приближенными эвристическими методами, когда выполняется декомпозиция транспортной сети и ее деление на кластеры. В основе лежит многоэтапная модель расчета, состоящая из определения набора кластеров и решения задачи маршрутизации в них. Существуют различные методики расчета этапов, однако общим их недостатком
является ограничение поиска в глубину по всей транспортной сети на основе выбранного критерия оптимальности целевой функции. Задачей исследования является разработка методики одновременного решения задач кластеризации и маршрутизации.
Материалы и методы. Поставленная цель достигается при использовании методики фиктивных узлов и ветвей с двумя контрольными узлами, а также создании единого кольцевого маршрута без пересечений, проходящего через все базы и пункты разгрузки. Выполнение ограничений по количеству вершин достигается блокировкой ветвей на дереве решений, приводящей к их невыполнению. Выбор оптимального маршрута производится из анализа всех вариантов сочетаний расположения контрольных вершин. После проведения первого этапа операция дихотомического деления повторяется.
Результаты. Проверка достоверности разработанного метода осуществлялась на численном примере транспортного графа из девяти вершин. Определены два маршрута по четыре пункта разгрузки груза. После их деления получены четыре схемы движения, содержащие по две вершины. Результаты сравнивались с данными расчетов по методу Кларка–Райта.
Выводы. Установлено, что предложенный метод дихотомической маршрутизации позволяет получить оптимальную схему движения. 

Ключевые слова

транспортный граф, маршрутизация, алгоритм, метод фиктивных узлов и ветвей, контрольные вершины, кольцевые схемы движения 

 Скачать статью в формате PDF