А нельзя ли среднестатистическую скорость на ребрах менять в зависимости от некоего интегрального параметра по пробкам в городе.
Типа, как, прости господи, у Яндекса - пробки по шкале от 1 до 10,
соответственно, коэффициент от 0,1 до 1, на который домножаем вшитую
среднестатистическую скорость при расчете маршрута. Возможно (к сожалению, обосновать математически не могу), это помогло бы в пробочные часы пик, чтобы маршрут не строился по улицам, по которым не проехал ни один датчик. Думаю, такой метод расчета маршрута можно было бы сделать опциональным, ведь это не сильно усложнит алгорит