[GraphHopper] Public Transport Support

[Peter K]

Hi Quinton and Thomas,

I'm sure there are improvements. Would be very nice to make graphhopper
aware of public transport as well.

BTW: OTP is LGPL not GPL.
BTW2: graphhopper is not a fork of OTP mainly because of the hibernate
and spring dependencies even in the routing package!

Regards,
Peter.

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