CONFERENCE PROCEEDINGS
Advanced Search
Home > Proceedings > Volume 13074 > Article
Paper
14 March 2024 Simple and fast TSP initialization by Delaunay graph
Jimi Tuononen, Pasi Fränti
Author Affiliations +
Proceedings Volume 13074, Fifth International Conference on Image, Video Processing, and Artificial Intelligence (IVPAI 2023); 130740I (2024) https://doi.org/10.1117/12.3023741
Event: Fifth International Conference on Image, Video Processing and Artificial Intelligence, 2023, Shenzhen, China
Abstract
Finding an initial solution for traveling salesman fast and with reasonable quality is needed both by the state-of-the-art local search and branch-and-bound optimal algorithms. Classical heuristics require O(n2) and their quality may be insufficient to keep the efficiency of the local search high. In this paper, we present two fast variants that utilize a Delaunay neighborhood graph. The best methods achieve 2.66% gap for Dots datasets, and 15.04% gap for the selected TSPLIB datasets. However, these results were obtained with slower algorithms. The best of the fast methods achieved 5.76% gap for Dots datasets, and 19.07% gap for the selected TSPLIB datasets in 307 milliseconds, on average.
(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.
Citation Download Citation
Jimi Tuononen and Pasi Fränti "Simple and fast TSP initialization by Delaunay graph", Proc. SPIE 13074, Fifth International Conference on Image, Video Processing, and Artificial Intelligence (IVPAI 2023), 130740I (14 March 2024); https://doi.org/10.1117/12.3023741
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
 7 PAGES
DOWNLOAD PAPER SAVE TO MY LIBRARY
GET CITATION
Advertisement
Advertisement
RIGHTS & PERMISSIONS
Get copyright permission  Get copyright permission on Copyright Marketplace
KEYWORDS
Nonlinear optimization
RELATED CONTENT
Subscribe to Digital Library
Receive Erratum Email Alert
Back to Top