Multi-core-, multi-thread-based optimization algorithm for large-scale traveling salesman problem

With the rapid development of general hardware technology, microcomputers with multi-core CPUs have been widely applied in commercial services and household usage in the last ten years. Multi-core chips could, theoretically, lead to much better performance and computational efficiency than single-core chips. But so far, they have not shown general advantages for users, other than for operating systems and some specialized software. It is not easy to transform traditional single-core-based algorithms into multi-core-, multi-thread-based algorithms that can greatly improve efficiency, because of difficulties in computation and scheduling of hardware kernels, and because some programming languages cannot support multi-core, multi-thread programming. Therefore, a kind of multi-core-, multi-thread-based fast algorithm was designed and coded with Delphi language for the medium- and large-scale traveling salesman problem instances from TSPLIB, which can fully speed up the searching process without loss of quality. Experimental results show that the algorithm proposed can, under the given hardware limitations, take full advantage of multi-core chips and effectively balance the conflict between increasing problem size and computational efficiency and thus acquire satisfactory solutions. (C) 2020 The Authors. Published by Elsevier B.V. on behalf of Faculty of Engineering, Alexandria University.

Automated summary

Multi-core computers have been widely used in commercial services and household usage in the past decade, although they have not shown general advantages for users. Due to hardware and programming language limitations, it is difficult to transform traditional algorithms into multi-core, multi-thread algorithms, requiring the design of new algorithms to fully utilize multi-core chips.