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 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.

@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},
  volume    = {2},
  number    = {7},
  year      = {2011},
  publisher = {The Science and Information Organization},
  author    = {Muhammad Ali Ismail and Dr. Shahid H. Mirza and Dr. Talat Altaf},
  doi       = {10.14569/IJACSA.2011.020706},
  url       = {https://doi.org/10.14569/IJACSA.2011.020706}
}