[GraphHopper] Public Transport Support

[Thomas Bürli]

Thank you for the papers. I will have a look at them.

> 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 :) !

This shouldn’t be too much a problem to me because I'm more interested 
in finding the single source shortest path than in finding a path. 
Therefore, I will go with Dijkstra for the start.

Regards,
Thomas


On 04/17/2013 10:47 AM, Peter K wrote:
> Hi Quinton,
>
> looks like mailman didn't let it through ... but google + the "cache 
> link" helped me already ;)
>
> Also: are you finally receiving mails from this list or are you 
> reading it via nabble or similar?
>
> Regards,
> Peter.
>
>> Are you happy I attach it to a mail response here? It is focused on 
>> the public transport problem.
>>
>> Sent from my iPhone
>>
>> On 17/04/2013, at 18:08, Peter K <peathal at yahoo.de 
>> <mailto:peathal at yahoo.de>> wrote:
>>
>>> Hi Quinton,
>>>
>>> thanks for pointing us to this paper (looks like uni-freiburg.de 
>>> <http://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 
>>> _______________________________________________
>>> GraphHopper mailing list
>>> GraphHopper at openstreetmap.org <mailto: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!
>
>
> _______________________________________________
> GraphHopper mailing list
> GraphHopper at openstreetmap.org
> http://lists.openstreetmap.org/listinfo/graphhopper