PARALLEL DAVIS'S ORDER CROSSOVER USING TRUE DUAL PORT RAM OF FPGA - AN APPROACH TO SOLVE TRAVELLING SALESMAN PROBLEM BY GENETIC ALGORITHM

Abstract

Travelling Salesman Problem (TSP) is an optimization problem. It has several applications, such as scheduling, VLSI, logistics, supply chain optimization. TSP is a NP-Hard problem, so it is impossible to find an optimal solution in polynomial time. There is much research that improves TSP performance for thousands of cities, such as Tabu algorithm, neural network, genetic algorithm (GA). In this paper, we suggest a proposed solution to improve parallelization of GA in order to reduce processing time when applied to solve TSP by parallel OX11 step using True Dual Port RAM of the Field-Programmable Gate Array (FPGA).