A new extension principle algorithm for the traveling salesman problem
作者:
Guntram Scheithauer,
Johannes Terno,
期刊:
Mathematische Operationsforschung und Statistik. Series Optimization
(Taylor Available online 1982)
卷期:
Volume 13,
issue 2
页码: 231-245
ISSN:0323-3898
年代: 1982
DOI:10.1080/02331938208842784
出版商: Akademic-Verlag
数据来源: Taylor
摘要:
In this paper, an algorithm for solving the asymmetric traveling salesman problem is developed and tested by computation. This algorithm is based on the extension principle by Schoch and uses the assignment problem relaxation of the traveling salesman problem for computing lower bounds. Computational experience with randomly generated test problems indicate that the present algorithm yields good results in runtime which are comparable with the results of Smith/Srinivasan/Thompson. Computational experience are reported for up to 120-node problems with uniformly distributed and approximately normally distributed cost.
点击下载:
PDF (767KB)
返 回