A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 343-349.
Abstract
We present and investigate a new method for the Traveling Salesman Problem (TSP) that incorporates backbone information into the well known and widely applied Lin-Kernighan (LK) local search family of algorithms for the problem. We consider how heuristic backbone information can be obtained and develop methods to make biased local perturbations in the LK algorithm and its variants by exploiting heuristic backbone information to improve their efficacy. We present extensive experimental results, using large instances from the TSP Challenge suite and real-world instances in TSPLIB, showing the significant improvement that the new method can provide over the original algorithms.
@inproceedings{ijcai2005p182,
title = {A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones},
author = {Zhang, Weixiong and Looks, Moshe},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {343--349},
year = {2005},
url = {https://ijcai.org/proceedings/2005/182},
}
TY - CPAPER TI - A Novel Local Search Algorithm for the Traveling Salesman Problem that Exploits Backbones AU - Zhang, Weixiong AU - Looks, Moshe T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 343 EP - 349 UR - https://ijcai.org/proceedings/2005/182 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
