Analysis of a high-performance TSP solver on the GPU

DOI10.1145/3154835zbMATH Open1414.68150OpenAlexW2782913138WikidataQ131115887 ScholiaQ131115887MaRDI QIDQ4577952FDOQ4577952

Authors: J. Robinson, Susan V. Vrbsky, Xiaoyan Hong, Brian P. Eddy 

Publication date: 6 August 2018

Published in: ACM Journal of Experimental Algorithmics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3154835

Recommendations

• Multiple \(k\)-opt evaluation multiple \(k\)-opt moves with GPU high performance local search to large-scale traveling salesman problems
• scientific article; zbMATH DE number 1304530
• The traveling salesman problem: An overview of exact and approximate algorithms
• Generalized traveling salesman problem reduction algorithms
• Discrete heat transfer search for solving travelling salesman problem

zbMATH Keywords

TSPCUDAGPGPU2-opt\(k\)-swap

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Parallel algorithms in computer science (68W10)

Cites Work

• TSPLIB—A Traveling Salesman Problem Library
• Introduction to algorithms.
• A method for solving traveling-salesman problems
• On the solution of traveling salesman problems
• Stability aspects of the traveling salesman problem based on \(k\)-best solutions
• An Effective Heuristic Algorithm for the Traveling-Salesman Problem
• Title not available (Why is that?)
• Worst case and probabilistic analysis of the 2-Opt algorithm for the TSP

Cited In (2)

• A novel list-constrained randomized VND approach in GPU for the traveling thief problem
• Solving the examination timetabling problem in GPUs

Uses Software

• TSPLIB
• CUDA
• OpenCL

This page was built for publication: Analysis of a high-performance TSP solver on the GPU

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4577952)