Дано:
- набор GPS координат (GPS трек)
- дорожный граф

Требуется построить маршрут по дорогам графа максимально приближенный к GPS треку.

Кто нибудь сталкивался с подобной задачей?

Пока думаю оценить близость всех ребер графа к GPS треку и построить маршрут по дорогам исходя из этой оценки. Подозреваю, что данное решение не оптимально. Может быть есть какие нибудь другие решения?

Я когда-то решал похожую задачку: дана огромная куча GPS-точек (от разных поездок), и надо по ним построить граф дорог (предполагая, что большинство людей ездят по дорогам  ).

Но ваша задача, по-видимому, гораздо проще. Если у вас GPS-точки хорошо согласуются с дорожной картой, то я бы решал таким образом: для каждой GPS-точки нашёл ближайшее к ней ребро графа, и увеличил бы у этого ребра счётчик на один. В результате для всех дорог, которые проходят вдоль искомого маршрута, эти счётчики получатся большими - так что дальше останется просто выкинуть рёбра с маленькими числами. Либо не выкидывать никакие рёбра, а найти путь от стартовой точки до конечной с максимально возможным минимумом значения счётчика.

2 maxdiver:

Что то подобное и я хочу сделать, но здесь есть проблема - в маршруте могут быть циклы.

Что такое трек? Последовательный набор точек, каждая последующая в котором, снята ПОСЛЕ предыдущих?

Какие проблемы? Не удается выяснить ближайшую дорогу? Если дорог несколько - нужно выбирать все, попадающие в диапазон погрешности GPS и идя по треку, выкидывать те, которые уже не подходят...

Да, еще есть время каждой точки.


Вообще у меня у самого в голове масса вариантов, но все они, при ближайшем рассмотрении, не работают или работают плохо в той или иной ситуации.
На самом деле задача не так проста, как кажется на первый взгляд. И придумать алгоритм, который работает во всех ситуациях не просто.

Пока у меня вариант решения у меня примерно такой же, как и предложил maxdiver: оценить все ребра дорог по критерию близости к треку и затем построить путь исходя из этого критерия.
Вот только с циклами проблемы: в пути могут быть циклы.  Но, думаю, что проблему с циклами можно решить используя дополнительный параметр - время каждой координаты GPS.

Вообще очень хотелось бы получить советы людей, которые сталкивались с подобной задачей сами или понимают как ее можно решить. Хотелось бы больше конкретики.

Ну всё же я ещё раз выскажу своё видение алгоритма.

Для каждой GPS-точки мы находим ближайшую к ней дорогу. Тем самым, если мы выпишем GPS-точки в порядке возрастания времени, то мы получим последовательность дорог в порядке их обхода.

Понятно, что главная трудность - в том, что так мы найдём некоторые лишние дороги, потому что когда человек проезжал перекрёсток, ближайшей на какое-то время могла стать другая дорога, чем та, по которой он на самом деле поедет дальше.


Решение мне видится такое: давайте научимся понимать для каждой дороги, действительно ли человек проехал её, или эта дорога - случайная "помеха". В качестве критерия можно взять такой: дорога является "помехой", если есть GPS-точка, близкая к одному её концу, но нет GPS-точки, близкой к другому её концу.

Формально это выглядит так. Пусть мы сейчас рассматриваем i-ую GPS-точку P[i], а ближайшая к ней дорога - это дорога (A,B) (где A - ближайший к точке P[i] конец дороги). Найдём, сколько ещё точек, следующих непосредственно после P[i], тоже находятся ближе всего к дороге (A,B) - пусть это количество равно k. Тогда эти k точек P[i+1]..P[i+k] должны монотонно приближаться к точке B, причём последняя из них - P[i+k] - должна находиться от B на расстоянии не более, скажем, distance(A,B) / 2. Если всё это выполнено, то дорога (A,B) - "хорошая", добавляем её в ответ, и переходим сразу к точке P[i+k+1]. Если не выполнено, то пропускаем эту дорогу, и тоже переходим к точке P[i+k+1].



P.S. Тут ещё многое зависит от того, с какой частотой снимались эти GPS-точки: не получится ли так, что какую-то дорогу в пути человек может "пролететь" одной-двумя GPS-точками. В этом случае алгоритм, конечно, усложняется.

2 maxdiver:
Спасибо, полезный для размышления совет.


Здесь проблем нет, частоту получения точек сами задаем, сейчас - одна точка в секунду. И идем мы пешком.