Michael Kalochristianakis

Electrical and Computer Engineer

---

optimization of the travelling salesman problem using a genetic approach

given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization. TSP is a special case of the travelling purchaser problem and the vehicle routing problem. The decision version of the TSP (where, given a length L, the task is to decide whether the graph has any tour shorter than L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (perhaps, specifically, exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved completely and even problems with millions of cities can be approximated within a small fraction of 1% (wikipedia).

input

number of nodes

distance matrix
9.25733 75.19099 38.48735 39.74480 38.70106 35.48747 55.16139 93.35338 99.81261 90.76033 0.89554 63.78854 48.85659 72.93861 37.11346 18.16018 72.72176 89.70271 20.53653 54.48069 60.62764 28.31094 36.40388 34.11330 83.76124 31.46316 80.64950 34.39866 18.59114 48.09284 15.32156 60.72770 8.36728 94.93607 43.39615 35.59964 29.05302 10.05130 1.34039 29.89064 22.76942 64.39465 66.53236 19.56381 8.49355 93.19299 64.13262 38.00222 80.09444 63.42116 72.81817 12.86409 39.26988 50.49508 72.45730 41.36256 7.76460 42.07790 66.99202 77.02365 68.98945 9.83730 44.68020 27.95149 48.55646 74.01208 5.26006 96.62766 31.29964 56.10781 42.51480 41.27626 98.66201 49.59467 81.75597 6.93130 6.54872 26.66130 85.42419 31.79558 88.50409 29.24490 86.61315 37.72296 86.06865 96.56075 90.07703 4.52111 1.23914 90.89805 40.91431 63.13865 35.78204 35.60250 75.68314 16.14723 6.73234 95.23888 72.37848 88.78147
population size

number of iterations

elite children percentage

April, 2004