pgRouting - Route between multiple destinations - in order

Question

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

For example, if I have the following list:

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)

simpleuser001 · Accepted Answer · 2013-12-13 14:11:11Z

2

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

answered Dec 13, 2013 at 14:11

simpleuser001

3,84417 silver badges20 bronze badges

So I'd need to run N-1 queries for N points? Is that the only way?
– Nicolas Rodriguez
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.
– Nicolas Rodriguez
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)
– simpleuser001
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.
– Nicolas Rodriguez
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.
– Uffe Kousgaard
Dec 15, 2013 at 8:44

| Show 3 more comments

1 Answer 1