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

В работе приведен теоретический обзор различных алгоритмов для решения задач составления маршрутов для транспортных средств с учетом ограничений (TSP и VRP), а также проведены практические эксперименты для сравнения эффективности описанных алгоритмов и двух подходов к составлению маршрутов - на основе предварительной кластеризации объектов с последующей классической задачей коммивояжера (TSP) для каждого агента и задачей VRP, которая распределяет объекты и определяет очередность посещения в рамках одной модели. Сравнение проводилось на основании алгоритмов, реализованных в открытом программном пакете or-tools на основе данных по 112 объектам и 4 агентам с индивидуальными ограничениями на длительность маршрутов и типы посещаемых объектов. В результате применительно к используемому набору данных концепция VRP оказалась незначительно эффективнее в терминах суммарной длительности маршрутов, чем индивидуальные TSP, а жадные алгоритмы показали результат не хуже, чем более сложные эвристики.