[GraphHopper] Public Transport Support

[Quinton Anderson]

Hi Guys,

Open trip planner has implemented the Raptor algorithm: https://github.com/openplans/OpenTripPlanner/tree/master/opentripplanner-routing/src/main/java/org/opentripplanner/routing/impl/raptor

I can't use Open trip planner because of GPL, and it is extremely bloated, but I did do some evaluation of the resulting routing in London, it didn't work particularly well. But I do get the point about the graph approach that the paper puts forward. 

So, I guess there is still room for improvement in it...

On 17 Apr 2013, at 6:08 PM, Peter K wrote:

> Hi Quinton,
> 
> thanks for pointing us to this paper (looks like uni-freiburg.de is down -> "Fast routing in very large public transportation networks using transfer patterns")
> Also the RAPTOR paper I mentioned earlier had some suggestions regarding efficient storage of routes etc in the appendix "Round-Based Public Transit Routing"
> 
> Regards,
> Peter.
> 
> 
>> Hi Guys,
>> 
>> On this topic, I assume you have seen the paper on Transfer Patterns. It does give some nice suggestions on the types of nodes and arcs to use for these purpose: http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf
>> 
>> Regards,
>> Quinton Anderson
>> 
>> On 17 Apr 2013, at 1:38 AM, Peter K wrote:
>> 
>>> 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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130418/c67cbad6/attachment-0001.html>