[GraphHopper] Public Transport Support

[Peter K]

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!

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