others (#15) - speed up routing - how? (#326) - Message List

speed up routing - how?

Hey folks,

I know that there are already some threads about this topic. But I think some of us have already figured out the intrinsic problem, so we can start from a higher level. We should agree, that in order to speed up routing prereduction of data is necessary. This may be implemented by using bboxes at the start and end points and for the rest regarding only higher level streets. But, as some of us already figured out, this is not always the best solution. I mean the missing density of main-street topology in some areas. Also if your shortest path is shaped like a 'C' you'll get poor and mostly no results. My idea, and I've already read the same thought in one older thread here, was to raise important minor streets to a higher priority. So what do you think? Does anyone has some clever PostGIS-Code that can do that? e.g. Creating a main grid and then precalculate some major paths?

  • Message #1364

    Hi there,

    What I can tell you definitely is that I personally don't have any code that does such thing.

    I also think that data reduction is not that simple task and it requires sophisticated techniques to improve the quality.

    Last year I studied different layering techniques and in my opinion it would be great to have something like Highway Hierarchies algorithm which assigns roads to layers by their 'importance', not by just road attributes. Unfortunately HH* algorithm, which does it somehow, doesn't have any open source implementation, and currently we have no resources to implement it from scratch.

    • Message #1367

      In the meantime I came to another workaround. I've implemented a kind of self learning mechanism. Starting from optimistic mode with small bboxes and only major streets between source and target. If that fails, I extend the bboxes at start and end and mix in streets with lower priority and give the routing a second chance. If the route is found, I raise the priority of streets, that let the first attempt fail.