Решение задачи о назначениях и формирование маршрута (VRP)

[enegul]

Добрый день! Подскажите, пожалуйста, с помощью какой системы можно решить следующую задачу, то что на западе называют Vehicle Routing and Scheduling Problem (смесь задачи коммивояжера и задачи о назначениях): есть пул ремонтников, которые выполняют ремонт объектов в разных частях города. Привязки ремонтника к территориям/активам НЕТ. Необходимо автоматически определить набор объектов ремонта для каждого сотрудника и сформировать оптимальный маршрут, с учетом того, что называется Street-Level-Routing (т.е. с учетом пробок, улиц с односторонним движением, лесов, полей и рек). На вход даны перечень ремонтников и перечень активов с координатами. Можно дать на вход матрицу расстояний или времен между ними (если это нужно).
Каким образом ГИС может здесь помочь?
Необходимо ли обязательно использовать эвристические алгоритмы вместе с ПО по картографии?
Заранее спасибо.

[dart]

В ArcGIS'е Network Analyst решает эту задачу. Естественно, нужно иметь для него входные данные: граф дорог, с закодированными ограничениями и т.д.

[andreichernov]

Алгоритм решения - в два с половиной этапа
1) Составляется матрица расстояний между точками ремонта на основе алгоритма поиска кратчайшего пути по графу дорог с помощью ГИС (в тех ГИС, где это реализовано)
2) Решается задача коммивояжера уже без ГИС
3) Результаты решения отображаются на ГИС в виде маршрутов.