Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? This is a solution to the Traveling Salesman Problem using the Google Maps API with a front-end web interface for visualizing the route, adding stops, and selecting whether to return to origin.
The problem itself is NP-Hard, as the optimal solution cannot be found in polynomial time for an arbitrary number of cities, n. The problem scales as n!. The primary heuristic algorithm used is the algorithm of Christofides and Serdyukov. This is an algorithm that provides a tour that is at most 1.5x the most optimal solution, provided that the location satisfy the triangle inequality and are symmetric (form a metric space).