Жадные и адаптивный алгоритмы решения задачи маршрутизации транспортных средств с несколькими центрами с чередованием объектов

В статье рассматривается задача маршрутизации транспортных средств с несколькими центрами с чередованием объектов. Предлагаются формальная постановка задачи с двумя типами объектов и математическая модель с двумя блоками булевых переменных. Вначале рассматривается модель без единого места сбора транспортных средств (мобильных объектов), а после вводится дополнительный специальный объект — место сбора. Показаны дополнительные ограничения, которые добавляются в математическую модель с учетом нового объекта. Отдельное внимание уделено условию отсутствия подциклов. Данное условие учитывается на основе матрицы смежности. Для предложенной задачи предлагаются жадные алгоритмы решения. Всего представлено пять алгоритмов, два из которых являются итеративными. На основе одного из рассмотренных жадных алгоритмов строится его вероятностная модификация на основе рандомизации переменных — адаптивный алгоритм. В завершение приводятся результаты вычислительного эксперимента по сравнению предложенных алгоритмов с точки зрения среднего значения целевой функции, а также времени работы. Также приводятся результаты эксперимента по настройке параметров адаптивного алгоритма.