[GraphHopper] Public Transport Support

[Peter K]

Hi Thomas,

regarding the size of the graph I don't expect problems, as the world
wide OSM graph currently has over 83mio nodes.

The problem is the algorithm and if it scales. E.g. if I would use a
normal bidirectional dijkstra for a 10 000km query it would take over 10
seconds but with a short cutting or hierarchical algorithm like
contraction hierarchies it is under 100ms! So I'm really excited to hear
what you choose for an algorithm :) !

Regards,
Peter.

> Thank you for your response and offering your help.
>
> I have looked little bit into the thematic and it seems that a
> implementation with a time-expended graph would be very straight
> forward. So, I would have to implement a GTFSReader which creates the 
> public transport graph.
> Would this approach perform well with ~1 million nodes (time stops)?
>
> Regards,
> Thomas
>
>
>
> On 04/08/2013 09:09 PM, Peter K wrote:
>> Hi Thomas,
>>
>> public transport would be nice to have, yes :)
>>
>> But there is no time dependent datastructure yet, and the algorithms
>> are not tuned regarding public transport. So, it is not easy to
>> implement. If you do not have much data you can just use the
>> GraphStorage (and model the time via nodes), then use a-star or
>> dijkstra to get routes. One minor gimmick would be the 'wayGeometry'
>> (in EdgeIterator) which you could use to display the real paths
>> between two nodes of the trains/buses/... instead of straight line
>> like e.g. google does.
>>
>> To properly implement public transport one would probably need to
>> create a new Graph interface and iterate from that, e.g. create a
>> simple algorithm and then use more advanced like RAPTOR. Also a new
>> GTFSReader will be necessary instead of or combined with OSMReader.
>>
>> If you're trying something you can be sure to have my assistance :) !
>>
>> Regards,
>> Peter.
>>
>> ------------------------------------------------------------
>>
>> Hello,
>>
>> I'm considering to use graphhopper for a student project. But for that I
>> also need support for public transport. So I'm thinking about
>> implementing it my own...
>> Do you have any thoughts or plans how to implement it and would it be a
>> lot of work?
>>
>> Regards,
>> Thomas
>>
>>
>> _______________________________________________
>> GraphHopper mailing list
>> GraphHopper at openstreetmap.org
>> http://lists.openstreetmap.org/listinfo/graphhopper
>
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/graphhopper


-- 
GraphHopper.com Your way is our destination!

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130416/32c2bb8e/attachment.html>