ЗАДАЧИ МАРШРУТИЗАЦИИ И РАСПРЕДЕЛЕНИЯ ЗАДАНИЙ
Аннотация
Цель работы: Дана маршрутно транспортная задача в которой нужно выполнить обход множества несколькими исполнителями, минимизируя максимум затрат исполнителей и оптимизируя маршрут каждого исполнителя. Решение задачи маршрутизации требуется произвести точным методом динамического программирования, а также эвристическим алгоритмом. После решения задач маршрутизации на всех подмножествах заданий, решить задачу об оптимизации разбиений методом динамического программирования.
В результате работы поставленные цели были выполнены. Была реализована программа на языке C++, решающая поставленную задачу. Были выполнены многочисленные вычислительные эксперименты, проведен анализ полученных результатов. Комбинированный алгоритм, включающий в себя эвристический метод на уровне задач маршрутизации и точный метод динамического программирования на уровне задачи об оптимизации разбиений, показал хороший результаты в условиях метрической задачи по точности и скорости вычислений. При условии отсутствия метрики в задаче результаты оказались далеки от истинных и данный подход не применим на практике
В результате работы поставленные цели были выполнены. Была реализована программа на языке C++, решающая поставленную задачу. Были выполнены многочисленные вычислительные эксперименты, проведен анализ полученных результатов. Комбинированный алгоритм, включающий в себя эвристический метод на уровне задач маршрутизации и точный метод динамического программирования на уровне задачи об оптимизации разбиений, показал хороший результаты в условиях метрической задачи по точности и скорости вычислений. При условии отсутствия метрики в задаче результаты оказались далеки от истинных и данный подход не применим на практике