This paper proposes a novel solution for the Traveling Salesman Problem, a NP (non-deterministic polynomial-time)hardness problem. The algorithm presented in this paper offers an innovative solution by combining the qualities of aNearest Neighbor (NN) greedy algorithm and the Genetic Algorithm (GA), by overcoming their weaknesses. The paperanalyses the algorithm features/improvements and presents this implementation on a FPGA based target board. Theexperimental results of the algorithm, tested in software (Matlab) and implemented on a portable hardware (FPGA forGA, Raspberry Pi 3 for NN) show a significant improvement: a shorter route, compared to NN , a shorter running time(less generations) compared to traditional GA , and reaching the optimal minimum (validated by Matlab). In real time,the algorithm runs on a handheld console, which can also act as a server, through a custom Android client application.
展开▼