BusyRoute

BusyRoute was the third-year Software Engineering Group Project I did at Imperial. It is a web application that helps users develop itineraries for completing a variety of tasks that they might have to do. For example, a user might want to grab a coffee, withdraw cash and post a letter; the application finds the places in which one can do these things, and then determines the optimal route that one can take passing through at least one place where one can carry out each task. The application presents places where these tasks can be carried out and requests that the user selects a place for each task; alternatively, the user can select “ANY” which means that the application takes all of the relevant locations into account (within a reasonable radius of the locations the user has already been to). We worked under the assumption that users had access to the London Underground network; we modelled this internally as we weren’t able to get access to the TfL open data APIs in time for the project.

In terms of algorithmic logic, this involves solving the Travelling Salesman Problem (TSP) for the first case, which is complete for the $\textsf{FP}^{\textsf{NP}}$ complexity class (read: very hard). We approach this problem with backtracking ( $O(N!)$ ) for small ( $N \leq 8$ ) problem instances, the Held-Karp dynamic programming algorithm ( $O(N^2 2^N)$ ) for larger instances ( $N \leq 15$ ), and the Nearest Neighbour and 2-Opt approximation heuristics for even larger instances, though it seems unlikely most users would actually be planning such large itineraries.

In the second case we’re solving the Generalized Travelling Salesman Problem (GTSP), which is a version of the regular TSP except that there are groups of points defined, and one only needs to visit at least one point from each group. We implemented a genetic algorithm approach for this, as in many cases these problems can be very large and thus infeasible to solve exactly.

I worked with Tom Burnell, Andrea Michi, Andrei Cioara and Alice Sibold on this project. I was responsible for the modelling of the Tube network, implementation of some of the backend algorithms for TSP/GTSP as well as overseeing the writing of the final report and documentation. We received an A+ grade (85%) for our work.

Have a look at the repository here.