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

Muhammad Ali Ismail, Dr. Shahid H. Mirza and Dr. Talat Altaf, “A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model ” International Journal of Advanced Computer Science and Applications(IJACSA), 2(7), 2011. http://dx.doi.org/10.14569/IJACSA.2011.020706

@article{Ismail2011,
title = {A Parallel and Concurrent Implementation of Lin-Kernighan Heuristic (LKH-2) for Solving Traveling Salesman Problem for Multi-Core Processors using SPC3 Programming Model },
journal = {International Journal of Advanced Computer Science and Applications},
doi = {10.14569/IJACSA.2011.020706},
url = {http://dx.doi.org/10.14569/IJACSA.2011.020706},
year = {2011},
publisher = {The Science and Information Organization},
volume = {2},
number = {7},
author = {Muhammad Ali Ismail and Dr. Shahid H. Mirza and Dr. Talat Altaf}
}