An Update on Fast Transit Routing with Transfer Patterns

http://googleresearch.blogspot.com/2016/03/an-update-on-fast-transit-routing-with.html

by runesoerensen • 10 years ago

84 20 10 years ago

googleresearch.blogspot.com

Pxtl2• 10 years ago

That's really cool. I've always been interested in pathfinding, but I'd naiveley assumed that the restricted world of mass transit would be simpler than free-form pathfinding.

Relatedly but somewhat off topic, I wonder why Google doesn't provide route maps too? While the transit route planning is neat, I often want a larger view of the route or system, and many municipalities just feed you a PDF from Hell.

ant6n3• 10 years ago

Google has the rapid transit lines in many cities, see for example London. In some of the Bay Area, they hint bus lines as well, but it's a bit of a mess (https://goo.gl/maps/rVPgGSBRD7G2). These maps are auto-generated it seems, so there are some issues - check out LA Union station (https://goo.gl/maps/GeW28w9MPpQ2).

Where the underlying transit data does not contain the exact shapes of routes, they interpolate the data with something that looks like Splines. You can see that in London, especially for the Docklands Light Railway (https://goo.gl/maps/uGmyBZZwDhy).

Apple maps makes much prettier transit maps, although I hear rumors they create them by hand.

LeifCarrotson• 10 years ago

Creating them by hand isn't necessarily a bad thing.

The post describes that there are on the order of 20,000 cities and towns covered; I expect that many of these are municipalities that are a part of a larger group of cities. WolframAlpha says that the 20,000th largest city coincidentally has a population of about 20,000 people, barely large enough to have its own public transit. And many states, companies, and countries will have common infrastructure for getting maps of all the public transit within the country. Taking a wild guess, there are probably significantly less than 500 separate transit systems to be mapped; a team of just 10 people could cover them in a year with a full person-week given to each location.

A mix of automation and manual entry is ideal for many tasks.

Pxtl2• 10 years ago

But if they get the stops right, does it matter if the line is a little vague? I mean, I just want to see all the routes, the lines don't matter. Big bulging stops with thin dottet splines connecting them would convey the important info even if it looks like the bus is flying.

eamsen2• 10 years ago

For anyone who's curious about an example implementation of transfer patterns: https://github.com/eamsen/transit-planner

Transfer patterns also behave robustly given real-time updates on the network, which we have shown here: http://stromboli.informatik.uni-freiburg.de/student-projects...

On top of being an excellent researcher, Hannah Bast is one of the best professors I've had pleasure of studying under and working with, so I'm happy to see her getting credit for this.

rabatata• 10 years ago

I'd love to play around with this. Do you have an estimate for the RAM and CPU requirements for the Toronto dataset? I skimmed the project site and didn't see this discussed.

eamsen2• 10 years ago

The robustness experiments are highly parallelized and maintain a copy of the (modified) network per thread. I vaguely remember the NYC test would take around a day on 16? cores and use up to 64GB of RAM.

You can find query time evaluation in the performance recap on the results page I linked. For NYC it's around 2.2s for the Dijkstra (baseline) and 27ms for the TP-based search.

For single-threaded pre-computation and shortest-path queries, I would expect you to need around 8GB for NYC, less for Toronto and you can get the Honolulu feeds to run on <2GB (which was my local test set).

Sorry for not being more specific or inaccurate.

You can find some GTFS feeds here: http://www.gtfs-data-exchange.com

evook• 10 years ago

Am I the only one who hoped for a google POV on BGP Transit when reading the title?

ape4• 10 years ago

I wonder if they consider how reliable the official schedule is. For example if a bus is supposed to come once an hour on the hour. It would be a bad plan to arrive just 1 minute before the top if the hour since the schedule is probably an approximation.

stormbrew2• 10 years ago

In my city the transit authority considers five minutes early to 1 minute late to be on-time. I don't know how normal this is, but it's actually pretty infuriating to have transit apps seem to treat it as the inverse.

A lot of issues like this tend to get glossed over in transit planning apps. Another issue is transfer timings, where the more transfers you do getting to your destination the more likely one of the transfers goes awry and throws off the whole schedule. For that reason I, as a person who exclusively uses transit in a city where it's not terribly good, almost always avoid a trip with 2 or more transfers if there's a 1 or less transfer option with more walking. Convincing transit apps to give you these kinds of options can be difficult (though google does have some knobs for controlling these things).

thrownaway2424• 10 years ago

What city is that? That is a rider-hostile definition of "on-time". In my city if the bus arrives at a stop early it will just stand there until the scheduled time.

aaronbrethorst• 10 years ago

Google has real-time data for public transit in lots of cities. http://maps.google.com/help/maps/mapcontent/transit/live-upd...

RivieraKid• 10 years ago

In the "Frequency-Based Search for Public Transit" paper they compare their algo's preprocessing time with RAPTOR - but RAPTOR doesn't require preprocessing AFAIK.

An Update on Fast Transit Routing with Transfer Patterns

Related Stories