The Traveling Salesman Problem (TSP) is a combinatorial optimization problem which is NP-hard. So, in pratice heuristics are used to find good approximations of the optimum of a TSP. However, for large problems even these heuristics still require a huge amount of computer time to find a good approximation. We consider the use of parallel computers to speed up the computation for large TSPs. We describe a partitioning based parallel heuristic. Inplementation issues and computational results on a distributed memory parallel computer are reported.
展开▼
