[GraphHopper] Public Transport Support

[Peter K]

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"
<http://research.microsoft.com/apps/pubs/default.aspx?id=156567>

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 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/graphhopper/attachments/20130417/588292d2/attachment-0001.html>