CONFERENCE PROCEEDINGS
Advanced Search
Home > Proceedings > Volume 12253 > Article
Paper
27 June 2022 Parallelizing the all-nearest-neighbor algorithm for Travelling Salesman Problem
Xiangyi Zhao
Author Affiliations +
Proceedings Volume 12253, International Conference on Automation Control, Algorithm, and Intelligent Bionics (ACAIB 2022); 122530X (2022) https://doi.org/10.1117/12.2639458
Event: Second International Conference on Automation Control, Algorithm, and Intelligent Bionics (ACAIB 2022), 2022, Qingdao, China
Abstract
Travelling Salesman Problem (TSP) is an NP-hard problem in combinational optimization important in operations research and theoretical computer science. The all-nearest-neighbor (NN) algorithm is a typical algorithm to solve TSP due to its brevity and effectiveness. However, as graphs become larger, the cubic growth of computational time makes sequential algorithms unfavorable. This paper presents two parallel all-nearest neighbor algorithms - the coarse-grained parallel model (PnnCG) and the integrated parallel model (PnnIN) to optimize the runtime of the sequential NN for TSP on large graphs. PnnCG employs a top-level parallelization to simultaneously search for the shortest tours within subgroups of the cities. PnnIN adds a lower level of parallelization based on PnnCG by again dividing the cities into subgroups when searching for the nearest city of the current one. To verify the effectiveness of PnnCG and PnnIN, we compare them with NN on ten TSP benchmark graphs whose sizes range from 48 to 11849. PnnCG reaches a speedup of 2-3 on graphs with a size from around 50 to 11500. PnnIN, though slower in smaller graphs, outperforms PnnCG on graphs with a size larger than 11500. Our analysis demonstrates that the proposed parallel models significantly decrease the runtime needed.
© (2022) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Citation Download Citation
Xiangyi Zhao "Parallelizing the all-nearest-neighbor algorithm for Travelling Salesman Problem", Proc. SPIE 12253, International Conference on Automation Control, Algorithm, and Intelligent Bionics (ACAIB 2022), 122530X (27 June 2022); https://doi.org/10.1117/12.2639458
ACCESS THE FULL ARTICLE
ORGANIZATIONAL
Sign in with credentials provided by your organization.
INSTITUTIONAL
Select your institution to access the SPIE Digital Library.
SELECT YOUR INSTITUTION
PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.
PERSONAL SIGN IN
No SPIE Account? Create one
PURCHASE THIS CONTENT
SUBSCRIBE TO DIGITAL LIBRARY
50 downloads per 1-year subscription
Members: $195
Non-members: $335 ADD TO CART
25 downloads per 1 - year subscription
Members: $145
Non-members: $250 ADD TO CART
PURCHASE SINGLE ARTICLE
Includes PDF, HTML & Video, when available
Members: $17.00
Non-members: $21.00 ADD TO CART
PROCEEDINGS
 9 PAGES
DOWNLOAD PAPER SAVE TO MY LIBRARY
GET CITATION
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Performance modeling
Integrated modeling
Data modeling
Optimization (mathematics)
Algorithms
Computer science
Parallel computing
RELATED CONTENT
Subscribe to Digital Library
Receive Erratum Email Alert
Back to Top