A data-guided lexisearch algorithm for the asymmetric traveling salesman problem
type: Item
instance of: scholarly article
title: A data-guided lexisearch algorithm for the asymmetric traveling salesman problem
zbMATH Open document ID: 1235.90123
DOI: 10.1155/2011/750968
author: Zakir Hussain Ahmed
published in: Mathematical Problems in Engineering
publication date: 2012-04-03T00:00:00Z
review text: Summary: A simple lexisearch algorithm that uses path representation method for the asymmetric traveling salesman problem (ATSP) is proposed, along with an illustrative example, to obtain exact optimal solution to the problem. Then a data-guided lexisearch algorithm is presented. First, the cost matrix of the problem is transposed depending on the variance of rows and columns, and then the simple lexisearch algorithm is applied. It is shown that this minor preprocessing of the data before the simple lexisearch algorithm is applied improves the computational time substantially. The efficiency of our algorithms to the problem against two existing algorithms has been examined for some TSPLIB and random instances of various sizes. The results show remarkably better performance of our algorithms, especially our data-guided algorithm.
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C59
zbMATH DE Number: 6021157
Wikidata QID: Q58693426
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1155/2011/750968
OpenAlex ID: W1964057427
cites work: Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation
cites work: Transforming asymmetric into symmetric traveling salesman problems
cites work: Q4461904
cites work: Q4461906
cites work: The Loading Problem
cites work: A data-guided lexisearch algorithm for the bottleneck travelling salesman problem
cites work: A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints
cites work: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints
cites work: A comparative analysis of several asymmetric traveling salesman problem formulations
cites work: Q3686500
cites work: Algorithm 750: CDT
cites work: Tolerance-based branch and bound algorithms for the ATSP
cites work: The travelling salesman problem with precedence constraints.
description: scientific article; zbMATH DE number 6021157