TSP

Project in Java to solve the Travelling Salesman Problem (TSP). An approximation solution with a self-organizing maps (SOM) is proposed.

som-xqf131-solution

Algorithms

Self-organizing maps

Data

TSP files from TSPLIB in the following format:

NAME : a280
COMMENT : drilling problem (Ludwig)
TYPE : TSP
DIMENSION: 280
EDGE_WEIGHT_TYPE : EUC_2D
NODE_COORD_SECTION
  1 288 149
  2 288 129
  3 270 133
  4 256 141
  5 256 157
  6 246 157
  7 236 169
  .
  .
  .
  EOF

Results

Next, the results of 10 different TSP files using the SOM algorithm implementation. The results are calculated after executing and averaging the 10 cases 5 times.

TSP File	# Points	Optimal Tour	Curr Tour	MAPE (%)	Elapsed Time (ms)
XQF131	131	564	598.915	6.1906	245
XQG237	237	1019	1108.2272	8.7563	714
PMA343	343	1368	1464.7101	7.0695	1571
XQL662	662	2513	2804.3936	11.5954	4941
RBX711	711	3115	3428.1617	10.0533	5806
PBD984	984	2797	3102.7567	10.9316	10225
DKA1376	1376	4666	5242.9936	12.3659	19565
DJA1436	1436	5257	5855.2285	11.3797	21390
DJC1785	1785	6115	6864.0603	12.2496	32591
DCB2086	2086	6600	7452.5379	12.9172	44726

With a weighted average MAPE of 11.5946 %. Below, the solution accuracy in one chart:

solution accuracy

And the time complexity of the solution is:

time complexity

Experimentally, it was calculated that the computational complexity of the solution is quadratic, which is better than the factorial time (natural behavior of the problem).

Program Execution Rules

The repository has an executable file in the jar folder. The .JAR program must be run with Java 8 or higher.

The program can be run in 2 modes: GUI or TESTS. Below, some examples of how to call the program in each mode.

GUI mode example: java -jar TSP_Solver-vX param-mode

    java -jar TSP_Solver-v0.6.jar
    java -jar TSP_Solver-v0.6.jar GUI

Tests mode example: java -jar TSP_Solver-vX param-mode param-directory param-algorithm param-number-tests

    java -jar TSP_Solver-v0.6.jar TESTS
    java -jar TSP_Solver-v0.6.jar TESTS Project/TSP/ SOM
    java -jar TSP_Solver-v0.6.jar TESTS Project/TSP/ SOM
    java -jar TSP_Solver-v0.6.jar TESTS Project/TSP/ SOM 5

The project was developed in the Eclipse IDE, and is located in the code folder.

TSP Solver GUI

tsp-solver-gui

Contributing and Feedback

Any kind of feedback/criticism would be greatly appreciated (algorithm design, documentation, improvement ideas, spelling mistakes, etc…).

Authors

Created by Andrés Segura Tinoco
Created on Jan 02, 2020

License

This project is licensed under the terms of the MIT license.

TSP

Travelling Salesman Problem solver

TSP