A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model

摘要: With the arrival of multi-cores, every processor has now built-in parallel computational power and that can be fully utilized only if program in execution is written accordingly. This study a part an on-going research for designing new programming model multi-core processors. In this paper we have presented combined concurrent implementation Lin-Kernighan Heuristic (LKH-2) Solving Travelling Salesman Problem (TSP) using newly developed model, SPC3 PM, general purpose found to very simple, highly efficient, scalable less time consuming compare existing LKH-2 serial implementations processing environment. We tested our with medium large size TSP instances TSBLIB. And all these tests proposed approach shown much improved performance scalability.