<html><head></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Hi Guys,<div><br></div><div>Open trip planner has implemented the Raptor algorithm: <a href="https://github.com/openplans/OpenTripPlanner/tree/master/opentripplanner-routing/src/main/java/org/opentripplanner/routing/impl/raptor">https://github.com/openplans/OpenTripPlanner/tree/master/opentripplanner-routing/src/main/java/org/opentripplanner/routing/impl/raptor</a></div><div><br></div><div>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. </div><div><br></div><div>So, I guess there is still room for improvement in it...</div><div><br><div><div>On 17 Apr 2013, at 6:08 PM, Peter K wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite">
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
<div bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Quinton,<br>
<br>
thanks for pointing us to this paper (looks like <a href="http://uni-freiburg.de">uni-freiburg.de</a>
is down -> "Fast routing in very large public transportation
networks using transfer patterns")<br>
<div align="left">Also the RAPTOR paper I mentioned earlier had
some suggestions regarding efficient storage of routes etc in
the appendix <a href="http://research.microsoft.com/apps/pubs/default.aspx?id=156567">"Round-Based
Public Transit Routing"</a><br>
</div>
<br>
Regards,<br>
Peter.<br>
<br>
<br>
</div>
<blockquote cite="mid:485EA734-503B-453A-8767-7F319762286B@gmail.com" type="cite">Hi Guys,
<div><br>
</div>
<div>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: <a moz-do-not-send="true" href="http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf">http://ad.informatik.uni-freiburg.de/files/transferpatterns.pdf</a></div>
<div><br>
</div>
<div>Regards,</div>
<div>Quinton Anderson</div>
<div><br>
<div>
<div>On 17 Apr 2013, at 1:38 AM, Peter K wrote:</div>
<br class="Apple-interchange-newline">
<blockquote type="cite">
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
<div bgcolor="#FFFFFF" text="#000000">
<div class="moz-cite-prefix">Hi Thomas,<br>
<br>
regarding the size of the graph I don't expect problems,
as the world wide OSM graph currently has over 83mio
nodes.<br>
<br>
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 :) !<br>
<br>
Regards,<br>
Peter.<br>
<br>
</div>
<blockquote cite="mid:516D5004.9020304@student.ethz.ch" type="cite">
<meta content="text/html; charset=ISO-8859-1" http-equiv="Content-Type">
<div class="moz-cite-prefix">Thank you for your response
and offering your help.<br>
<br>
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.<br>
Would this approach perform well with ~1 million nodes
(time stops)?<br>
<br>
Regards,<br>
Thomas<br>
<br>
<br>
<br>
On 04/08/2013 09:09 PM, Peter K wrote:<br>
</div>
<blockquote cite="mid:51631606.7070708@yahoo.de" type="cite">
<meta http-equiv="Content-Type" content="text/html;
charset=ISO-8859-1">
Hi Thomas,<br>
<br>
public transport would be nice to have, yes :) <br>
<br>
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. <br>
<br>
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. <br>
<br>
If you're trying something you can be sure to have my
assistance :) ! <br>
<br>
Regards, <br>
Peter.<br>
<br>
------------------------------------------------------------<br>
<br>
Hello, <br>
<br>
I'm considering to use graphhopper for a student
project. But for that I <br>
also need support for public transport. So I'm
thinking about <br>
implementing it my own... <br>
Do you have any thoughts or plans how to implement it
and would it be a <br>
lot of work? <br>
<br>
Regards, <br>
Thomas </blockquote>
</blockquote>
</div>
</blockquote>
</div>
</div>
</blockquote>
</div>
_______________________________________________<br>GraphHopper mailing list<br><a href="mailto:GraphHopper@openstreetmap.org">GraphHopper@openstreetmap.org</a><br>http://lists.openstreetmap.org/listinfo/graphhopper<br></blockquote></div><br></div></body></html>