An improved assignment lower bound for the Euclidean traveling salesman problem (Q1058993)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An improved assignment lower bound for the Euclidean traveling salesman problem |
scientific article |
Statements
An improved assignment lower bound for the Euclidean traveling salesman problem (English)
0 references
1985
0 references
A simple transformation of the distance matrix for the Euclidean traveling salesman problem is presented that produces a tighter lower bound on the length of the optimal tour than has previously been attainable using the assignment relaxation. The improved lower bound is obtained by exploiting geometric properties of the problem to produce fewer and larger subtours on the first solution of the assignment problem. This research should improve the performance of assignment based exact procedures and may lead to improved heuristics for the traveling salesman problem.
0 references
flow algorithms
0 references
transformation of the distance matrix
0 references
Euclidean traveling salesman
0 references
lower bound
0 references
improved heuristics
0 references
0 references
