Looking Inside a Bus Routing Algorithm

Posted to Maps  |  Nathan Yau

In an effort to put transit data from the Toronto Transit Committee to better use, MyTTC provides a trip planner to help you find the best route from point A to point B. This video, compete with smart arses sitting on a couch, provides a peek into how the underlying algorithm works.

[Thanks, Canna]

13 Comments

  • Any video which includes the words “so we graph that ass pain in the third dimension” is automatically thereby a work of genius.

  • MATH! Love it! :)

  • Simon Hawkin March 9, 2010 at 5:56 pm

    Great animation.

    But what about the algorithm? What does it optimize, how does it work?

  • Yet another example of how technology regularly takes my breath away. Thanks for the share. MATH! UNMATH!

  • nice representation – but the algorithm seems to be a simple shortest path algorithm on a weighted (hyper-)graph (with weights=time used for a given distance and different transportation possibilities)

    • Simon Hawkin March 10, 2010 at 2:12 pm

      @Andy – They don’t really say what the algorithm is, so we can only guess (a weighted shortest path is indeed a likely guess).

      But the animation is good, and a good point of reference for further references (as a teaching tool).

  • Hey all – thanks for the kind words :-)

    Our algorithm (which we call k*) differs from shortest path algorithms like Dijkstra & A* in a few key ways:

    Traditional shortest path algorithms are designed to traverse static graphs (driving directions and the like), and typically optimize for time.

    k* was designed to operate on a multi-modal, directional, dynamic graph, and it doesn’t simply weight by time. Instead, it makes path decisions based on a composite function (our pain-in-the-ass factor) which includes time, cost, walking distance, number of transfers, stairs, elevators, escalators, and (soon) weather data; basically anything that would contribute to the overall user experience. Our accessibility options (in testing) are based on use cases which each adjust the overall PITA at each step in an appropriate manner.

    k* also tries to return the best *distinct* trips, so you don’t just get the same one with slight variations.

    We do plan to write up a more detailed explanation of k* eventually, but that’s likely a ways off.

    Cheers,
    Kieran

  • Had to watch a couple of times to get what was really going on (reading the post later helped I have to admit)…

    Maybe it’s just me, but the background music was really annoying.

    With that said, I really enjoyed the video and the smart asses on a couch explanation

    • I wish they’d made the effort to record a narration. Sometimes I ‘watch’ online videos while I’m doing other work, which means that I’m really listening to them.

  • I’ve yet to see a transit planner that’s really useful, although, adding ability to reason about waking routes, as done here, is a good addition.

    I spoke with the PR guy from my local bus organization about the atrocious trip planner that they have and he told me that, even if it wasn’t useful for passengers, it was very useful for the bus organization. After all, the trip planner tells them where we want to go and when, even if the bus can’t get us there!

    That’s a major reason why search has eclipsed browsing as a navigation paradigm: search is is a form of surveillance! Even if a search engine fails the user entirely, it always accumulates information of value for its operator.

Favorites

Most popular porn searches, by state

We’ve seen that we can learn from what people search for, through the eyes of Google suggestions: state stereotypes, national …

Famous Movie Quotes as Charts

In celebration of their 100-year anniversary, the American Film Institute selected the 100 most memorable quotes from American cinema, and …

Graphical perception – learn the fundamentals first

Before you dive into the advanced stuff – like just about everything in your life – you have to learn the fundamentals before you know when you can break the rules.

Reviving the Statistical Atlas of the United States with New Data

Due to budget cuts, there is no plan for an updated atlas. So I recreated the original 1870 Atlas using today’s publicly available data.