Human – Computer TSP solver is a tool meant for visualizing the solving of travelling salesman problem with Random Mix algorithm in 2-dimensional space. The idea of this webpage is to compare what kind of impact would it cause if the user could select which area the algorithm focuses on. On the page, left side of the screen is the one where the user can choose which points the search should focus on. The right side of the page does not have drawing functionality, because this is where the computer applies the algorithm to the whole dataset.
1. Add desired data from the samples or read any file of your own.
2. Make a greedy/random initial solution
3. Press start to begin optimization process with Random mix algorithm. Data is passed to a server which makes desired number of iterations and returns the solution.
Optimization can be paused with the same button.
The website supports adding the users own data. However, desired kind of formatting is expected so that the data is read correctly. The system automatically recognizes which type of data is given from the formatting. Note that big datasets are heavy for the website. Recommended maximum amount of points is something around 5000 (slow machines) to 20000 (fast machines).
The simplest kind of formatting follows these rules: each separate data point is separated by a newline character and a pair of values in one data point is separated with a space. Like in this example:
With this formatting the algorithm is ran using euclidean distance function and visualization is done on a blank map. Calculations are done with the original data, but visualization uses normalization to fit the data between -1 and 1 latitude/longitude. Small area is used to avoid stretching problems caused by the latitude/longitude system.
The TSP file format is a normal textfile with additional header information used to describe the data. These files have either .tsp or .txt extension. An example:
While most of these headers do not matter, the critical parts to notice here is the NODE_COORD_SECTION/EOF and indexing in front of the data points. All of these things should be included so that the data is read correctly. EDGE_WEIGHT_TYPE can be included to change distance function between euclidean or haversine (if missing, default is euclidean). Expected values are "EUC_2D" or "haversine"/"HVS" with spaces between the words. Haversine distance function also changes the map to be a normal google map type.