Imperial College DoC third year group project, team 2.
##Project Abstract Individuals often face the problem of having to develop an itinerary for efficiently completing various tasks, many of which can only be done at certain locations. For example, they may have to withdraw cash and meet a friend for coffee during their (short) lunch break. Such an itinerary may be easily planned by one who knows the exact locations he needs to visit, the order in which he should visit them, and their distances from each other / his current position, however triviality vanishes when any of these are unknown. Our project aims to provide a user with a system that can determine a suitable route to complete all of his tasks. This differs from existing routing products in that our system is intended to be able to cope with planning routes incorporating multiple destinations in an arbitrary order, as well as situations where the exact locations or even types of locations may not necessarily be well-defined. In motivation, consider a user who wants to post a letter and fetch a coffee. Our application could suggest visiting a postbox the user is unaware of in a street closely neighbouring a nearby Starbucks store, rather than venturing to the Post Office he is familiar with, situated farther away.
##High-level Algorithmic Discussion Given a list of tasks and their possible locations, find a route that goes through some of the locations, at a minimum cost, such that all tasks are completed - this is an instance of the Generalised Travelling Salesman Problem (GTSP); it can be reduced to the standard TSP.