Hi,
I wonder whether it is possible to apply Graphhopper/jspirit to the problem of finding the “most reasonable” route for a number of uncertain locations, and how you would approach this.
What we have as input is a set of location candidates for a number of different time stamps t_0 … t_n. I.e. for each t_i we have say 10 location candidates, each assigned with a probability. These candidates are not exact locations, they are uncertain - with a radius of say roughly 100 meters. The higher the candidates probability, the less its uncertainty. The candidates for each time stamp t_i can even be further apart from each other, say up to 500 meters.
Up to now we find the best route using the Viterbi algorithm, selecting the candidate for each t_i such that the route through these locations minimizes the average speed overall and also takes the candidates probability into account.
We would like to improve this by taking map data into account. So if it is obvious from the time stamps and the rough distances between them that this route has been done by car, the selected locations should be along roads (note that the candidates are most likely not on roads, so they’d need to snap to roads). As a bonus, if it is obvious from times and distances that the travel was very fast, hence must have been along the motorway, then we’d like to have the locations on the motorway, and not on roads nearby.
How could we approach this, as routing normally requires exact locations? Ok, if I click randomly on the map, then the starting/end point of the route is placed on the nearest road nearby. But in case of the motorway scenario, we’d need not the nearest road, but the road that fits best to the speed/time constraint imposed by the time_stamps we have.
We could utilize the Matrix API, calculating all the distances between location candidate pairs of time stamps t_i and t_(i+1). So we’d still be using Viterbi, but instead of the direct distances we’d have the “real” road distances. But this doesn’t solve the motorway scenario, since if there is no location candidate that gets snapped to the motorway, we won’t find it.
Any ideas?
Many thanks!