Which routing algorithm does Google Transit use?

[xayide]

Hello to everybody?

I'd like to know which routing algorithm does Google Transit use? is
it Dijkstra? or floyd-marshal? or a variety of one of them? or could
it be a propietary one?

thanks in advance!

[corsario]

There is an aplication in Recife - Brazil where you can find an
answer. But you have to know javascript.
The link is here http://www.onibusrecife.com.br/comochegar?saddr=Aeroporto&daddr=Centro+de+Convencoes.
Download all the Js files and take a look. I think they use GDirection
class with a data base of stops bus, routes and anything else.
You can participate of the group http://groups.google.com/group/Google-Maps-API?hl=en&lnk=
for more information and ...

good luck.

corsario.

[Tom Brown]

If you have questions about the transit trip planner in Google Maps
please use one of the groups dedicated to the feature, such as
http://groups.google.com/group/googletransit/

At a high level we build a graph where each departure is represented
by a node and time, distance, amount of walking distance, number of
transfers, etc are used to assign weights to edges. I believe
graphserver builds a similar graph and is open source so you can
inspect and improve on the implementation.

[Nitai Bezerra]

I'm part of the www.onibusrecife.com.br developer team. Our solution
are all server side, so you do not find any answer scratching
javascript files. All i can say is that we implemented our solution
with T-SQL within SQL Server 2008 runing softly over a dual core
processor with 1gb ram.

On Dec 30 2008, 5:14 pm, Tom Brown <tom.brown.c...@gmail.com> wrote:
> On Dec 24, 12:11 am, xayide <leire6...@gmail.com> wrote:
>
> > Hello to everybody?
>
> > I'd like to know which routing algorithm does Google Transit use? is
> > it Dijkstra? or floyd-marshal? or a variety of one of them? or could
> > it be a propietary one?
>
> If you have questions about the transit trip planner in Google Maps

> please use one of the groups dedicated to the feature, such ashttp://groups.google.com/group/googletransit/

[Brandon Martin-Anderson]

Graphserver uses a simple Dijkstra algorithm operating on a
representation of a transit system schedule incarnated as a graph as
detailed here: http://docs.google.com/Doc?id=dpr34df_18z77kphdx&hl=en.

Code to convert a gtfs-like data structure to such a graph structure is here:

http://github.com/bmander/graphserver/blob/4c733950e1c6beb3b3d4a0d43c7e5a7f07771d40/apps/package_graph/prepare_graphs.py

The core trip planning algorithm is here:

http://github.com/bmander/graphserver/blob/4c733950e1c6beb3b3d4a0d43c7e5a7f07771d40/core/router.c

Hope that helps. Happy hacking.

-B

[William Lachance]

2009/2/9 Brandon Martin-Anderson <bad...@gmail.com>:

>
> Graphserver uses a simple Dijkstra algorithm operating on a
> representation of a transit system schedule incarnated as a graph as
> detailed here: http://docs.google.com/Doc?id=dpr34df_18z77kphdx&hl=en.

My understanding of Djikstra's algorithm is that it implied visiting
every node on the graph:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Doesn't astar (http://en.wikipedia.org/wiki/A*_search_algorithm) make
more sense in the case of a transit network, where some vertices
should just plain never be visited? For example, if you're travelling
from Brooklyn to the Upper West Side, it probably doesn't make sense
to go into Queens.

libroutez uses astar (with a number of extensions to further reduce
the search space), with pretty good results.
--
William Lachance
wrl...@gmail.com

[JP]

On Feb 10, 4:39 am, William Lachance <wrl...@gmail.com> wrote:
> Doesn't astar (http://en.wikipedia.org/wiki/A*_search_algorithm) make
> more sense in the case of a transit network, where some vertices
> should just plain never be visited? For example, if you're travelling
> from Brooklyn to the Upper West Side, it probably doesn't make sense
> to go into Queens.

I was involved in trip planner development early on in my career. A
few experiences here:
If brute force is an option, do it. When results do not match
expectations and assuming the algorithm for finding solutions in the
problem space is correct, you know you need to work on the data. Brute
force isn't an option in many cases though (nature of the problem), so
things get tricky now.
Enter heuristics and you are confronted with an additional layer of
complexity. In particular if the heuristics are not supported by the
data model and reliable data behind it. My favorite metaphor here,
it's winter after all: It's like a blanket that's too short. Pull it
over the nose and the toes get cold. Cover the toes, and you get a
cold nose. You might have success to develop a blanket that somewhat
fits New York, but take it to another transit system, and you will
likely be out of luck.

Looking at the data models of scheduling systems, or better, the model
behind data exports (or GTFS for that matter), it looks pretty hard to
find aspects of the data models that could support effective
heuristics. Adding supporting data to complement the transit data is
hard. Try too much, and the effort to populate and maintain the data
model may be way too involved. You're also fighting the inner platform
effect. Try too little, and your effort may not be effective.

[Nitai Bezerra]

The solution is pretty beautiful, theoretically perfect. But the main
problem in my opinion is the time spent to run the algorithm over real
complex transit system as happens here in Recife, Brazil. Recife have
more tham 400 buslines, is a non-planned city. The solution is
suitable to real-time applications? Is this algorithm running in real-
time applications?

-N

On 9 fev, 23:29, Brandon Martin-Anderson <badh...@gmail.com> wrote:
> Graphserver uses a simple Dijkstra algorithm operating on a
> representation of a transit system schedule incarnated as a graph as
> detailed here:http://docs.google.com/Doc?id=dpr34df_18z77kphdx&hl=en.
>
> Code to convert a gtfs-like data structure to such a graph structure is here:
>

> http://github.com/bmander/graphserver/blob/4c733950e1c6beb3b3d4a0d43c...

>
> The core trip planning algorithm is here:
>

> http://github.com/bmander/graphserver/blob/4c733950e1c6beb3b3d4a0d43c...

>
> Hope that helps. Happy hacking.
>
> -B
>

> On Mon, Feb 9, 2009 at 2:20 PM, Nitai Bezerra <nitaibeze...@gmail.com> wrote:
>
> > I'm part of thewww.onibusrecife.com.brdeveloper team. Our solution