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)

2

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

  • So I'd need to run N-1 queries for N points? Is that the only way? – Nicolas Rodriguez Dec 13 '13 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. – Nicolas Rodriguez Dec 13 '13 at 15:52
  • 1
    Wont be problem if you use dijkstra(or other routin) with oneway street support (if your data supports it) – simplexio Dec 13 '13 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. – Nicolas Rodriguez Dec 14 '13 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. – Uffe Kousgaard Dec 15 '13 at 8:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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