1

I'm new in pgrouting. Is it possible to get 10 (some) ordered shortest paths ordered by distance (cost) with PgRouting (ex: SELECT TOP 10 SHORTEST)?

Update: why "second shortest" needed?

"second shortest" or "10 shortest path", this is the because the shortest path is not the best, for example if all people go to work with the shortest path, it will become a traffic jam, so "the shorted path is not the best". This is can be applied too with "10 cheapest path". Is this impossible?

-aris setyawan

2 Answers 2

5

The algorithm you're looking for is called "k-shortest path" and it returns alternative routes that take a significantly different way.

It has been discussed on pgRouting mailing list and there is a ticket with links to algorithms: https://github.com/pgRouting/pgrouting/issues/11

But it hasn't been implemented yet in pgRouting. I thought someone was working on it, but I don't remember who and can't find the post in the mailing list.

2
  • 1
    An excellent criticism of k-shortest paths is found at section 4.1 of Alternative Graphs in Road Networks (Bader et al.): "The computed routes are usually so similar to each other that they are not considered as distinct alternatives by humans." This paper surveys several methods, tests them, and concludes that two seem to work best for road networks. Some form of a penalty method looks most promising: after finding an optimal route, upweight its edges and all edges attached to it, then try again from the start.
    – whuber
    Apr 13, 2012 at 15:36
  • This is have been implemented in pg_routing.
    – Iwanio
    Mar 1, 2015 at 9:51
1

Short answer: No.

What would a "second shortest" path look like? It would probably differ in a few short links and otherwise look exactly like the shortest path.

Please describe in more detail what kind of result you are looking for. e.g. two paths should not share more than 50 % of their links (calculated by length).

Update:

Judging from your comment, you want to do Route assignment?

Route assignment allocates trips between an origin and destination by a particular mode to a route. [...] The difficulty is that travel times are a function of demand, while demand is a function of travel time, ...

There is specialized software to solve such problems. Do you want to create your own solution from scratch?

4
  • "second shortest" or "10 shortest path", this is the because the shortest path is not the best, for example if all people go to work with the shortest path, it will become a traffic jam, so "the shorted path is not the best". This is can be applied too with "10 cheapest path". Is this impossible?
    – Iwanio
    Apr 13, 2012 at 6:50
  • about "Route assignment", (if I'm not misunderstanding about it) I think my usecase is not that complex or large. I just want to make something like transportation routing searching search engine (just like google), where peoples can use it to search some possible alternative to from one city to another city with many combination of transportation facility (bus, train, rent a car, ship, boat, or a plane). In here (my country), using airplane still very expensive for most people, so if there is exist cheaper elternative, it will be welcomed. Is there another alternative solution?
    – Iwanio
    Apr 13, 2012 at 7:30
  • @Aris: One quick and dirty method starts by finding key nodes or edges through which a lot of traffic passes or perhaps should pass in order to avoid congested areas. Force the alternative routes to pass through one or more given key points. E.g., if the best route passes west of an intermediate obstacle, find a key point east of that obstacle and require the alternative to pass through it. The alternative will differ substantially from the best route in exactly the sense you are looking for: it takes traffic far from the best route but otherwise is as short as possible.
    – whuber
    Apr 13, 2012 at 15:41
  • Aris, another simple way for your case would be, if you need route alternatives, just use different costs. For example make highways a bit faster and regular roads slower. If you have different cost profiles you should get different routes.
    – dkastl
    Apr 14, 2012 at 6:11

Your Answer

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

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