Plan Your Round Trip is a project created for my bachelor thesis. It implements heuristics to solve the Traveling Salesman Problem (TSP). The TSP is the problem of finding the shortest route from a starting point to different locations and back to the starting point. Heuristics do not necessarily provide the ideal solution - they are used to get good solutions in a short time.
An initial solution is found with the Nearest Neighbor algorithm. In each step one looks for the nearest stop (that is not considered yet) and adds it to the route. This creates the initial tour which is used for the 2-opt algorithm (a tour improvement algorithm). This algorithm needs an initial solution and inverses the order between two stops in each step. If an improvement is found, this new route is used and the inversion starts again. This happens until no improvement can be found.
You can use the implementation of the algorithms for free. It is released under the MIT-License - you can use, distribute, and change the source code. For more information on the MIT-License and the source code of my project, please visit my Github Project.
The heuristics could handle more locations, but since Google Maps is used, there are some limitations to consider. For the use of the Google Maps API (which provides functionality to get route informations) only a specific contingent is available. It could happen that Google rejects the request even if you are using less than ten locations because the quota for the day is reached.
Should you have any questions, don't hesitate to contact me via email.
Please be aware that this site does not necessarily provide the ideal solution for your round trip. This website uses algorithms to provide a good solution in a short time. For more information click here.
Overall round trip: 0 km,
Detailed Directions