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]
Any video which includes the words “so we graph that ass pain in the third dimension” is automatically thereby a work of genius.
Pingback: The New Generation Copywriting Tool To Improve Conversions.
MATH! Love it! :)
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)
@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
Pingback: links for 2010-03-11 « lugar do conhecimento
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.
Pingback: Looking Inside a Bus Routing Algorithm « O(blah)