Saturday, July 10, 2021

The Traveling Tourist Problem

POI Path is an interactive route planning map which can help you plot an interesting walk around the city of Zurich, taking in some of the city's most famous landmarks. You just have to select the places that you want to visit in Zurich and POI Path will calculate a route between your selected points of information

The POI Path interactive map is populated with points of interest taken from the Open Data Catalog of the City of Zurich. These include locations such as historical buildings, monuments, churches, art objects in public spaces, and parks & gardens.If you select any of the mapped points of interest then an information window will open to provide information on the selected location.

To plan your walk around the city of Zurich you just have to select the attractions that you wish to visit. The map will then calculate the optimal route taking in all the sights of the city that you wish to see. The route chosen is also optimized to be the most attractive route for walkers or cyclists (using the City's own routing service). If you are happy with the calculated route then you can download it as a gpx file.


Calculating an optimal path taking in a number of different selected points of interest is essentially a Traveling Salesman Problem (in this case with the added constraint of choosing paths attractive for walkers & cyclists). You can get an idea about how to solve Traveling Salesman Problems on Shiny Salesman, which is a tool for solving a global Traveling Salesman Problem (TSP).

The Shiny Salesman tool allows you to choose a number of different locations around the world (or in the USA) to include in the TSP. You can then watch the map solve the traveling salesman problem using your own simulated annealing parameters. Shiny Salesman runs through iterations of possible routes searching for the optimal path. As it does this it also plots the distance of each calculated route so that you can see how many iterations it took to find the quickest possible route.

No comments: