The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science and operations research. The primary purpose is to develop an optimized algorithm to solve it. There are numerous methodology developed over the decades to find the ideal solution in the shortest span of time & space. One of the techniques in solving TSP is to apply Genetic Algorithm to it.
In this academic project, the algorithm is developed (written in Java), to carry out an experimental approach to find an ideal solution to a problem when our solution space spans across up to 2.432902e+18 (20!) possible elements.
Developed By:
- Abdusamed Ahmed
- Yanfei Peng
Sample Output
{2,6,11,14,13,9,15,4,5,18,17,8,16,19,12,0,1,10,3,7,}1967.5264056386352
{19,0,7,8,12,18,2,5,1,13,9,11,4,3,14,15,16,17,10,6,}1894.903839520548
{19,0,17,18,2,5,1,7,8,9,10,11,12,13,14,15,4,3,16,6,}2042.769478937477
{19,17,4,6,7,8,5,18,2,9,10,11,12,13,14,15,16,3,0,1,}2015.9775166051609
{17,18,16,19,3,5,6,7,8,9,10,11,12,13,14,15,0,4,1,2,}1840.4103911593684
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,}1713.53203210795
{0,1,2,3,4,5,6,7,17,15,16,13,8,11,19,18,14,12,10,9,}1698.5748637784054
{1,2,3,0,14,4,5,6,7,8,9,10,11,12,13,15,16,19,17,18,}1545.1166612330949
{0,1,2,3,4,5,6,7,8,9,17,15,16,13,11,19,18,14,12,10,}1626.8132746815438
{8,6,13,3,4,11,16,10,2,5,14,7,15,19,9,1,0,12,18,17,}2000.2065200279965
{17,15,16,13,8,11,19,18,3,14,12,10,6,5,0,4,1,9,7,2,}1639.0456906378142
{17,2,9,19,18,5,6,7,8,3,4,1,10,11,12,13,14,15,16,0,}1849.8508735207517
{17,18,0,3,4,5,6,7,8,9,10,11,12,13,14,15,1,19,2,16,}1905.8531224078806
{2,9,12,10,11,6,3,5,4,1,0,7,8,13,14,15,16,17,18,19,}1869.6539642986243
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,}1713.53203210795
{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,19,18,}1813.53203210795
{19,0,7,8,17,18,2,5,1,9,10,11,12,13,14,15,4,3,16,6,}1934.713022599705
{19,3,5,6,7,8,0,4,1,9,10,11,12,13,14,15,16,17,18,2,}1895.7881933299584
{17,2,16,9,13,19,15,12,10,11,18,6,3,5,4,1,0,7,8,14,}1783.4546945096292
{0,3,4,5,6,7,8,9,10,11,1,19,12,13,14,15,16,17,18,2,}1835.6807337523321
{1,2,3,0,14,4,5,6,7,8,9,10,11,12,13,16,19,17,18,15,}1435.6601795181994
{0,1,2,3,4,10,11,18,14,15,17,13,12,5,9,6,7,8,16,19,}1734.137410142362
{19,0,7,8,17,15,12,18,2,5,1,13,9,11,4,3,14,10,16,6,}1769.7303262633586
{19,18,3,6,5,0,4,7,8,9,10,11,12,13,14,15,16,17,1,2,}1986.8407082683352
{0,1,8,7,12,4,5,16,2,18,17,9,3,15,19,11,14,6,13,10,}1820.152029170766
Parent A - {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,}1713.53203210795
Parent B - {0,1,2,17,15,16,13,8,11,19,18,3,14,12,10,6,5,4,9,7,}1700.429287030018
START:5:END:13
Child Gen -> {0,1,2,17,15,5,6,7,8,9,10,11,12,13,16,19,18,3,14,4,}:1670.366076419064
Fittest Route -> {1,2,3,0,14,4,5,6,7,8,9,10,11,12,13,16,19,17,18,15,}1435.6601795181994