Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

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

share|improve this question
add comment

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
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 '12 at 15:36
add comment

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?

share|improve this answer
    
"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 Apr 13 '12 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? –  Aris Setyawan Apr 13 '12 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 '12 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 '12 at 6:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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