Routes to the Future
Two weeks ago, I took part in the Routes to the Future Innovation Challenge event, along with my friend Vic Smith. This was a hack event held by Transport for Greater Manchester as part of the FutureEverything conference. Their stated aim for the competition was
To build new, useful applications from TfGM’s data that will drive improvements to the way people travel in Greater Manchester.
I’m pleased to be able to say that we were the winner for the category “Best use of multiple datasets” for our iPad app ‘Locus’.
When Vic and I were planning to attend the competition, I asked Vic if he had any ideas of what we should make. He managed to immediately respond with what turned out to be a brilliant idea: an app that would make transport route maps for you. that looked like the London Tube Map, but personalised to the places you go and the bus routes you travel on. I loved the idea, and thought it sounded ideal in scope for a two-day project.
Before we left, we did a bit of research on how to go about automatically generating schematic maps. It turned out not to be so easy: I found two separate people who had each spent four years doing a Ph.D. in solving that exact problem! Luckily, they had published their results, which included some strategies for doing the calculations, and the specific algorithms they had used. Armed with a couple of academic papers and the source code for the GNU Linear Programming Kit (GLPK), we set off for Manchester.
Friday evening held an introductory session, where we were told the rules of the competition and shown the APIs that were being provided. Strangely, after that everyone dispersed, and congregated again at 8am on the Saturday in order to start coding. We had been under the impression that the competition would start on the Friday evening, so we had a bit of a wander round central Manchester to find a hotel for the night. In the hotel room, we attempted to compile the GLPK for iPad. Luckily (and somewhat surprisingly), it compiled relatively easily, which we took to be a sign!
Bright and early on Saturday, we grabbed the desk that would be our base of operations for the rest of the contest. Our plan of attack was simple: I was to work on the user interface, web service queries, and transforming the geographical data we got back from the web services into nodes and edges that we could feed into the mixed integer programming solver. Vic was to work on the maths itself: creating the constraints that we’d pass to GLPK, then applying its output back to our graph of nodes and edges. We decided to use the approach described by Martin Nöllenberg, so Vic’s main job of the weekend (after working with me to build a data model) was to translate Nöllenberg’s algorithms into constraints.
We grabbed a few huge pieces of paper to cover the desk around our laptops: we’d definitely want to be able to scribble down notes and diagrams in a hurry! Then we got to work. From my side of things, I first had to choose how we were going to be getting bus route data. The idea of the app was that the user would indicate a few places they regularly went, and the app would work out all the routes that link those places. I turned to the Jeppesen Journey Planner, an API I had used before and can provide public transport routing for the whole of Britain, and set to work.
If you’ve ever taken part in a hack day or coding competition, you’ll know there’s a long period between the point at which you commit to an approach, and the point at which you see everything come together for the first time. So it was with our project. I quickly had the interface for selecting bus stops up and running, and the bit that downloaded, parsed and converted the bus routes data into nodes and edges was underway, but the drawing code didn’t follow until a while later. That meant that I was trying to make sure all my algorithms (for things like merging nearby bus stops into single nodes to make interchanges) were working just by logging numbers in the debugger. Vic was having similar issues, testing out the linear programming code using sample data. It wasn’t until a point quite late on Saturday that we first brought everything together… and it worked! I could draw the route map before or after optimisation. Vic had written the first set of constraints: the ones that ensure octolinearity (i.e. the feature of transport maps where all the lines are on 45° angles). That day, we had some rudimentary graphics on screen, but they were at least showing actual route lines.
It wasn’t ready yet — in particular, there was nothing telling the app to try and get the route lines going in roughly the same geographical direction as real life, and nothing to stop it putting nodes in the same place as other nodes on the map. But this was the point where we first started to see the app come together. So, at 2am on the Saturday, we went to bed.
On Sunday, my main task was to add realtime data for busses. We had access to TfGM’s realtime positioning feed for the MetroShuttle buses, so I coded something that would download the positioning data, find the nearest edge on our graph, and display a pulsing dot on that edge. Vic was working on getting some more of Nöllenberg’s equations into our optimiser. Sadly, some of these proved too much for our lowly iPad. We’d been putting off running the app on an actual device, as things always run slower on the device than on the simulator, but we were quite pleased to find our first day’s work ran acceptably (taking 5-10 seconds to make a map with circa 3 bus routes). When Vic added the next set of constraints, suddenly GLPK was having to optimise things rather than just naively enforce some constraints. It started running incredibly slowly even on the Mac. After a ten minute run which still hadn’t completed, we gave up, and started to simplify our approach.
In Nöllenberg’s paper, he mentions various ways to compensate for speed of calculation. In particular, you take all the nodes that only have two connections entirely out of the map, and just leave in enough nodes to allow bends in the line. We could have gone down that route, but it was nearing the judging point. We made the decision to go back to the earlier (and faster) set of constraints, and used a couple of bus routes that still looked good with them. Luckily, some of the city centre MetroShuttle routes looked fine, and those were the ones with realtime data.
The last code I put in was to use CitySDK for locating the bus stops on the map where users choose their locations. Previously I’d been using Jeppesen’s API for bus stops as well as for routes, but we decided to switch in order to have a better shot at the “Multiple Datasets” prize category. We had had that in mind from the beginning, so the bus stops selector part of the app was quite easily refactorable to use the new data source.
After we’d had a discussion with two sets of judges, where we demonstrated our app, there was a bit of a break before the presentations. We got to see what everyone else had been up to, highlights of which included a PacMan game played by travelling on buses, a service which would leave a PDF of the latest bus timetable in your DropBox, and many other exciting apps. For our presentation, we gave a demonstration of our app in real time, with the iPad plugged in to the projector. After that there was another agonisingly long wait before the results were announced.
Having won one of the categories, as well as a prize we were offered a £3000 development fund in exchange for ten days of our time. This is to take the app from this initial proof-of-concept to a first prototype. While we can’t work on it until after Vic’s exams, we’re hoping we can develop it into something fit to release!