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