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

19 Maps That Will Blow Your Mind and Change the Way You See the World. Top All-time. You Won’t Believe Your Eyes. Watch.

Many lists of maps promise to change the way you see the world, but this one actually does.

The Most Unisex Names in US History

Moving on from the most trendy names in US history, let’s look at the most unisex ones. Some names have …

Jobs Charted by State and Salary

Jobs and pay can vary a lot depending on where you live, based on 2013 data from the Bureau of Labor Statistics. Here’s an interactive to look.

Top Brewery Road Trip, Routed Algorithmically

There are a lot of great craft breweries in the United States, but there is only so much time. This is the computed best way to get to the top rated breweries and how to maximize the beer tasting experience. Every journey begins with a single sip.