A data-guided lexisearch algorithm for the asymmetric traveling salesman problem (Q410535): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 5 users not shown) | |||
Property / 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. | |||
Property / 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. / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C27 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C35 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C59 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6021157 / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q58693426 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1155/2011/750968 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1964057427 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Large traveling salesman problems arising from experiments in X-ray crystallography: A preliminary report on computation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Transforming asymmetric into symmetric traveling salesman problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4461904 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4461906 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Loading Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A data-guided lexisearch algorithm for the bottleneck travelling salesman problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A comparative analysis of several asymmetric traveling salesman problem formulations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3686500 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Algorithm 750: CDT / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tolerance-based branch and bound algorithms for the ATSP / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The travelling salesman problem with precedence constraints. / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 01:44, 5 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A data-guided lexisearch algorithm for the asymmetric traveling salesman problem |
scientific article |
Statements
A data-guided lexisearch algorithm for the asymmetric traveling salesman problem (English)
0 references
3 April 2012
0 references
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.
0 references