0

I want to calculate the route between multiple points, respecting the order of the list.

For example, if I have the following list:

  1. Lat: -40, Long: -30
  2. Lat: -41, Long: -31
  3. Lat: -40.5, Long: -30.5

I want the route to go from point 1 to 2, and then from point 2 to 3.

  • I don't want to calculate the best path from 1 to 2 and 3 (Travelling Sales Person) because that would give me a path 1-3-2, as the 1st point is closer to the 3rd point than the 2nd one.
  • I don't want to calculate the best path from 1 to 2, and from 1 to 3 (Mutliple destination Shortest Path Dijkstra), because that would give me a path from 1 to 2 and from 1 to 3.

I want it to calculate the best path from 1 to 2, and then from 2 to 3. All with just 1 query, using pgrouting.

It would be something like a TSRP but preserving the order of the points. Google already does that (https://developers.google.com/maps/documentation/javascript/directions#Waypoints) and if you want, they can optimize the order of the waypoints (using TSRP)

1 Answer 1

2

You just need to execute desired shortest path algorithm twice, first from 1 to 2 and second from 2 to 3.

8
  • So I'd need to run N-1 queries for N points? Is that the only way? Dec 13, 2013 at 14:35
  • Also, I'd have another problem with that approach: for example, if points 2 and 3 are in the same highway, it would arrive to point 2 and then go directly to point 3, in the opposite direction as it was going. Dec 13, 2013 at 15:52
  • 1
    Wont be problem if you use dijkstra(or other routin) with oneway street support (if your data supports it) Dec 13, 2013 at 16:36
  • and that way, how will dijkstra know that I was going in one direction, and not the other? I mean, in a two-way street... The next query will give me a result in the opposite direction. Dec 14, 2013 at 23:34
  • With N points, the vehicle can face in 2 directions for each point. Meaning you have 2^N combinations to test for the best direction at each point. Because changing direction for one point, affects the next ones. But if some of them are oneway, there is no choice and the number of combinations is reduced a lot, since only sequences of twoway streets need to be tested individually. I'm not sure if pgrouting can handle it, but our RW Net 4 product can. Dec 15, 2013 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.